汉诺塔问题
【例1】汉诺塔问题描述：
古代有一个梵塔，塔内有3个基座A、B、C，开始时A基座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A座移到B座，但每次只允许移动一个盘子，且在移动过程中在3个基座上的盘子都始终保持大盘在下，小盘在上。在移动过程中可以利用C基座做辅助。请编程打印出移动过程 。
算法设计：
用归纳法解此题，约定盘子自上而下的编号为1，2，3，……，n。
首先看一下2阶汉诺塔问题的解，不难理解以下移动过程：
初始状态为 A（1,2） B（） C（）
第一步后 A（2） B（） C（1）
第二步后 A（） B（2） C（1）
第三步后 A（） B（1,2） C（）
如何找出大规模问题与小规模问题的关系，从而实现递归呢？
把n个盘子抽象地看作“两个盘子”，上面“一个”由1——n-1号组成，下面“一个”就是n号盘子。移动过程如下：
第一步：先把上面“一个”盘子以a基座为起点借助b基座移到c基座。
第二步：把下面“一个”盘子从a基座移到b基座。
第三步：再把c基座上的n-1盘子借助a基座移到b基座。
把n阶的汉诺塔问题的模块记作hanoi(n,a,b,c)
a代表每一次移动的起始基座，
b代表每一次移动的终点基座，
c代表每一次移动的辅助基座
则汉诺塔问题hanoi(n,a,b,c)等价于以下三步：
第一步，hanoi(n-1,a,c,b)；
第二步，把下面“一个”盘子从a基座移到b基座；
第三步， hanoi(n-1,c,b,a)。
算法如下：
hanoi (int n,char a,char b,char c)
1) if(n>0) /*0阶的汉诺塔问题当作停止条件*/
2) hanoi(n-1,a,c,b);
3) 输出 “ Move dise” ,n.”from pile”,a,” to”b);
4) haboi(n-1,c,b,a);
5) endif
}
总结：
通上面的例子可以看出，递归的思路就是将一个负责的数学模型化为较小的数学模型，找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。，然后找出停止条件，即算法可解的最小规模问题。
