目 录
CS51：约瑟夫问题 ........................................................................................................................... 1 CS52：花生问题（同CS93） .......................................................................................................... 3 CS53：显示器（见CS327） ............................................................................................................ 6 CS54：排列..................................................................................................................................... 13 CS55：宇航员 ................................................................................................................................. 15 CS56：数根..................................................................................................................................... 26 CS57：武林..................................................................................................................................... 27 CS58：循环数 ................................................................................................................................. 32 CS59：醉酒的狱卒（The Drunk Jailer） ................................................................................. 36 CS510：网络拥堵解决方案（Eeny Meeny Moo） ....................................................................... 38 CS511：约瑟夫环问题（Joseph） ............................................................................................... 41 CS512：另一个约瑟夫环问题（未做）（Yet Another Josephus Problem） ......................... 43 CS513：三子棋游戏（Tic Tac Toe） ......................................................................................... 43 CS514：扫雷游戏（Mine Sweeper） ........................................................................................... 46 CS515：弹球游戏（Linear Pachinko） ..................................................................................... 50 CS516：分糖果的游戏（Candy Sharing Game） ....................................................................... 53 CS517：爬动的蠕虫(Climbing Worm) ......................................................................................... 54 CS518：遍历迷宫（Maze Traversal） ....................................................................................... 55 CS319：........................................................................................................................................... 58 CS320：............................................................................................................. 错误!未定义书签。 CS321：............................................................................................................. 错误!未定义书签。 CS322：............................................................................................................. 错误!未定义书签。 CS323：............................................................................................................. 错误!未定义书签。 CS324：............................................................................................................. 错误!未定义书签。 CS325：............................................................................................................. 错误!未定义书签。 CS326：............................................................................................................. 错误!未定义书签。 CS327：............................................................................................................. 错误!未定义书签。 CS328：............................................................................................................. 错误!未定义书签。 CS329：............................................................................................................. 错误!未定义书签。
《算法与程序实践》习 题 解 答5——模拟
现实中的有些问题，难以找到公式或规律来解决，只能按照一定步骤，不停地做下去，最后才能得到答案。这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解决此问题的行为即可。这一类的问题可以称之为“模拟题”。比如下面经典的约瑟夫问题：
讲课：CS51 CS52 CS53 实验：CS56 CS516 CS517 讲课：CS59 CS513 CS518
CS51：约瑟夫问题
（来源：poj.grids.cn 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指向当前数
1
到的数组元素，相当于人的手指；划掉一个数的操作，就用将一个数组元素置0的方法来实现。人工数的时候，要跳过已经被划掉的数，那么程序执行的时候，就要跳过为0的数组元素。需要注意的是，当nPtr指向anLoop中最后一个元素（下标n-1）时，再数下一个，则nPtr要指回到数组的头一个元素（下标0），这样anLoop才象一个圈。
参考程序：
#include
#define MAX_NUM 300 int aLoop[MAX_NUM+1];
int main() { int n,m,i; while(1) { scanf(\ if(n==0) break; for(i=0;i 2 注意事项： 上面的程序完全模拟了人工操作的过程，但因为要反复跳过为0 的数组元素，因此算法的效率不是很高。后文的“链表”一章，采用单链表进行模拟来解决本题，就能省去跳过已出圈的猴子这个操作，大大提高了效率。 n 个元素的数组，从下标0 的元素开始存放猴子编号，则循环报数的时候，下一个猴子的下标就是“(当前猴子下标+ 1 )% n”。这种写法比用分支语句来决定下个猴子的下标是多少，更快捷而且写起来更方便。 对于本题，虽然很难直接找出结果函数 f(n, m)，但是如果仔细研究，找出局部的一些规律，比如，每次找下一个要出圈的猴子时，直接根据本次的起点位置就用公式算出下一个要出圈的猴子的位置，那么写出的程序就可以省去数m只猴子这个操作，大大提高效率，甚至不需要用数组来存放 n 个数。请写出这个高效而节省空间的程序。 问题一：在数组里循环计数的时候，一定要小心计算其开始的下标和终止的下标。比如，语句15，循环是从0到n-1，而不是从0 到n。 问题二：nPtr--到nPtr=n-1回退一个位置，易被忽略或写错。比如只写了语句nPtr--，忘了处理nPtr变成小于0的情况。 CS52：花生问题（同CS93） （来源：poj.grids.cn 2950，程序设计导引及在线实践（李文新）例4.3 P107） 问题描述： 鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。 鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图5-1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 我们假定多多在每个单位时间内，可以做下列四件事情中的一件： 1) 从路边跳到最靠近路边（即第一行）的某棵花生植株； 2) 从一棵植株跳到前后左右与之相邻的另一棵植株； 3) 采摘一棵植株下的花生； 4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。 3 图 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 解题思路： 试图找规律，得到一个以花生矩阵作为自变量的公式来解决这个问题，是不现实的。结果只能是做了才知道。即走进花生地，每次要采下一株花生之前，先计算一下，剩下的时间，够不够走到那株花生，采摘，并从那株花生走回到路上。如果时间够，则走过去采摘；如果时间不够，则采摘活动到此结束。 4
算法与程序实践习题解答5(模拟)
