猴子分桃問(wèn)題的Python求解方法

王德貴

1979年著名美籍物理學(xué)家李政道教授來(lái)華講學(xué)時(shí)， 訪問(wèn)了中國(guó)科技大學(xué)，會(huì)見了少年班的部分同學(xué)（科大少年班的設(shè)立，就源自李政道1974年向毛澤東、周恩來(lái)的建議）。在會(huì)見時(shí)，給少年班同學(xué)出了一道題：有五只猴子，分一堆桃子，可是怎么也平分不了。于是大家同意先去睡覺(jué)，明天再說(shuō)。夜里一只猴子偷偷起來(lái)，把一個(gè)桃子扔到山下后，正好可以分成五份，它就把自己的一份藏起來(lái)，又睡覺(jué)去了。第二只猴子爬起來(lái)也扔了一個(gè)桃子，剛好分成五份，也把自己那一份收起來(lái)了。第三、第四、第五只猴子都是這樣，扔了一個(gè)也剛好可以分成五份，也把自己那一份收起來(lái)了。問(wèn)一共有多少個(gè)桃子？這道題，小朋友們可能算不出來(lái)，如果我給增加一個(gè)條件，最后剩下1020個(gè)桃子，看誰(shuí)能算出來(lái)？

這是個(gè)經(jīng)典問(wèn)題，也有很多求解方法，如純數(shù)學(xué)分析方法和各種編程語(yǔ)言求解方法等，但不管用什么方法，我們都可以從兩個(gè)角度來(lái)分析，一個(gè)是根據(jù)剩余數(shù)目來(lái)反推總桃子數(shù)目，另一個(gè)是從桃子總數(shù)順序推出剩余數(shù)目。下面我們就通過(guò)這兩個(gè)思路，利用Python來(lái)研究求解問(wèn)題的過(guò)程和方法。

程序設(shè)計(jì)涉及的是中國(guó)電子學(xué)會(huì)等級(jí)考試四級(jí)內(nèi)容。

設(shè)剩余為x個(gè)桃子，則第5個(gè)猴子來(lái)的時(shí)候看到的桃子數(shù)目為：x*5//4+1，第4個(gè)猴子未分時(shí)的數(shù)目為：（x*5//4+1）*5//4+1，……，這樣我們就可以利用遞推關(guān)系求出第1個(gè)猴子未分時(shí)的數(shù)目，即桃子的總數(shù)目（圖1）。

這個(gè)思路也可以用遞歸法求解（圖2）。

兩種方法測(cè)試結(jié)果相同（圖3）。

這是根據(jù)李政道教授說(shuō)剩余1020個(gè)桃子，如果不知道剩余多少，是不是可以隨意輸入剩余多少個(gè)呢？我們先看程序和運(yùn)行結(jié)果（圖4）。

比如隨意輸入剩余個(gè)數(shù)是2000、1200，結(jié)果如下（圖5）。

發(fā)現(xiàn)結(jié)果是錯(cuò)誤的！桃子總數(shù)不能滿足減1后能被5整除。為什么？

因?yàn)樵谶\(yùn)算的過(guò)程中，我們是直接取整商（//）運(yùn)算，而實(shí)際上沒(méi)有被整除，所以有些數(shù)值是不滿足條件的。

因此每個(gè)猴子取走桃子后，剩余數(shù)目必須是4的倍數(shù)，而每個(gè)猴子在未分桃子之前，桃子數(shù)目減1后一定能被5整除。

修改程序，采用枚舉法，將剩余數(shù)目在一定范圍內(nèi)枚舉，并一一進(jìn)行驗(yàn)證，滿足條件的值才是問(wèn)題的解（圖6）。

自定義兩個(gè)函數(shù)，Istao函數(shù)判斷數(shù)值是否滿足條件，tao函數(shù)是對(duì)滿足條件的數(shù)值進(jìn)行求解計(jì)算，并輸出每個(gè)猴子未分之前的桃子數(shù)目。主函數(shù)是輸入范圍后，枚舉出可滿足條件的剩余數(shù)目，并輸出（圖7）。

范圍大，滿足條件的剩余數(shù)目就會(huì)增加。

我們并不知道桃子總數(shù)是多少，所以要設(shè)定一個(gè)范圍n，從前面分析可知，這個(gè)范圍應(yīng)該不小于3121，否則無(wú)解。

根據(jù)前面分析，枚舉桃子總數(shù)，要滿足條件：減1后能被5整除。于是還需要先判斷是否滿足條件，再順推到最后剩余桃子數(shù)目，程序與上類似，輸入的范圍為桃子總數(shù)目，關(guān)系式變?yōu)閺目倲?shù)開始計(jì)算。倒推是乘以5/4，那么從總數(shù)開始計(jì)算，就是丟掉1個(gè)后的4/5（圖8）。

運(yùn)行結(jié)果如下（圖9）：

遞歸方法這里不再敘述，有興趣的同學(xué)可以自己設(shè)計(jì)程序。

前面我們的分析都是假設(shè)有5只猴子，那么要是6只、7只，…n只猴子，在同樣條件下，如何求解呢？

如果其他條件不變，只是猴子數(shù)目變化了，在前例中將5個(gè)猴子的條件修改為n個(gè)猴子?？聪旅娉绦颍▓D10）。

運(yùn)行結(jié)果如下（圖11）。

上述情況中，如果范圍輸入小了，則會(huì)無(wú)解，所以可以加個(gè)語(yǔ)句，提示一下（圖12）。

比如輸入8，范圍100000，則顯示無(wú)解（圖13）。

那么猴子多了，在多大范圍內(nèi)才有解呢？并不好判斷！

換個(gè)角度，我們可以不管什么范圍，只要沒(méi)找到滿足條件的解，就繼續(xù)查找，就不用確定數(shù)據(jù)范圍了。修改程序如下。

tao函數(shù)中，由于循環(huán)次數(shù)不確定，因而采用while循環(huán)。首先在p值增加的過(guò)程中，判斷div函數(shù)返回值，如果為假，就將p加1，否則則輸出p。

div函數(shù)是判斷桃子數(shù)目減1是否能被n整除，即被n個(gè)猴子平分，不能平分返回“假”，否則返回“真”，即是滿足條件的值（圖14）。

再次輸入8，則結(jié)果顯示如下。由此可以看到，在100000范圍內(nèi)，確實(shí)無(wú)解。輸入4，結(jié)果為253（圖15）。

如果條件稍微變化一下，比如，第1個(gè)猴子發(fā)現(xiàn)分成5份，恰好少1個(gè)，于是他自己就拿走了少1個(gè)桃子的那份，回去睡覺(jué)了。后邊的猴子都是這樣，自己拿走了少一個(gè)桃子的那份，問(wèn)，原來(lái)桃子最少有多少個(gè)？

這個(gè)問(wèn)題的分析，就是每個(gè)猴子未分之前的桃子數(shù)目，加上1個(gè)，正好是5的倍數(shù)，而分完取走之后，一定是4的倍數(shù)。筆者給出一個(gè)從總數(shù)遞推的程序（圖16、圖17）。

本文從簡(jiǎn)單方法入手，循序漸進(jìn)地講解了猴子分桃問(wèn)題，需要說(shuō)明的是，我們只是從Python解法入手，來(lái)分析簡(jiǎn)單的求解問(wèn)題。其實(shí)在Python中還有很多方法，這里不一一介紹，有興趣的老師和同學(xué)可以自行研究一下。

本文難免有不當(dāng)之處，請(qǐng)各位同仁、朋友斧正。