1.1 自顶向下的程序设计
1.1.1 问题分解和自顶向下的程序设计方法
一个程序员最容易犯的错误就是先编写子程序，然后编写调用该子程序的父程序，最后再写主程序。之所以会犯这种错误是因为子程序只关注局部问题，比较容易编写和调试。在子程序都已经编写完毕甚至调试成功的情况下再写主程序，会让人觉得比较“踏实”。
可是这种自底向上的方法问题很多，例如过多地关注了细节而忽略了整体和全局。当我们把注意力集中在子程序或者局部问题时，就有可能忽视了主程序或者整体的需求，以至于经常写着写着就忘记了自己本来要干什么。
更重要的是，这是一种削足适履的方法。程序员过多地将关注点放在了如何根据现有的方法解决问题——让脚去适应鞋子，而不是根据问题找方法——根据脚的大小找到合适的鞋子。正确的程序设计方法应该是根据主程序的需要来确定子程序的功能和界面。也就是说，先在主程序中确定子程序要干什么以及怎么与主程序交互，然后让子程序去决定怎么干。
先把问题分解为若干个小问题，然后再把每个小问题分解为若干个更小的问题。以此类推，直到每个最小的问题能够轻而易举地解决为止。
这就是著名的分治法。表现在程序设计上，就应该是先编写主程序，接着编写主程序要调用的子程序，再编写这些子程序要调用的子程序，以此类推。这种方法称为自顶向下的程序设计方法，又称为先整体后局部的程序设计方法。
也就是说，我们要学会分解问题，学会从整体和全局看待问题。下面来看几个例子。
1.1.2 五猴分桃问题
第一个问题就是五猴分桃问题。问题的描述是这样的：
有5只猴子上山去摘桃，一直摘到天黑。它们把所有的桃子放在一起，约定第二天一早来分桃。
第二天早晨，来了1只猴子。它等了一会儿后心想：“不如我干脆把桃子分了吧。”于是它把桃子分成了5等份，分完后发现多了1个桃子。它想：“我这么辛苦把桃子分了，这多出的1个桃子理应归我！”于是它吃了这个桃子，然后带上1等份桃子，走了。
过了一会儿，第二只猴子来了。它也等了一会儿。等得不耐烦之后也把桃子分成了5等份，也发现多了1个桃子。它同样吃了那个桃子，然后带走了1等份桃子。
后来，第三、第四、第五只猴子都是先5等分桃子，然后吃掉多出来的1个桃子，最后再带走1等份桃子。
问最初一共有多少个桃子？
解决这个问题的基本思路是把问题分解。既然我们不知道桃子有多少个，那我们就从1个桃子开始考虑，如果这1个桃子能够被5只猴子这样分掉，那么桃子的总数就是1个，如果不能，那就把桃子的数目加1，变成2，然后再看这2个桃子是否能被5只猴子这样分掉，如果能分，那么桃子总数就是2，否则就把桃子的数目再加1。以此类推，直到找到第一个能被5只猴子这样分的数目为止。
至于如何判断一个数目是否能被5只猴子这样分掉，我们把它作为一个子问题留待子程序去解决。在主程序中我们先调用这个子程序，之后再去实现它。“先调用，后实现”是自顶向下程序设计方法的具体做法。
现在，我们打开PyCharm，新建一个工程，然后创建一个名为p01_01_monkeys.py的文件。在这个文件中，编写以下主程序：
其中的distributable（）函数用来判断peaches个桃子能否被monkeys只猴子分掉。由于我们采用自顶向下、先调用后实现的方法，先调用了这个函数，但是还没有实现它，所以程序界面的distributable之下有红色波浪线警告，这是正常的。
下面开始实现子程序distributable。实现子程序仍然采用自顶向下、先整体后局部的方法。要判断peaches个桃子能否被5只猴子分掉，只需把问题分解为判断桃子能否被1只猴子分掉，如果能则进行下一次判断。如果连续5次都能被分掉，则返回True；否则，只要有一次不能分掉，就返回False。
所以distributable（）函数体的整体是一个5次循环，循环内判断当前桃子数能否被1只猴子分掉。如何判断？先把桃子数减1（因为猴子要吃掉1个桃子），然后看看剩余桃子数能否被5整除。若能整除，则留下4等份桃子；若不能整除，则返回False。于是，就有了以下对distributable（）函数的实现：
自顶向下的程序设计方法不仅符合问题分解的正确思路，而且还能够帮助我们很容易地发现错误或者优化程序。例如，我们可以很容易地证明桃子的总数肯定是5的倍数加1。既然如此，那么上述算法中的倒数第4行就没有必要1个1个地加桃子了，可以5个5个地加。也就是说，可以将这一行代码改为：
这样可以把程序运行的速度提高大约5倍。
同样，由于程序设计思路正确，上述代码可以轻而易举地扩展到6只甚至更多的猴子分桃问题上，只需把代码最后一行的“5”改为“6”或相应数字即可。
我们也可以采用逆向思维，也就是从第5只猴子开始考虑。它把桃子分成了5等份，拿走1等份剩下4等份。假设每等份里的桃子数是n（n＝1，2，3……），则它开始分桃之前的桃子总数就是5n+1。对第4只猴子来说，这个数一定要能被4整除。如果不能整除，则那个n就不对；否则，把桃子总数除以4乘以5再加1。重复上述过程，直到第一只猴子为止。由此得到的代码如下：
上述代码中，unit_ peaches表示第5只猴子分桃后每等份里的桃子数。这个数每增加1，相当于桃子最终的总数增加了很多，所以上述逆向思维的代码大大减少了最底层循环［即子程序get_ peaches（）中的循环］被调用的次数，仅为594次。而正向思维下内层循环被调用了1405次，后者是前者的约2.4倍。
1.1.3 猜姓氏问题
那还是我当学生的时候，有一天路过学校附近的马路，看到一个算命老者在高声招揽生意。老者说他是一个神算子，可测事业、姻缘、前途、祸福、能生几个娃，无一不准。有好事者不信。只见老者拿出7张纸来，每张纸上密密麻麻地写满了各种姓氏（例如赵钱孙李什么的）。他说只要告诉他姓在哪几张纸上出现过，他就能猜出来姓什么。有好事者上前实验，告诉老者自己的姓在哪几张纸上出现过，老者立刻报出他的姓氏。现在问题来了：你能想出老者是怎么做到的吗？当然，虽然算命是一种迷信，但猜姓氏他的确没有作弊。
秘密就在那7张纸上，因为你必须首先告诉人家你的姓出现在哪几张纸上。那么这7张纸的排列组合可以表示多少姓氏？这不难计算，答案是27－1，即127个姓氏。所以把百家姓中的每个姓用7位的二进制进行编码，然后根据0或1决定相应的姓氏是否要写到对应的纸上即可。表1－1为百家姓中前8个姓的编码。
表1－1 姓氏的二进制编码及其所属纸张
如果表1－1中某个单元的值是1，则其横向对应的姓氏就应该写到纵向对应的纸上。例如，第一张纸（Page1）上就应该写“赵”“孙”“周”“郑”。“吴”就应该写到第二张（Page2）和第三张（Page3）纸上。
现在你也可以猜姓氏了。例如有人告诉你说他的姓氏只出现在第一张和第三张纸上，这意味着他的姓氏的编码是0000101，即第五个姓，所以他姓周。该问题的主程序如下：
主程序的主体是一个循环，用来显示每一页的姓氏。姓氏页的列表是通过调用函数get_name_pages（）获得的。我们只需直接调用这个函数即可，先不用关心它是怎么实现的。先调用后实现是自顶向下程序设计的一个特征。同样，我们直接调用get_name（）函数以获得用户的姓氏，先不关心它的实现。
下面，我们来实现get_name_pages（）函数：
姓氏都放在字符串常数NAMES中。通过对姓氏的个数取对数的方法获得总页数。例如，100个姓氏就需要7张纸，15个姓氏就需要4张纸。接着，程序用空字符串（″）初始化了所有的姓氏页，然后在一个for循环中通过insert_name（）函数把所有姓氏插入到姓氏页列表result中。我们不关心insert_name（）是怎么实现的，只需知道它能达到什么目的即可。
接下来就是实现insert_name（）函数。这是一个把姓氏的id从十进制转为二进制的过程。方法是求id模2的值，然后把id整除以2，这个过程不断重复即可。如果id的二进制的某一位是1，就把姓名插入到相应的页（page_id）中。
然后，再实现get_name（）函数。这是一个二进制转为十进制的过程，方法是采用连乘法。例如，1011的十进制就是（（1×2+0）×2+1）×2+1，其中加粗的数字就是二进制的每一位编码。采用这个方法，程序会比较简单，代码如下：
最后把所有程序放在一起，代码如下：
程序运行的结果如下：
赵 孙 周 郑 冯 褚 蒋 韩
你猜的姓在这一行中吗？（y，n，yes，no）y
钱 孙 吴 郑 陈 褚 沈 韩
你猜的姓在这一行中吗？（y，n，yes，no）n
李 周 吴 郑 卫 蒋 沈 韩
你猜的姓在这一行中吗？（y，n，yes，no）y
王 冯 陈 褚 卫 蒋 沈 韩
你猜的姓在这一行中吗？（y，n，yes，no）y
你猜的姓是：蒋
另外，这个程序没有考虑用户的姓氏不在任何一页上出现的情况。读者可以把这个因素考虑进去，然后稍微修改一下主程序，使用户可以不断玩下去而不必反复运行程序。这样，程序就比较完美了。
1.1.4 囚犯问题
如果说猜姓氏问题是用二进制知识解决的，那么下面这个问题就要用到——一进制。对，没错！一进制！
一群囚犯即将被带到牢房里坐牢。看守把他们集中在一起，宣布：
1）每个囚犯将被单独关在一个牢房里。
2）每天会随机地抽取一个囚犯放风。
3）放风的地方有一盏电灯，囚犯可以任意开关这盏电灯。
4）电灯永久有电，永远不会损坏。
5）囚犯在放风的地方以及来回的路上都不会被其他囚犯看见。
6）牢房相互之间隔绝，囚犯相互之间不可能传递任何消息。
7）囚犯在放风时，除了开关电灯不能留下任何痕迹或者信息。
8）看守只负责随机抽取囚犯，不会帮助囚犯传递信息。
9）如果有人确定所有人都被放风过，则可以通知看守，看守确认之后可以把所有囚犯释放；如果永远没有人通知，或者通知的人弄错了（并不是所有人都被放风过），则所有人将永久坐牢，永无出头之日。
10）囚犯们可以商议一个方法出来以避免永久坐牢，商议好之后就会被关进各自的牢房。
问题：囚犯们会商议出什么方法？
这一题可以用一进制来求解。什么是一进制？远古时代人类的结绳记事就是一进制。问有多少只羊？伸出3根手指，别人就知道了——你有3只羊。一进制的麻烦就在于，如果你有100只羊，那么你就必须刻下100个点。刻下这么多点不但很麻烦，而且容易出错（因为必须把点和羊一一对应）。所以即使是今天，地球上原始森林中那些只会用结绳记事的部落，对于超过10的数还一概以“很多”表示。
对于囚犯这一题，可以事先指定一个囚犯当计数员。计数员是这样工作的：当他被选中出去放风时，先看看那盏灯是不是亮的。如果是亮的，就把它关掉，然后在心里把计数加1。这个数用来记录到目前为止有多少囚犯至少被放过一次风，初值是1。一旦这个数等于囚犯总数，则意味着所有囚犯都至少被放过一次风，问题就能解决。如果灯是灭的，就什么也不做。
其他囚犯怎么做呢？如果他是第一次出来放风，或者虽然不是第一次出来放风但是他以前出来时从来没有碰过灯开关，那么他要看看那盏灯亮不亮。如果是灭的，就把它打开；如果是亮的，则不管它，就当什么事也没发生。
如果这个囚犯不是第一次出来放风，并且以前他打开过电灯，则即使灯是灭的也不要打开它。为什么呢？因为打开灯其实是为了通知计数员：我出来放风了，给我计个数吧。所以一旦他打开电灯，则他早晚会被计数员计数。即使他以后再次被放风，也不用碰电灯开关了，以避免误导计数员。
所以打开和关闭电灯就好比在绳子上打一个结，计数员的职责就是数这个结有多少个。这样用一进制解决问题的方法很有趣吧？下面我们用程序来求解这个问题，代码如下：
所以，数的进制并不是仅仅在计数时有用，在其他场景下也能发挥重要作用。其他计算机理论和数学知识也是如此。我们将在后面的章节中用更多的例子来说明这一点。
1.1.5 扑克牌问题
有一副只有点数没有花色的扑克牌，点数分别是1，2，3，…，20，一共20张。我们把所有牌正面朝下堆成一叠放在手上，然后用另一只手翻开第一张，发现是1点。把这张1点牌放在一边，然后摸下一张牌。这时我们并不看它的点数，而是把它放在这叠牌的末尾，使之成为最后一张牌。接着，翻开下一张牌，发现是2点。把这张2点牌也放在一边，然后按顺序摸两张牌，不看点数，而是把它们放在这叠牌的末尾。注意，把它们一起放在末尾和把它们一张一张按顺序放在末尾的结果是一样的。再翻开下一张牌，发现是3点。这张3点牌也放在一边，再一张一张地摸3张牌，并按顺序放在末尾。以此类推，直到把所有牌都翻开并放在一边。检查被翻开的牌的点数，发现其顺序分别是1，2，3，…， 20。问：最初牌的顺序是什么？
解决这个问题的思路仍然是自顶向下，先整体后局部。如果采用逆向思维，我们可以先准备一叠牌。一开始这叠牌里一张扑克牌都没有，然后把20点牌插入这叠牌中去，怎么插入的，我们不关心，待会只需要设计一个子程序来完成这个插入操作即可。然后按顺序把19点牌，18点牌，…，2点牌，1点牌插入到这叠牌中。所以，主程序是这样的：
其中的_insert（）函数就是用来把扑克牌插入到列表中去的。接下来，我们来实现这个子程序。假设这张被插入的牌的点数是k。在正向思维下，它被翻开拿到一边之后我们又摸了k张牌，并放到了这叠牌的底下。现在用逆向思维，在把这张牌插入到列表中去之前，应该从这叠牌的底下一张一张地抽出k张牌，并按顺序放在这叠牌的顶端。我们用子程序_move_last_to_top（）来实现这个功能。现在在_insert（）的函数体中，我们只管调用它，哪怕它还没有实现，代码如下：
最后我们再实现_move_last_to_top（）函数。很简单，只需从列表中删除最后一个元素，然后把它插入到顶端即可。
至此我们就解决了这个问题。其中的关键在于：把一个困难的、大的问题分解为若干小问题，再把每个小问题分解为更小的问题，直到每个最小的问题可以很容易解决为止。