Python-汉诺塔问题

先给大家更新一下消息，Mark学编程已经三位一体了，本微信公众号，QQ群，还有CSDN社区的博客。都开始运行，名字都叫“Mark学编程”，请关注，便于相互交流，尤其是QQ群，要逐渐将资料放到上面去。请大家主动关注另外两个，避免遗漏交流机会。

本次讨论，我们继续上一次开始的Python递归函数，解决著名的汉诺塔问题。汉诺塔的历史版本，大家可以网上搜，但简单版本我简要介绍如下：有三根柱子，我们分别叫 a， b， c， 排成一列，如下图：

上苍要求，如图，大的在下面，小的在上面的，放置在a柱上的64个盘子，移动到c柱上，移动后也是同样，大的总在下面，小的总在上面。移动过程中，可以使用，a, b, c任何一根柱子，一次只能移动一个盘子，每次移动后，都要保持大盘子在小盘子的下面。

抓紧开始吧，听说接受该项任务的老和尚小和尚们还在紧张的搬动着，已经搬动了几百年了，完成任务仍然遥遥无期。好在我们可以使用计算机模拟搬动，所以，还是有可能在本世纪末借助计算机完成的。

为了一次性成功建立移动模型，我们先复习上一次讲的两个递归函数，一个是阶乘，一个是斐波那契数。

阶乘，比如1的阶乘表示为 1！2的阶乘可以表示为 2*1！3的阶乘3*2！4的 4*3！5*4！ （enough！）n的可以表示为 n * (n-1)! , 抽象的模型就是他了， n! = n * (n-1)!; （n-1)! 其实又等于 (n-1)*(n-2)！每一个紧跟着的阶乘都可以用同一个结构表达，使用同一结构，这就是递归的本质。在编程中，就相当于使用同一个函数反复调用，当然，是在函数内部调用相同的函数。

我们知道 1！定义为等于 1；那么只要给你一个n, 根据 n * (n-1)! 展开后，总会到达1！，于是只要返回到1！= 1 的值，就会得出答案了。拿n=5计算阶乘为例，它就等于 5*4！而 4！又等于 4*3！很快就到了 1！= 1，整体结果就出来了。

由此可见，这里有两个重要的东西，一是能够计算出值的基准语句（我个人的语言，基准），而是能够抽象的模式（结构），并且这个模式贯穿整个计算过程，是同一种模式。再重复一下， n!= n * (n-1)! 和 （n-1)!= (n-1)*(n-2)! 是同一种模式。这就是递归，只不过我们是在函数的内部自己调用自己。

如果还看不懂，可能是没有看昨天的递归解释。请一定回看上一篇，要么在微信公众号，要么在QQ群，要么在CSDN博客上。

再看斐波那契数，先有两个基准，fib(0) = 0； fib(1) = 1; 然后，任何其他的斐波那契数都可以表达为 fib(n) = fib(n-1) + fib(n-2); 只要你给出n的值，比如5，那么fib(5) = fib(4)+fib(3)， 很快就会抵达 fib(1) 和 fib(0), 因为fib(0), fib(1) 的值已经在基准case中定义了，所以函数很快返回将 fib(5)的值求出来。因为fib(n), fib(n-1), fib(n-2) 都是同一个函数，并且在函数内部调用自己，所以属于递归函数。again， 有基准语句，基准case， 加上抽象出来的模式，是这个模式fib(n), 而fib(n-1)就是函数fib(n), 只是参数值不同吧了。

我们开始汉诺塔代码：

先分析，归纳或找出基准case，从上面两个例子看，都是最前面的1个或2个或更多的基准case，他们都是显而易见。那么汉诺塔是什么样的基准呢？当a柱只有1个盘子的时候，移动到c柱，直接移动过去。很简单是不是？当有两个盘子的时候呢，如何移动？我们直观看，把上面小的，先移动到b柱， 底下大盘子移动到c柱，然后将b柱的小盘子移动到c柱，大功告成。嗯，估计聪明的猴子也能做得到。

如果是三个呢？好像无从下手，那就说明，开始抽象，开始归纳的时候到了，估计猴子们已经败下阵来。人类是不是会抽象才从其他动物中脱颖而出的？不知道。反正抽象在这里起了巨大的作用。如何抽象，我们能不能把3个盘子和更多的盘子n，看成是两个盘子？一个大盘子在底层，另一个是（n-1在上面，把（n-1）个盘子看成一个盘子，然后按照两个盘子的移动方式来移动就行了。这就是解决这一难题的奥秘。把n个盘子看成两个盘子，然后按照两个盘子移动方式移动。

思路有了，写代码，最后不要看下面的代码，先安装文字说明，在纸上或电脑上写代码并运行测试：

函数格式是：

def hannoi(n, a, b, c): #hannoi英文汉诺塔，n 指n个盘子，a, b, c分别代表三个柱子，注意这个顺序，很重要。前几节我们并没有介绍参数的位置，函数定义的形式参数当被调用时，是以位置与实际参数绑定的，叫位置参数，当然，我们并没有讲解其他形式的参数，但要有参数位置的意识。

然后，写第一个基准case, 就是当只有1个盘子时，如何移动。

if n == 1:

print ( a, “–>”, c )

打印就相当于给出移动盘子的指令。注意，a 参数代表a 柱子，c 代表c 柱子。 中间 “–>” 字符串代表移动方向。

还有没有第二个基准case（还是说一下吧，有的同学对case可能没有感觉，书中翻译为案例，可能并不能让读者准确把握英文的真正含义，如果翻译成情形（情况），是不是更好，只少，你现在就这么理解）根据我们刚才已经抽象出来的模型，把两个和两个以上盘中抽象成两个，底下一个大的，上面一个小的，小的是第（n-1）个盘子，所以，没有第二个基准case了。

OK， 移动第二个盘子，第二个盘子移动的方向是从a 到 b柱（中间那个）。

上面是if，不是一个盘子时，就else

else：

print（n-1, a, c, b）

没有写错，刚才已经讲了位置参数，定义的时候是第二个参数移动到第4个参数上。所以，a 柱到 b 柱就这么写了。 c 也不能漏掉，因为这个函数定义时参数是4个。

接下来，就是最低层那个了，从 a 柱到 c 柱，语句是这样的：

print(1, a, b, c),

请注意，1 不要写成 n, 因为当上面的搬走了，剩下的就是1个大盘子，就相当于当一个盘子时，如何移动的问题了。

最后需要将b柱上的第（n-1）个盘子搬到 c 柱了，语句如下：

print(n-1, b, a, c)

有的同学一定是分郁闷，这么多盘子一次性搬，不符合规则呀。

这就是递归的妙处了。我们不用管，想想阶乘和斐波那契数，你计算（n-1)！和 fib(n-1)了吗？没有，所以，不用管（n-1）个盘子是如何移动的。其实，我们的模型是将n个盘子看成两个的，所以，代码自然将（n-1）看做第2个盘子了。

况且递归函数会在运行时，再把（n-1）个盘子看成两个盘子。也就是展开（n-1）个盘子的同样移动代码。

请看测试。看图，代码和结果。 我们仅仅测试了3个盘子情况，你可以做4个，5个，或更多，但超过10个一定要谨慎呀，因为，移动次数会惊人的增长。要知道，老和尚小和尚还在努力搬运呢。

如果遇到电脑不能停止，使用control-d, 或 c 键终止，再不行，关机。

还有，为了更清晰，我把 a, b, c 三根柱子换做了英文的第一根，第二根，第三根。这也又一次提醒我们 a, b, c 是形参，而 first, second, third 是实际参数。