猴子分桃问题的Python求解方法

王德贵

1979年著名美籍物理学家李政道教授来华讲学时， 访问了中国科技大学，会见了少年班的部分同学（科大少年班的设立，就源自李政道1974年向毛泽东、周恩来的建议）。在会见时，给少年班同学出了一道题：有五只猴子，分一堆桃子，可是怎么也平分不了。于是大家同意先去睡觉，明天再说。夜里一只猴子偷偷起来，把一个桃子扔到山下后，正好可以分成五份，它就把自己的一份藏起来，又睡觉去了。第二只猴子爬起来也扔了一个桃子，刚好分成五份，也把自己那一份收起来了。第三、第四、第五只猴子都是这样，扔了一个也刚好可以分成五份，也把自己那一份收起来了。问一共有多少个桃子？这道题，小朋友们可能算不出来，如果我给增加一个条件，最后剩下1020个桃子，看谁能算出来？

这是个经典问题，也有很多求解方法，如纯数学分析方法和各种编程语言求解方法等，但不管用什么方法，我们都可以从两个角度来分析，一个是根据剩余数目来反推总桃子数目，另一个是从桃子总数顺序推出剩余数目。下面我们就通过这两个思路，利用Python来研究求解问题的过程和方法。

程序设计涉及的是中国电子学会等级考试四级内容。

设剩余为x个桃子，则第5个猴子来的时候看到的桃子数目为：x*5//4+1，第4个猴子未分时的数目为：（x*5//4+1）*5//4+1，……，这样我们就可以利用递推关系求出第1个猴子未分时的数目，即桃子的总数目（图1）。

这个思路也可以用递归法求解（图2）。

两种方法测试结果相同（图3）。

这是根据李政道教授说剩余1020个桃子，如果不知道剩余多少，是不是可以随意输入剩余多少个呢？我们先看程序和运行结果（图4）。

比如随意输入剩余个数是2000、1200，结果如下（图5）。

发现结果是错误的！桃子总数不能满足减1后能被5整除。为什么？

因为在运算的过程中，我们是直接取整商（//）运算，而实际上没有被整除，所以有些数值是不满足条件的。

因此每个猴子取走桃子后，剩余数目必须是4的倍数，而每个猴子在未分桃子之前，桃子数目减1后一定能被5整除。

修改程序，采用枚举法，将剩余数目在一定范围内枚举，并一一进行验证，满足条件的值才是问题的解（图6）。

自定義两个函数，Istao函数判断数值是否满足条件，tao函数是对满足条件的数值进行求解计算，并输出每个猴子未分之前的桃子数目。主函数是输入范围后，枚举出可满足条件的剩余数目，并输出（图7）。

范围大，满足条件的剩余数目就会增加。

我们并不知道桃子总数是多少，所以要设定一个范围n，从前面分析可知，这个范围应该不小于3121，否则无解。

根据前面分析，枚举桃子总数，要满足条件：减1后能被5整除。于是还需要先判断是否满足条件，再顺推到最后剩余桃子数目，程序与上类似，输入的范围为桃子总数目，关系式变为从总数开始计算。倒推是乘以5/4，那么从总数开始计算，就是丢掉1个后的4/5（图8）。

运行结果如下（图9）：

递归方法这里不再叙述，有兴趣的同学可以自己设计程序。

前面我们的分析都是假设有5只猴子，那么要是6只、7只，…n只猴子，在同样条件下，如何求解呢？

如果其他条件不变，只是猴子数目变化了，在前例中将5个猴子的条件修改为n个猴子。看下面程序（图10）。

运行结果如下（图11）。

上述情况中，如果范围输入小了，则会无解，所以可以加个语句，提示一下（图12）。

比如输入8，范围100000，则显示无解（图13）。

那么猴子多了，在多大范围内才有解呢？并不好判断！

换个角度，我们可以不管什么范围，只要没找到满足条件的解，就继续查找，就不用确定数据范围了。修改程序如下。

tao函数中，由于循环次数不确定，因而采用while循环。首先在p值增加的过程中，判断div函数返回值，如果为假，就将p加1，否则则输出p。

div函数是判断桃子数目减1是否能被n整除，即被n个猴子平分，不能平分返回“假”，否则返回“真”，即是满足条件的值（图14）。

再次输入8，则结果显示如下。由此可以看到，在100000范围内，确实无解。输入4，结果为253（图15）。

如果条件稍微变化一下，比如，第1个猴子发现分成5份，恰好少1个，于是他自己就拿走了少1个桃子的那份，回去睡觉了。后边的猴子都是这样，自己拿走了少一个桃子的那份，问，原来桃子最少有多少个？

这个问题的分析，就是每个猴子未分之前的桃子数目，加上1个，正好是5的倍数，而分完取走之后，一定是4的倍数。笔者给出一个从总数递推的程序（图16、图17）。

本文从简单方法入手，循序渐进地讲解了猴子分桃问题，需要说明的是，我们只是从Python解法入手，来分析简单的求解问题。其实在Python中还有很多方法，这里不一一介绍，有兴趣的老师和同学可以自行研究一下。

本文难免有不当之处，请各位同仁、朋友斧正。