第29课 汉诺塔

了解了递归的概念之后，本章我们来完成一个经典的递归算法问题—汉诺塔。

汉诺塔（又称河内塔）问题源于印度一个古老的神话传说，如图29-1所示。大梵天创造世界时做了3根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命人把圆盘从下面开始按大小顺序重新摆放在另一根柱子上，并且规定，在小圆盘上不能放大圆盘，在3根柱子之间一次只能移动一个圆盘。当所有的圆盘都从一根石柱上移到另外一根石柱上时，世界就将在一声霹雳中消灭。

图29-1 汉诺塔模型

那么移动这些圆盘需要多少时间呢？这个我们之后再计算，现在先来看看如何用算法完成汉诺塔上圆盘的移动。

汉诺塔用到了五大常用算法之一的分治法。在计算机科学中，分治法是一种很重要的算法，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。下面我们就在Scratch中来完成汉诺塔这个游戏。先来创建3个列表，如图29-2所示。

创建一个程序来给“list1”添加“圆盘”，这个程序是通过空格键来触发的，内容如图29-3所示。