师：同学们好，上节课大家学习了用递归算法解决斐波那契兔子问题，今天我们来学习用递归算法解决其他问题。
大家看屏幕上这个装置，可能有的同学小时候玩过，这是汉诺塔，又称河内塔，源于印度古老传说的益智游戏。我们通过一段视频了解下这个游戏怎么玩。
汉诺塔问题是心理学实验研究常用任务之一。主要材料有三根高度相同的柱子和一些大小及颜色不同的圆盘，三根柱子分别为起始柱a、辅助柱b及目标柱c。操作规则是每次只能移动一个圆盘，且移动过程中三根柱上始终保持大盘在下、小盘在上，移动时盘子可置于a、b、c任意柱上。汉诺塔问题是用递归方法求解的典型问题。
下面我们分析这个游戏的基本规则：第一，必须将起始柱上所有圆盘移至目标柱；第二，每次只能在三个柱子间移动一块圆盘；第三，移动时小盘必须在大盘上面。
现在我们来完成任务，把a柱上所有圆盘按规则移到c柱。若圆盘数量多，问题会复杂，我们分步操作。
先分析圆盘数量为1时的情况，很简单，直接把起始柱上的圆盘移到c柱。
当圆盘数量为2时，就复杂些。我们需借助辅助柱，先把起始柱上的小盘子移到辅助柱，移动步骤是a到b，然后将起始柱上的大盘子移到目标柱，步骤是a至c。这时会发现，起始柱上只剩一个盘子，和圆盘数量为1时情况类似，我们可把b柱看作起始柱，a柱看作辅助柱，直接把b柱上的圆盘移到目标柱。
当圆盘数量为3时，更复杂。先按前面方法，把两个盘子移到b柱，这和圆盘数量为2时的操作一样。第四步把a柱最下面的一个盘子移到c柱，此时b柱上有两个圆盘，和之前起始柱上有两个圆盘情况相同，我们交换起始柱和辅助柱位置，b柱变成起始柱。移动方法是先把上面的圆盘移到辅助柱，再把起始柱圆盘放到目标柱，最后把辅助柱圆盘移到目标柱，一共经过7步完成。同学们在这个过程中发现什么规律了吗？大家思考一下。
下面总结一下发现的规律：一、当圆盘数量为1时，可直接将圆盘从a柱移到c柱；二、当圆盘数量大于1时，需借助辅助柱才能将下面的圆盘移到目标柱；三、当起始柱上圆盘个数为奇数时，最上面的圆盘移动到目标柱；若为偶数，则移到辅助柱，各柱子角色不断变化；四、若要将起始柱最下面的圆盘移到目标柱，必须先把起始柱除最底下圆盘外的所有圆盘移到辅助柱，再把最下面圆盘移到目标柱。
以有五个圆盘放在a柱为例，把最下面标号为一号盘，上面所有盘子看作一个整体。若想把1号盘移到c柱，必须先把1号盘上面所有盘子移到b柱，再移1号盘到c柱。1号盘上面的圆盘整体不能一次性移动，要进行分解，通过把问题分解成规模缩小的同类子问题，按此方法，把最下面圆盘移出来，剩下部分不断分解，最终会得到只剩一个盘子，就可轻易移到目标盘，这是经典的递归过程。下面我们设计算法解决这个问题。
我们先定义一个函数，功能是把n个盘子从a柱经过b柱移到c柱，即从a到c。首先要对盘数n进行判断。
若盘数n为1，直接把a柱上圆盘移到c柱。否则，说明圆盘数量大于1，需借助辅助盘。先把a柱上除最底下圆盘外的其他盘子移到b柱，再把a柱最底下圆盘移到c柱，最后把b柱上圆盘移到c柱。这里a移到b和b移到c可能涉及多个盘子，不是一个盘子，所以需要用递归过程。对这两行语句转换时，第一个参数要递减，把a柱上圆盘移到c柱，同理，把b柱上圆盘移到c柱，也要先把盘数递减，通过这样实现递归过程。
下面看算法完整过程：定义一个过程叫“汉诺”，有四个变量n、a、b、c，n代表盘数，a、b、c分别代表三个柱子。接着进行判断，如果n等于1，输出显示移动圆盘的步骤从a到c；否则，关键语句是调用“汉诺”函数，把n参数减一，并且调换c和b参数位置。调用完后，再输出移动圆盘步骤从a到c。然后还要调用函数，把b上圆盘移到c上，结束判断，结束过程，这就是完整的递归算法。
下面通过VB程序实现，分两步，先设计界面，再编写代码。界面有几个关键控件，添加一个下拉列表框，用于设置圆盘数量；一个按钮触发事件；一个列表框，用于存储圆盘移动步骤；一个文本框，用于累计移动次数；还有三个标签。代码有三段，即三个过程。第一个是窗体加载事件，用于初始化下拉列表框数值；第二段是按钮事件，用于触发递归过程，注意按钮里还有两行，一行用于清除列表框内容，一行把移动步骤放到文本框显示；最下面是最重要的递归过程，和刚才算法基本一样。首先判断n是否等于1，如果等于1，在列表框添加一个步骤“从a移到c”，否则调用函数，参数减一，即n减一，还要调换c和b位置，以此类推。