程序设计方法选
张铭版权所有 北京大学计算机系
程序设计方法选
程序设计方法选程序设计方法选
程序设计方法选
摘选自"从标准 Pascal 到 Delphi 4.0 —— 计算引论和程序设计基
础"，张铭，黄维通，北京大学出版社， 1999 年１月。
一、穷举法
例：猴子分桃子
有一堆桃子和甲、乙两组猴子，甲组有 3 只猴子，乙组有 5 只。甲组先看到桃子，第一
只猴子把桃子均分成 3 堆，结果剩下 2 个，它吃了这两个，又拿了一堆便走了。第二、第三
只猴子亦照样办理。甲组走后，乙组又看到了桃子，第一只猴子把桃子均分成 5 堆，结果剩
下 1 个，它吃了这一个，又拿了一堆便走了。第二、第三、第四、第五只猴子亦照样办理。
8 只猴子分别来过之后，至少还剩多少个桃子？原来至少有多少个桃子？
分析：最容易想到的是穷举法，桃子的数目一个个地增加，直到猴子能按条件取桃子时
为止。但这样简单的穷举效率太低，我们应该尽量利用已知条件，减少穷举的计算次数。设
原来至少有 total 个桃子，最后还剩 rest 个桃子。我们穷举的模拟方向可以是变化 total，直
到满足条件为止；也可以变化 rest，直到满足条件。 由于 rest << total，采用 rest 作为模拟的
变量效率一定更高。所以可以用“倒退法”，从数据的最后形式出发，反方向模拟。再者由
于最后还剩 4 堆桃子，也就是最后剩余桃子的数目是 4 的倍数，rest 的变化步长可以是 4 的
倍数，这样数据模拟的速度提高了许多。由于最后的计算结果是 rest=8188，total=84371，
超出了标准 Pascal 的整数范围，所以把它们定义为实型。
我们按拿桃子的顺序把猴子分为第一只到第八只。最后剩 rest 个，而 rest 可以均匀分为
4 堆，每堆有 rest/4 个桃子，这个猴子已吃过一堆和另外的一个，所以轮到第八只猴子拿桃
子时，共有 5*(rest/4)+1 个，即 rest*5/4+1 个桃子。可利用变量 total 存放该值，total=rest*5/4+1。
并把 total 的初值设为 rest，则上式改为 total=total*5/4+1。 这其实是 “迭代法” 的算法技巧。
轮到第七只、第六只、第五只、第四只猴子拿桃子时，分别在前述的 total 计算基础上共有
total=total*5/4+1 个桃子。而轮到第三只、第二只、第一只猴子拿桃子时，分别在前述的 total
计算基础上共有 total=total*3/2+1 个桃子。最后计算出的 total 结果即为所求解。值得注意的
是，在八次迭代计算 total 时，如果结果不是整数，则要抛弃，可以用条件“total <> Trunc(total)”
来判断。(此处也可以用“total <> Round(total)”来判断 total 是否是整数值。)
算法是一个二重循环，外层循环变量为 rest，按步长 4 递增变化，内层是对取桃子的猴
子序数 seq 从 8 至 1 循环，每一步迭代计算 total 值，直至 total 不合法(非整数)。外层循环
直至找到合法的 total 为止。
PROGRAM Peach(Input, Output);
VAR total, rest : REAL;
seq : INTEGER;
BEGIN
rest := 0;
REPEAT
