信息学竞赛习题解答5(模拟).doc

《算法与程序实践》习 题 解 答5——模拟
现实中的有些问题，难以找到公式或规律来解决，只能按照一定步骤，不停地做下去，最后才能得到答案。这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解决此问题的行为即可。这一类的问题可以称之为“模拟题”。比如下面经典的约瑟夫问题：

CS51：约瑟夫问题
（来源： 2746，程序设计导引及在线实践（李文新）例6.1 P141）
问题描述：
约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1 开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
输入：
每行是用空格分开的两个整数，第一个是 n，第二个是m ( 0 < m, n < 300) 。最后一行是：
0 0
输出：
对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号。
样例输入：
6 2
12 4
8 3
0 0
样例输出：
5
1
7
解题思路：
初一看，很可能想把这道题目当作数学题来做，即认为结果也许会是以n和m为自变量的某个函数f(n,m)，只要发现这个函数，问题就迎刃而解。实际上，这样的函数很难找，甚至也许根本就不存在。用人工解决的办法就是将n个数写在纸上排成一圈，然后从1开始数，每数到第m个就划掉一个数，一遍遍做下去，直到剩下最后一个。有了计算机，这项工作做起来就会快多了，我们只要编写一个程序，模拟人工操作的过程就可以了。
用数组anLoop来存放n个数，相当于n个数排成的圈；用整型变量 nPtr指向当前数到的数组元素，相当于人的手指；划掉一个数的操作，就用将一个数组元素置0的方法来实现。人工数的时候，要跳过已经被划掉的数，那么程序执行的时候，就要跳过为0的数组元素。需要注意的是，当nPtr指向anLoop中最后一个元素（下标n-1）时，再数下一个，则nPtr要指回到数组的头一个元素（下标0），这样anLoop才象一个圈。

参考程序：
#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 300
int aLoop[MAX_NUM+1];

int main()
{
int n,m,i;
while(1)
{
scanf("%d%d",&n,&m);
if(n==0) break;
for(i=0;i<n;i++)
aLoop[i]=i+1;
int nPtr=0; //存储位置信息
for(i=0;i<n;i++) //每次循环将1只猴子赶出圈子
{
int nCount=0; //记录本轮数到的猴子数目
while(nCount<m) //一直要数出m个猴子
{
while(aLoop[nPtr]==0) //跳过已经出圈的猴子
nPtr=(nPtr+1)%n; //到下一个位置，如果到最后就跳到第1个
nCount++;
nPtr=(nPtr+1)%n;
}
nPtr--; //找到要出圈的猴子，位置要回退一个
if(nPtr<0)
nPtr=n-1;
if(i==n-1) //最后一个出圈的猴子
printf("%d\n",aLoop[nPtr]);
aLoop[nPtr]=0;
}
}

return 0;
}

注意事项：
上面的程序完全模拟了人工操作的过程，但因为要反复跳过为0 的数组元素，因此算法的效率不是很高。后文的“链表”一章，采用单链表进行模拟来解决本题，就能省去跳过已出圈的猴子这个操作，大大提高了效率。
n 个元素的数组，从下标0 的元素开始存放猴子编号，则循环报数的时候，下一个猴子的下标就是“(当前猴子下标+ 1 )% n”。这种写法比用分支语句来决定下个猴子的下标是多少，更快捷而且写起来更方便。
对于本题，虽然很难直接找出结果函数 f(n, m)，但是如果仔细研究，找出局部的一些规律，比如，每次找下一个要出圈的猴子时，直接根据本次的起点位置就用公式算出下一个要出圈的猴子的位置，那么写出的程序就可以省去数m只猴子这个操作，大大提高效率，甚至不需要用数组来存放 n 个数。请写出这个高效而节省空间的程序。
问题一：在数组里循环计数的时候，一定要小心计算其开始的下标和终止的下标。比如，语句15，循环是从0到n-1，而不是从0 到n。
问题二：nPtr--到nPtr=n-1回退一个位置，易被忽略或写错。比如只写了语句nPtr--，忘了处理nPtr变成小于0的情况。

CS52：醉酒的狱卒（The Drunk Jailer）
（来源：POJ 1218 ZOJ 1350，程序设计方法及在线实践指导（王衍等） P169）
问题描述：
某个监狱有一排、共n间牢房，一间挨一间。每间牢房关着一名囚犯，每间牢房的门刚开始时都是关着的。
有一天晚上，狱卒厌烦了看守工作，决定玩一个游戏。游戏的第1轮，他喝了一杯酒，然后沿着监狱，把所有的牢房的门挨个挨个打开；第2轮，他又喝了一杯酒，然后沿着监狱，把编号为偶数的牢房的门关上；第3轮，他又喝了一杯酒，然后沿着监狱，对编号为3的倍数的牢房，如果牢房的门开着，则关上，否则打开；……，狱卒重复游戏n轮。游戏结束后，他喝下最后一杯酒，醉倒了。
这时，囚犯才意识到他们牢房的门可能是开着的，而且狱卒醉倒了，所以他们越狱了。
给定牢房的数目，求越狱囚犯的人数。
输入：
输入文件的第1行为一个正整数，表示测试数据的个数。每个测试数据占一行，为一个整数n，5<=n<=100，表示牢房的数目。
输出：
对每个测试数据所表示的牢房数目n，输出越狱的囚犯人数。
样例输入：
2
5
100
样例输出：
2
10
解题分析：
n轮游戏后，哪些牢房的门是开着的，并无规律可循。但这个游戏的规则和过程很简单：游戏有n轮，第j轮游戏是将编号为j的倍数的牢房状态变反，原来是开着的，则关上，原来是关着的，则打开，j=1,2,3,…,n。这些规则和过程用程序能较容易地实行，所以适合采用“模拟”的思路来求解。
具体实现时可定义一个一维数组，每个元素表示对应牢房的状态，初始为1，表示牢房门是关着的，然后模拟游戏的每一轮：第j轮时，改变牢房编号为j的倍数的牢房状态，为0则改为1，为1则改为0。n轮游戏后，统计状态为0的牢房数即可。

参考程序：
#include <stdio.h>
#include <string.h>

int main()
{
int nCases,n;
int prision[101]; //n个牢房，n最多100个,1表示锁着，0表示开着
int i,j;

scanf("%d",&nCases);
for(i=0;i<nCases;i++)
{
scanf("%d",&n);
for(j=1;j<=n;j++)
prision[j]=1;
for(j=1;j<=n;j++)
{
int tmp=j;
while(tmp<=n)
{
prision[tmp]=(prision[tmp]==1)?0:1;
tmp+=j;
}
}
int num=0;
for(j=1;j<=n;j++)
if(!prision[j]) num++;
printf("%d\n",num);
}
return 0;
}
CS53：花生问题（同CS93）
（来源： 2950，程序设计导引及在线实践（李文新）例4.3 P107）
问题描述：
鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。
鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图5-1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内，可以做下列四件事情中的一件：
1) 从路边跳到最靠近路边（即第一行）的某棵花生植株；
2) 从一棵植株跳到前后左右与之相邻的另一棵植株；
3) 采摘一棵植株下的花生；
4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。

图 5-1 花生地图 5-2 摘花生过程
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。
例如在图5-2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4) 的植株下长有花生，个数分别为13、7、15、9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。
输入：
输入的第一行包括三个整数，M, N 和K，用空格隔开；表示花生田的大小为M *N（1 <= M, N <= 20），多多采花生的限定时间为K（0 <= K <= 1000 ）个单位时间。接下来的M 行，每行包括N 个非负整数，也用空格隔开；第i + 1 行的第j 个整数Pij（0 <= Pij <= 500） 表示花生田里植株(i, j)下花生的数目，0 表示该植株下没有花生。
输出：
输出包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。

样例输入：
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
样例输出：
37
解题思路：
试图找规律，得到一个以花生矩阵作为自变量的公式来解决这个问题，是不现实的。结果只能是做了才知道。即走进花生地，每次要采下一株花生之前，先计算一下，剩下的时间，够不够走到那株花生，采摘，并从那株花生走回到路上。如果时间够，则走过去采摘；如果时间不够，则采摘活动到此结束。

参考程序：
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>

int T,M,N,K;
#define MAX_NUM 55
int aField[MAX_NUM][MAX_NUM];

int main()
{
int i,j,t,m,n;
scanf("%d",&T);
for(t=0;t<T;t++)
{
scanf("%d%d%d",&M,&N,&K);
for(m=1;m<=M;m++)
for(n=1;n<=N;n++)
scanf("%d",&aField[m][n]);
int nTotalPeanuts=0; //摘得的花生总数
int nTotalTime=0; //已经花去的总时间
int nCuri=0,nCurj; //当前位置坐标
while(nTotalTime<K)
{
int nMax=0,nMaxi,nMaxj; //最大的花生数目，及其所处的位置
//寻找下一个最大花生数目及其位置
for(i=1;i<=M;i++)
{
for(j=1;j<=N;j++)
{
if(nMax<aField[i][j])
{
nMax=aField[i][j];
nMaxi=i;
nMaxj=j;
}
}
}
if(nMax==0) //地里没有花生了
break;
if(nCuri==0)
nCurj=nMaxj; //如果当前位置在路上，那么应走到横坐标nMaxj处，再进入花生地
//下面检查剩余的时间够不够走到nMaxi,nMaxj处，摘取花生，并回到路上
if(nTotalTime+nMaxi+1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj)<=K)
{
nTotalTime+=1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj);
nCuri=nMaxi;
nCurj=nMaxj;
nTotalPeanuts+=aField[nMaxi][nMaxj];
aField[nMaxi][nMaxj]=0; //摘走花生赋值为0
}
else
break;
}
printf("%d\n",nTotalPeanuts);

}

return 0;
}

实现技巧：
用二维数组存放花生地的信息是很自然的想法。然而，用aField[0][0]还是aField[1][1] 对应花生地的左上角，是值得思考一下的。因为从地里到路上还需要1 个单位时间，题目中的坐标又都是从1 开始，所以若aField[1][1] 对应花生地的左上角，则从aField[i][j] 点，回到路上所需时间就是i，这样更为方便和自然，不易出错。并不是C/C++ 的数组下标从0 开始，我们使用数组的时候，就要从下标为0 的元素开始用。
常见问题：
问题一：读题时应该仔细读。有的同学没有看到每次只能拿剩下花生株中最大的，而是希望找到一种在规定时间内能够拿最多花生的组合，把题目变成了另外一道题。
问题二：有的同学没有读到“没有两株花生株的花生数目相同”的条件，因此把题目复杂化了。
问题三：这个题目是假设猴子在取花生的过程中不会回到大路上的，有些同学在思考是否可能在中间回到大路上，因为题目没说在大路上移动要花时间，所以有可能中途出来再进去摘的花生更多。

CS54：分糖果的游戏（Candy Sharing Game）
（来源：POJ 1666 ZOJ 1814，程序设计方法及在线实践指导（王衍等） P186）
问题描述：
N个学生围成一圈坐着，面向老师（老师位于中心）。每个学生手头上刚开始都有偶数块糖果。每轮游戏：老师一吹哨子，每个学生将他的糖果的一半分给他右边相邻的学生；N个学生分糖果完毕后，如果某个学生手头上的糖果数为奇数，则由老师再给一块糖果凑成偶数块。当所有学生的糖果数一样时，则游戏结束。要求编写程序，输出游戏进行的轮数，以及最终每个学生手头糖果的块数。
输入：
输入文件描述了多次游戏（即输入文件中包含多个测试数据）。每次游戏的数据第一行是一个整数N，表示学生的人数，接下来是N个偶数，代表初始时N个学生手上的糖果数目（逆时针排列）。输入文件最后一行为0，表示输入结束。
输出：
对每次游戏，输出游戏进行的轮数，以及游戏结束后每个学生手上的糖果数。
样例输入：
6
36
2
2
2
2
2
11
22
20
18
16
14
12
10
8
6
4
2
4
2
4
6
8
0
样例输出：
15 14
17 22
4 8
注意：
游戏会在有限次内结束，因为（设每轮游戏过后N个学生拥有糖果的最大数目为max，最小数目为min）：
（1）max不会增加；
（2）min不会减少；
（3）且任何一个糖果数多于min的学生，他的糖果数不会减少到min；
（4）如果max和min不等，则至少有一个学生，他的糖果数会增加，这个学生就是糖果数最少的学生。
解题分析：
对于给定的学生人数N，以及初始时N个学生的糖果数，最终需要进行游戏的轮数以及最终每个学生的糖果数是没有规律可循的，只能进行模拟。模拟游戏的每一轮，直到N个学生的糖果数一样为止。
以样例输入中的第1个测试数据为例解释游戏的过程，如图5.9所示，图（a）中圆圈里的数字表示初始时6个学生的糖果数，旁边的数字表示学生的序号（从0开始，按逆时针顺序排列）。图（b）表示第1轮游戏，每个人将手上糖果数的一半分给右边的学生（虚线箭头所示）；如果某个学生手头上的糖果数位奇数，则由老师再给一块糖果凑成偶数块，如图（c）所示；第1轮游戏过后，每人手上的糖果数如图（d）所示。
具体实现时，可以用一整型数组candys存储N个学生（序号为0~N-1，如图5.9（a）所示）的糖果数。在模拟每一轮游戏时，要先用临时变量（设为half0）保存第N-1个学生糖果数的一半，然后将第i个学生的糖果数candys[i]更新为：candys[i]/2+candys[i-1]/2；最后一个学生，即第0个学生的糖果数更新为：candys[0]/2+half0。
在判断N个学生的糖果数是否一致时，注意只要有前后两个学生的糖果数不一致的情况，就可以判断这N个学生的糖果数不一致；另外第N-1个学生右边相邻的学生是第0个学生，所以要取模，即要判断candys[i]与candys[(i+1)%N]是否相等。
1
0

18
2
2
2
2
2
36
5
36

1
2
2

1
1

4
2
2
2

2

1
1
3

图（a）初始 图（b）分糖果
+1
2
2
2
2
20
20
2
2
2
2
19
19

+1

图（c）凑成偶数 图（d）第1轮游戏结束后
图5.9 分糖果游戏（第1轮）

CS55：爬动的蠕虫(Climbing Worm)
（来源： ZOJ 1494，程序设计方法及在线实践指导（王衍等） P192）
问题描述：
一只1英才长的蠕虫在一口深为n英寸井的底部。每分钟蠕虫可以向上爬u英寸，但必须休息1分钟才能接着往上爬。在休息的过程中，蠕虫又下滑了d英寸。上爬和下滑重复进行。蠕虫需要多长时间才能爬出井？不足一分钟按一分钟计，并且假定只要在某次上爬过程中蠕虫的头部到达了井的顶部，那么蠕虫就完成任务了。初始时，蠕虫是趴在井底的（即高度为0）。
输入：
输入文件包括多个测试数据。每个测试数据占一行，为3个正整数n,u,d，其中n是井的深度，u是蠕虫每分钟上爬的距离，d是蠕虫在休息的过程中下滑的距离。假定d<u，n<100。n=0表示输入数据结束。
输出：
对输入文件中的每个测试数据，输出一个整数，表示蠕虫爬出井所需要的时间（分钟）。
样例输入：
10 2 1
20 3 1
0 0 0
样例输出：
17
19

解题分析：
蠕虫爬动的过程和判断蠕虫是否爬出井的依据都是很简单的，到底需要多少分钟才能爬出井要通过计算得出，本题适合用“模拟”思路求解。
在本题中，整个模拟过程是通过一个永真循环实现的，在该循环里，先是上爬一分钟，蠕虫的高度要加上u，然后判断是否达到或超过了井的高度，如果是则退出循环；如果不是则要下滑d距离。也就是说，执行一次循环，实际上上爬了一分钟和下滑一分钟。是否退出循环是在上爬后判断的。

10