1.1 自頂向下的程序設(shè)計

1.1.1 問題分解和自頂向下的程序設(shè)計方法

一個程序員最容易犯的錯誤就是先編寫子程序，然后編寫調(diào)用該子程序的父程序，最后再寫主程序。之所以會犯這種錯誤是因?yàn)樽映绦蛑魂P(guān)注局部問題，比較容易編寫和調(diào)試。在子程序都已經(jīng)編寫完畢甚至調(diào)試成功的情況下再寫主程序，會讓人覺得比較“踏實(shí)”。

可是這種自底向上的方法問題很多，例如過多地關(guān)注了細(xì)節(jié)而忽略了整體和全局。當(dāng)我們把注意力集中在子程序或者局部問題時，就有可能忽視了主程序或者整體的需求，以至于經(jīng)常寫著寫著就忘記了自己本來要干什么。

更重要的是，這是一種削足適履的方法。程序員過多地將關(guān)注點(diǎn)放在了如何根據(jù)現(xiàn)有的方法解決問題——讓腳去適應(yīng)鞋子，而不是根據(jù)問題找方法——根據(jù)腳的大小找到合適的鞋子。正確的程序設(shè)計方法應(yīng)該是根據(jù)主程序的需要來確定子程序的功能和界面。也就是說，先在主程序中確定子程序要干什么以及怎么與主程序交互，然后讓子程序去決定怎么干。

先把問題分解為若干個小問題，然后再把每個小問題分解為若干個更小的問題。以此類推，直到每個最小的問題能夠輕而易舉地解決為止。

這就是著名的分治法。表現(xiàn)在程序設(shè)計上，就應(yīng)該是先編寫主程序，接著編寫主程序要調(diào)用的子程序，再編寫這些子程序要調(diào)用的子程序，以此類推。這種方法稱為自頂向下的程序設(shè)計方法，又稱為先整體后局部的程序設(shè)計方法。

也就是說，我們要學(xué)會分解問題，學(xué)會從整體和全局看待問題。下面來看幾個例子。

1.1.2 五猴分桃問題

第一個問題就是五猴分桃問題。問題的描述是這樣的：

有5只猴子上山去摘桃，一直摘到天黑。它們把所有的桃子放在一起，約定第二天一早來分桃。

第二天早晨，來了1只猴子。它等了一會兒后心想：“不如我干脆把桃子分了吧。”于是它把桃子分成了5等份，分完后發(fā)現(xiàn)多了1個桃子。它想：“我這么辛苦把桃子分了，這多出的1個桃子理應(yīng)歸我！”于是它吃了這個桃子，然后帶上1等份桃子，走了。

過了一會兒，第二只猴子來了。它也等了一會兒。等得不耐煩之后也把桃子分成了5等份，也發(fā)現(xiàn)多了1個桃子。它同樣吃了那個桃子，然后帶走了1等份桃子。

后來，第三、第四、第五只猴子都是先5等分桃子，然后吃掉多出來的1個桃子，最后再帶走1等份桃子。

問最初一共有多少個桃子？

解決這個問題的基本思路是把問題分解。既然我們不知道桃子有多少個，那我們就從1個桃子開始考慮，如果這1個桃子能夠被5只猴子這樣分掉，那么桃子的總數(shù)就是1個，如果不能，那就把桃子的數(shù)目加1，變成2，然后再看這2個桃子是否能被5只猴子這樣分掉，如果能分，那么桃子總數(shù)就是2，否則就把桃子的數(shù)目再加1。以此類推，直到找到第一個能被5只猴子這樣分的數(shù)目為止。

至于如何判斷一個數(shù)目是否能被5只猴子這樣分掉，我們把它作為一個子問題留待子程序去解決。在主程序中我們先調(diào)用這個子程序，之后再去實(shí)現(xiàn)它。“先調(diào)用，后實(shí)現(xiàn)”是自頂向下程序設(shè)計方法的具體做法。

現(xiàn)在，我們打開PyCharm，新建一個工程，然后創(chuàng)建一個名為p01_01_monkeys.py的文件。在這個文件中，編寫以下主程序：

其中的distributable（）函數(shù)用來判斷peaches個桃子能否被monkeys只猴子分掉。由于我們采用自頂向下、先調(diào)用后實(shí)現(xiàn)的方法，先調(diào)用了這個函數(shù)，但是還沒有實(shí)現(xiàn)它，所以程序界面的distributable之下有紅色波浪線警告，這是正常的。

下面開始實(shí)現(xiàn)子程序distributable。實(shí)現(xiàn)子程序仍然采用自頂向下、先整體后局部的方法。要判斷peaches個桃子能否被5只猴子分掉，只需把問題分解為判斷桃子能否被1只猴子分掉，如果能則進(jìn)行下一次判斷。如果連續(xù)5次都能被分掉，則返回True；否則，只要有一次不能分掉，就返回False。

所以distributable（）函數(shù)體的整體是一個5次循環(huán)，循環(huán)內(nèi)判斷當(dāng)前桃子數(shù)能否被1只猴子分掉。如何判斷？先把桃子數(shù)減1（因?yàn)楹镒右缘?個桃子），然后看看剩余桃子數(shù)能否被5整除。若能整除，則留下4等份桃子；若不能整除，則返回False。于是，就有了以下對distributable（）函數(shù)的實(shí)現(xiàn)：

自頂向下的程序設(shè)計方法不僅符合問題分解的正確思路，而且還能夠幫助我們很容易地發(fā)現(xiàn)錯誤或者優(yōu)化程序。例如，我們可以很容易地證明桃子的總數(shù)肯定是5的倍數(shù)加1。既然如此，那么上述算法中的倒數(shù)第4行就沒有必要1個1個地加桃子了，可以5個5個地加。也就是說，可以將這一行代碼改為：

這樣可以把程序運(yùn)行的速度提高大約5倍。

同樣，由于程序設(shè)計思路正確，上述代碼可以輕而易舉地擴(kuò)展到6只甚至更多的猴子分桃問題上，只需把代碼最后一行的“5”改為“6”或相應(yīng)數(shù)字即可。

我們也可以采用逆向思維，也就是從第5只猴子開始考慮。它把桃子分成了5等份，拿走1等份剩下4等份。假設(shè)每等份里的桃子數(shù)是n（n＝1，2，3……），則它開始分桃之前的桃子總數(shù)就是5n+1。對第4只猴子來說，這個數(shù)一定要能被4整除。如果不能整除，則那個n就不對；否則，把桃子總數(shù)除以4乘以5再加1。重復(fù)上述過程，直到第一只猴子為止。由此得到的代碼如下：

上述代碼中，unit_ peaches表示第5只猴子分桃后每等份里的桃子數(shù)。這個數(shù)每增加1，相當(dāng)于桃子最終的總數(shù)增加了很多，所以上述逆向思維的代碼大大減少了最底層循環(huán)［即子程序get_ peaches（）中的循環(huán)］被調(diào)用的次數(shù)，僅為594次。而正向思維下內(nèi)層循環(huán)被調(diào)用了1405次，后者是前者的約2.4倍。

1.1.3 猜姓氏問題

那還是我當(dāng)學(xué)生的時候，有一天路過學(xué)校附近的馬路，看到一個算命老者在高聲招攬生意。老者說他是一個神算子，可測事業(yè)、姻緣、前途、禍福、能生幾個娃，無一不準(zhǔn)。有好事者不信。只見老者拿出7張紙來，每張紙上密密麻麻地寫滿了各種姓氏（例如趙錢孫李什么的）。他說只要告訴他姓在哪幾張紙上出現(xiàn)過，他就能猜出來姓什么。有好事者上前實(shí)驗(yàn)，告訴老者自己的姓在哪幾張紙上出現(xiàn)過，老者立刻報出他的姓氏。現(xiàn)在問題來了：你能想出老者是怎么做到的嗎？當(dāng)然，雖然算命是一種迷信，但猜姓氏他的確沒有作弊。

秘密就在那7張紙上，因?yàn)槟惚仨毷紫雀嬖V人家你的姓出現(xiàn)在哪幾張紙上。那么這7張紙的排列組合可以表示多少姓氏？這不難計算，答案是2⁷－1，即127個姓氏。所以把百家姓中的每個姓用7位的二進(jìn)制進(jìn)行編碼，然后根據(jù)0或1決定相應(yīng)的姓氏是否要寫到對應(yīng)的紙上即可。表1－1為百家姓中前8個姓的編碼。

如果表1－1中某個單元的值是1，則其橫向?qū)?yīng)的姓氏就應(yīng)該寫到縱向?qū)?yīng)的紙上。例如，第一張紙（Page1）上就應(yīng)該寫“趙”“孫”“周”“鄭”。“吳”就應(yīng)該寫到第二張（Page2）和第三張（Page3）紙上。

現(xiàn)在你也可以猜姓氏了。例如有人告訴你說他的姓氏只出現(xiàn)在第一張和第三張紙上，這意味著他的姓氏的編碼是0000101，即第五個姓，所以他姓周。該問題的主程序如下：

主程序的主體是一個循環(huán)，用來顯示每一頁的姓氏。姓氏頁的列表是通過調(diào)用函數(shù)get_name_pages（）獲得的。我們只需直接調(diào)用這個函數(shù)即可，先不用關(guān)心它是怎么實(shí)現(xiàn)的。先調(diào)用后實(shí)現(xiàn)是自頂向下程序設(shè)計的一個特征。同樣，我們直接調(diào)用get_name（）函數(shù)以獲得用戶的姓氏，先不關(guān)心它的實(shí)現(xiàn)。

下面，我們來實(shí)現(xiàn)get_name_pages（）函數(shù)：

姓氏都放在字符串常數(shù)NAMES中。通過對姓氏的個數(shù)取對數(shù)的方法獲得總頁數(shù)。例如，100個姓氏就需要7張紙，15個姓氏就需要4張紙。接著，程序用空字符串（″）初始化了所有的姓氏頁，然后在一個for循環(huán)中通過insert_name（）函數(shù)把所有姓氏插入到姓氏頁列表result中。我們不關(guān)心insert_name（）是怎么實(shí)現(xiàn)的，只需知道它能達(dá)到什么目的即可。

接下來就是實(shí)現(xiàn)insert_name（）函數(shù)。這是一個把姓氏的id從十進(jìn)制轉(zhuǎn)為二進(jìn)制的過程。方法是求id模2的值，然后把id整除以2，這個過程不斷重復(fù)即可。如果id的二進(jìn)制的某一位是1，就把姓名插入到相應(yīng)的頁（page_id）中。

然后，再實(shí)現(xiàn)get_name（）函數(shù)。這是一個二進(jìn)制轉(zhuǎn)為十進(jìn)制的過程，方法是采用連乘法。例如，1011的十進(jìn)制就是（（1×2+0）×2+1）×2+1，其中加粗的數(shù)字就是二進(jìn)制的每一位編碼。采用這個方法，程序會比較簡單，代碼如下：

最后把所有程序放在一起，代碼如下：

程序運(yùn)行的結(jié)果如下：

趙 孫 周 鄭 馮 褚 蔣 韓

你猜的姓在這一行中嗎？（y，n，yes，no）y

錢 孫 吳 鄭 陳 褚 沈 韓

你猜的姓在這一行中嗎？（y，n，yes，no）n

李 周 吳 鄭 衛(wèi) 蔣 沈 韓

你猜的姓在這一行中嗎？（y，n，yes，no）y

王 馮 陳 褚 衛(wèi) 蔣 沈 韓

你猜的姓在這一行中嗎？（y，n，yes，no）y

你猜的姓是：蔣

另外，這個程序沒有考慮用戶的姓氏不在任何一頁上出現(xiàn)的情況。讀者可以把這個因素考慮進(jìn)去，然后稍微修改一下主程序，使用戶可以不斷玩下去而不必反復(fù)運(yùn)行程序。這樣，程序就比較完美了。

1.1.4 囚犯問題

如果說猜姓氏問題是用二進(jìn)制知識解決的，那么下面這個問題就要用到——一進(jìn)制。對，沒錯！一進(jìn)制！

一群囚犯即將被帶到牢房里坐牢。看守把他們集中在一起，宣布：

1）每個囚犯將被單獨(dú)關(guān)在一個牢房里。

2）每天會隨機(jī)地抽取一個囚犯放風(fēng)。

3）放風(fēng)的地方有一盞電燈，囚犯可以任意開關(guān)這盞電燈。

4）電燈永久有電，永遠(yuǎn)不會損壞。

5）囚犯在放風(fēng)的地方以及來回的路上都不會被其他囚犯看見。

6）牢房相互之間隔絕，囚犯相互之間不可能傳遞任何消息。

7）囚犯在放風(fēng)時，除了開關(guān)電燈不能留下任何痕跡或者信息。

8）看守只負(fù)責(zé)隨機(jī)抽取囚犯，不會幫助囚犯傳遞信息。

9）如果有人確定所有人都被放風(fēng)過，則可以通知看守，看守確認(rèn)之后可以把所有囚犯釋放；如果永遠(yuǎn)沒有人通知，或者通知的人弄錯了（并不是所有人都被放風(fēng)過），則所有人將永久坐牢，永無出頭之日。

10）囚犯們可以商議一個方法出來以避免永久坐牢，商議好之后就會被關(guān)進(jìn)各自的牢房。

問題：囚犯們會商議出什么方法？

這一題可以用一進(jìn)制來求解。什么是一進(jìn)制？遠(yuǎn)古時代人類的結(jié)繩記事就是一進(jìn)制。問有多少只羊？伸出3根手指，別人就知道了——你有3只羊。一進(jìn)制的麻煩就在于，如果你有100只羊，那么你就必須刻下100個點(diǎn)。刻下這么多點(diǎn)不但很麻煩，而且容易出錯（因?yàn)楸仨毎腰c(diǎn)和羊一一對應(yīng)）。所以即使是今天，地球上原始森林中那些只會用結(jié)繩記事的部落，對于超過10的數(shù)還一概以“很多”表示。

對于囚犯這一題，可以事先指定一個囚犯當(dāng)計數(shù)員。計數(shù)員是這樣工作的：當(dāng)他被選中出去放風(fēng)時，先看看那盞燈是不是亮的。如果是亮的，就把它關(guān)掉，然后在心里把計數(shù)加1。這個數(shù)用來記錄到目前為止有多少囚犯至少被放過一次風(fēng)，初值是1。一旦這個數(shù)等于囚犯總數(shù)，則意味著所有囚犯都至少被放過一次風(fēng)，問題就能解決。如果燈是滅的，就什么也不做。

其他囚犯怎么做呢？如果他是第一次出來放風(fēng)，或者雖然不是第一次出來放風(fēng)但是他以前出來時從來沒有碰過燈開關(guān)，那么他要看看那盞燈亮不亮。如果是滅的，就把它打開；如果是亮的，則不管它，就當(dāng)什么事也沒發(fā)生。

如果這個囚犯不是第一次出來放風(fēng)，并且以前他打開過電燈，則即使燈是滅的也不要打開它。為什么呢？因?yàn)榇蜷_燈其實(shí)是為了通知計數(shù)員：我出來放風(fēng)了，給我計個數(shù)吧。所以一旦他打開電燈，則他早晚會被計數(shù)員計數(shù)。即使他以后再次被放風(fēng)，也不用碰電燈開關(guān)了，以避免誤導(dǎo)計數(shù)員。

所以打開和關(guān)閉電燈就好比在繩子上打一個結(jié)，計數(shù)員的職責(zé)就是數(shù)這個結(jié)有多少個。這樣用一進(jìn)制解決問題的方法很有趣吧？下面我們用程序來求解這個問題，代碼如下：

所以，數(shù)的進(jìn)制并不是僅僅在計數(shù)時有用，在其他場景下也能發(fā)揮重要作用。其他計算機(jī)理論和數(shù)學(xué)知識也是如此。我們將在后面的章節(jié)中用更多的例子來說明這一點(diǎn)。

1.1.5 撲克牌問題

有一副只有點(diǎn)數(shù)沒有花色的撲克牌，點(diǎn)數(shù)分別是1，2，3，…，20，一共20張。我們把所有牌正面朝下堆成一疊放在手上，然后用另一只手翻開第一張，發(fā)現(xiàn)是1點(diǎn)。把這張1點(diǎn)牌放在一邊，然后摸下一張牌。這時我們并不看它的點(diǎn)數(shù)，而是把它放在這疊牌的末尾，使之成為最后一張牌。接著，翻開下一張牌，發(fā)現(xiàn)是2點(diǎn)。把這張2點(diǎn)牌也放在一邊，然后按順序摸兩張牌，不看點(diǎn)數(shù)，而是把它們放在這疊牌的末尾。注意，把它們一起放在末尾和把它們一張一張按順序放在末尾的結(jié)果是一樣的。再翻開下一張牌，發(fā)現(xiàn)是3點(diǎn)。這張3點(diǎn)牌也放在一邊，再一張一張地摸3張牌，并按順序放在末尾。以此類推，直到把所有牌都翻開并放在一邊。檢查被翻開的牌的點(diǎn)數(shù)，發(fā)現(xiàn)其順序分別是1，2，3，…， 20。問：最初牌的順序是什么？

解決這個問題的思路仍然是自頂向下，先整體后局部。如果采用逆向思維，我們可以先準(zhǔn)備一疊牌。一開始這疊牌里一張撲克牌都沒有，然后把20點(diǎn)牌插入這疊牌中去，怎么插入的，我們不關(guān)心，待會只需要設(shè)計一個子程序來完成這個插入操作即可。然后按順序把19點(diǎn)牌，18點(diǎn)牌，…，2點(diǎn)牌，1點(diǎn)牌插入到這疊牌中。所以，主程序是這樣的：

其中的_insert（）函數(shù)就是用來把撲克牌插入到列表中去的。接下來，我們來實(shí)現(xiàn)這個子程序。假設(shè)這張被插入的牌的點(diǎn)數(shù)是k。在正向思維下，它被翻開拿到一邊之后我們又摸了k張牌，并放到了這疊牌的底下。現(xiàn)在用逆向思維，在把這張牌插入到列表中去之前，應(yīng)該從這疊牌的底下一張一張地抽出k張牌，并按順序放在這疊牌的頂端。我們用子程序_move_last_to_top（）來實(shí)現(xiàn)這個功能。現(xiàn)在在_insert（）的函數(shù)體中，我們只管調(diào)用它，哪怕它還沒有實(shí)現(xiàn)，代碼如下：

最后我們再實(shí)現(xiàn)_move_last_to_top（）函數(shù)。很簡單，只需從列表中刪除最后一個元素，然后把它插入到頂端即可。

至此我們就解決了這個問題。其中的關(guān)鍵在于：把一個困難的、大的問題分解為若干小問題，再把每個小問題分解為更小的問題，直到每個最小的問題可以很容易解決為止。