算法与程序实践习题解答5(模拟)doc.doc

目 录

CS51：约瑟夫问题............................................................................................................................1

CS52：花生问题（同 CS93）..........................................................................................................3

CS53：显示器（见 CS327）............................................................................................................6

CS54：排列......................................................................................................................................13

CS55：宇航员..................................................................................................................................16

CS56：数根......................................................................................................................................26

CS57：武林......................................................................................................................................27

CS514：扫雷游戏（Mine Sweeper）............................................................................................46

CS515：弹球游戏（Linear Pachinko）.........................................................................................50

CS516：分糖果的游戏（Candy Sharing Game）.........................................................................53

CS517：爬动的蠕虫(Climbing Worm)...........................................................................................55

CS518：遍历迷宫（Maze Traversal）...........................................................................................55

CS319：............................................................................................................................................58

《算法与程序实践》习 题 解 答 5——模拟

现实中的有些问题，难以找到公式或规律来解决，只能按照一定步骤，不停地做下去，

最后才能得到答案。这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解

决此问题的行为即可。这一类的问题可以称之为“模拟题”。比如下面经典的约瑟夫问题：

讲课：CS51 CS52 CS53

实验：CS56 CS516 CS517

讲课：CS59 CS513 CS518

猴王的编号。

输入：

每行是用空格分开的两个整数，第一个是 n，第二个是 m ( 0 < m, n < 300) 。最后一行

是：

0 0

输出：

对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号。

样例输入：

6 2

12 4

解题思路：

初一看，很可能想把这道题目当作数学题来做，即认为结果也许会是以 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

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 个猴子

{

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”。这种写法比用分支语句来决定下个猴子的下标是

多少，更快捷而且写起来更方便。

问题二：nPtr--到 nPtr=n-1 回退一个位置，易被忽略或写错。比如只写了语句 nPtr--，

忘了处理 nPtr 变成小于 0 的情况。

CS52：花生问题（同 CS93）

问题描述：

鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发

现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。

鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有

一块花生田，花生植株整齐地排列成矩形网格（如图 5-1）。有经验的多多一眼就能看出，

每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多

的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此

类推，不过你一定要在我限定的时间内回到路边。”

我们假定多多在每个单位时间内，可以做下列四件事情中的一件：

1) 从路边跳到最靠近路边（即第一行）的某棵花生植株；

现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多

少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。

例如在图 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 ）个单位时间。接下来的

500） 表示花生田里植株(i, j)下花生的数目，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

解题思路：

试图找规律，得到一个以花生矩阵作为自变量的公式来解决这个问题，是不现实的。

结果只能是做了才知道。即走进花生地，每次要采下一株花生之前，先计算一下，剩下的

时间，够不够走到那株花生，采摘，并从那株花生走回到路上。如果时间够，则走过去采