例8.9 Hanoi(汉诺)塔问题。这是一个古典的数学
问题，是一个只有用递归方法(而不可能用其他方法)解决的问题。问题是这样的：古代有一个梵塔，塔内有3个座A、B、C，开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上(图7.13)。有一个老和尚想把这64个盘子从A座移到C座，但每次只允许移动一个盘，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求编程序打印出移动的步骤。
可以肯定地说：任何一个人(包括“天才”) 都不可能直接写出移动盘子的每一个具体步骤。请读者试验一下按上面的规律将5个盘子从A座移到C座，能否直接写出每一步骤?老和尚自然会这样想：假如有另外一个和尚能有办法将63个盘子从一个座移到另一座。那么，问题就解决了。此时老和尚只需这样做：
(1) 命令第2个和尚将63个盘子从A座移到B座；
(2) 自己将1个盘子(最底下的、最大的盘子)从A座移到C座；
(3) 再命令第2个和尚将63个盘子从B座移到C座。
至此，全部任务完成了。这就是递归方法。但是，有一个问题实际上未解决：第2个和尚怎样才能将63个盘子从A座移到B座?为了解决将63个盘子从A座移到B座，第2个和尚又想：如果有人能将62个盘子从一个座移到另一座，我就能将63个盘子从A座移到B座，他是这样做的：
(1) 命令第3个和尚将62个盘子从A座移到C座；
(2) 自己将1个盘子从A座移到B座；
(3) 再命令第3个和尚将62个盘子从C座移到B座。
再进行一次递归。如此“层层下放”,直到后来找到第63个和尚，让他完成将2个盘子从一个座移到另一座，进行到此，问题就接近解决了。最后找到第64个和尚，让他完成将1个盘子从一个座移到另一座，至此，全部工作都已落实，都是可以执行的。可以看出，递归的结束条件是最后一个和尚只需移一个盘子。否则递归还要继续进行下去。
应当说明，只有第64个和尚的任务完成后，第63个和尚的任务才能完成。只有第2到第64个和尚任务完成后，第1个和尚的任务才能完成。这是一个典型的递归的问题。为使问题简化，我们先分析将A座上3个盘子移到C座上的过程：
(1) 将A座上2个盘子移到B座上(借助C)；
(2) 将A座上1个盘子移到C座上；
(3) 将B座上2个盘子移到C座上(借助A)。
其中第2步可以直接实现。第1步又可用递归方法分解为：
1．1将A上1个盘子从A移到C；
1．2将A上1个盘子从A移到B；
1．3将C上1个盘子从C移到B。
第3步可以分解为：
3．1将B上1个盘子从B移到A上；
3．2将B上1个盘子从B移到C上；
3．3将A上1个盘子从A移到C上。
将以上综合起来，可得到移动3个盘子的步骤为
A→C，A→B，C→B，A→C，B→A，B→C，A→C。
共经历7步。由此可推出：移动n个盘子要经历2n-1步。如移4个盘子经历15步，移5个盘子经历31步，移64个盘子经历264-1步。
由上面的分析可知：将n个盘子从A座移到C座可以分解为以下3个步骤：
(1) 将A上n-1个盘借助C座先移到B座上。
(2) 把A座上剩下的一个盘移到C座上。
(3) 将n-1个盘从B座借助于A座移到C座上。
上面第1步和第3步，都是把n-1个盘从一个座移到另一个座上，采取的办法是一样的，只是座的名字不同而已。为使之一般化，可以将第1步和第3步表示为：
“将“one” 座上n-1个盘移到“two” 座(借助“three” 座)。只是在第①步和第③步中，one、two、three和A、B、C的对应关系不同。对第①步，对应关系是one——A，two——B，three——C。对第③步，是：one——B，two——C，three——A。
因此，可以把上面3个步骤分成两类操作：
(1) 将n-1个盘从一个座移到另一个座上(n>1)。这就是大和尚让小和尚做的工作，它是一个递归的过程，即和尚将任务层层下放，直到第64个和尚为止。
(2) 将1个盘子从一个座上移到另一座上。这是大和尚自己做的工作。
下面编写程序。分别用两个函数实现以上的两类操作，用hanoi函数实现上面第1类操作(即模拟小和尚的任务)，用move函数实现上面第2类操作(模拟大和尚自己移盘)，函数调用hanoi(n，one，two，three)表示“将n个盘子从“one” 座移到“three” 座的过程(借助“two”针”)。函数调用move(x，y)表示将1个盘子从x 座移到y 座的过程。x和y是代表A、B、C座之一，根据每次不同情况分别取A、B、C代入。
程序如下：
void move(char x，char y)
｛
printf("%c-->%c\n"，x，y)；
｝
void hanoi(int n，char one，char two，char three)
/*将n个盘从one座借助two座，移到three座/
｛
if(n＝＝1) move(one，three)；
else
｛
hanoi(n-1，one，three，two)；
move(one，three)；
hanoi(n-1，two，one，three)；
｝
｝
main()
｛
int m；
printf("input the number of diskes：")；
scanf("%d"，&m)；
printf("The step to moving %3d diskes：\n"，m)；
hanoi(m，′A′，′B′，′C′)；
｝
运行情况如下：
input the number of diskes：3
The step to moving 3 diskes：
A-->C
A-->B
C-->B
A-->C
B-->A
B-->C
A-->C
在本程序中move函数并未真正移动盘子，而只是打印出移盘的方案(从哪一个座移到哪一个座)。
问题，是一个只有用递归方法(而不可能用其他方法)解决的问题。问题是这样的：古代有一个梵塔，塔内有3个座A、B、C，开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上(图7.13)。有一个老和尚想把这64个盘子从A座移到C座，但每次只允许移动一个盘，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求编程序打印出移动的步骤。
可以肯定地说：任何一个人(包括“天才”) 都不可能直接写出移动盘子的每一个具体步骤。请读者试验一下按上面的规律将5个盘子从A座移到C座，能否直接写出每一步骤?老和尚自然会这样想：假如有另外一个和尚能有办法将63个盘子从一个座移到另一座。那么，问题就解决了。此时老和尚只需这样做：
(1) 命令第2个和尚将63个盘子从A座移到B座；
(2) 自己将1个盘子(最底下的、最大的盘子)从A座移到C座；
(3) 再命令第2个和尚将63个盘子从B座移到C座。
至此，全部任务完成了。这就是递归方法。但是，有一个问题实际上未解决：第2个和尚怎样才能将63个盘子从A座移到B座?为了解决将63个盘子从A座移到B座，第2个和尚又想：如果有人能将62个盘子从一个座移到另一座，我就能将63个盘子从A座移到B座，他是这样做的：
(1) 命令第3个和尚将62个盘子从A座移到C座；
(2) 自己将1个盘子从A座移到B座；
(3) 再命令第3个和尚将62个盘子从C座移到B座。
再进行一次递归。如此“层层下放”,直到后来找到第63个和尚，让他完成将2个盘子从一个座移到另一座，进行到此，问题就接近解决了。最后找到第64个和尚，让他完成将1个盘子从一个座移到另一座，至此，全部工作都已落实，都是可以执行的。可以看出，递归的结束条件是最后一个和尚只需移一个盘子。否则递归还要继续进行下去。
应当说明，只有第64个和尚的任务完成后，第63个和尚的任务才能完成。只有第2到第64个和尚任务完成后，第1个和尚的任务才能完成。这是一个典型的递归的问题。为使问题简化，我们先分析将A座上3个盘子移到C座上的过程：
(1) 将A座上2个盘子移到B座上(借助C)；
(2) 将A座上1个盘子移到C座上；
(3) 将B座上2个盘子移到C座上(借助A)。
其中第2步可以直接实现。第1步又可用递归方法分解为：
1．1将A上1个盘子从A移到C；
1．2将A上1个盘子从A移到B；
1．3将C上1个盘子从C移到B。
第3步可以分解为：
3．1将B上1个盘子从B移到A上；
3．2将B上1个盘子从B移到C上；
3．3将A上1个盘子从A移到C上。
将以上综合起来，可得到移动3个盘子的步骤为
A→C，A→B，C→B，A→C，B→A，B→C，A→C。
共经历7步。由此可推出：移动n个盘子要经历2n-1步。如移4个盘子经历15步，移5个盘子经历31步，移64个盘子经历264-1步。
由上面的分析可知：将n个盘子从A座移到C座可以分解为以下3个步骤：
(1) 将A上n-1个盘借助C座先移到B座上。
(2) 把A座上剩下的一个盘移到C座上。
(3) 将n-1个盘从B座借助于A座移到C座上。
上面第1步和第3步，都是把n-1个盘从一个座移到另一个座上，采取的办法是一样的，只是座的名字不同而已。为使之一般化，可以将第1步和第3步表示为：
“将“one” 座上n-1个盘移到“two” 座(借助“three” 座)。只是在第①步和第③步中，one、two、three和A、B、C的对应关系不同。对第①步，对应关系是one——A，two——B，three——C。对第③步，是：one——B，two——C，three——A。
因此，可以把上面3个步骤分成两类操作：
(1) 将n-1个盘从一个座移到另一个座上(n>1)。这就是大和尚让小和尚做的工作，它是一个递归的过程，即和尚将任务层层下放，直到第64个和尚为止。
(2) 将1个盘子从一个座上移到另一座上。这是大和尚自己做的工作。
下面编写程序。分别用两个函数实现以上的两类操作，用hanoi函数实现上面第1类操作(即模拟小和尚的任务)，用move函数实现上面第2类操作(模拟大和尚自己移盘)，函数调用hanoi(n，one，two，three)表示“将n个盘子从“one” 座移到“three” 座的过程(借助“two”针”)。函数调用move(x，y)表示将1个盘子从x 座移到y 座的过程。x和y是代表A、B、C座之一，根据每次不同情况分别取A、B、C代入。
程序如下：
void move(char x，char y)
｛
printf("%c-->%c\n"，x，y)；
｝
void hanoi(int n，char one，char two，char three)
/*将n个盘从one座借助two座，移到three座/
｛
if(n＝＝1) move(one，three)；
else
｛
hanoi(n-1，one，three，two)；
move(one，three)；
hanoi(n-1，two，one，three)；
｝
｝
main()
｛
int m；
printf("input the number of diskes：")；
scanf("%d"，&m)；
printf("The step to moving %3d diskes：\n"，m)；
hanoi(m，′A′，′B′，′C′)；
｝
运行情况如下：
input the number of diskes：3
The step to moving 3 diskes：
A-->C
A-->B
C-->B
A-->C
B-->A
B-->C
A-->C
在本程序中move函数并未真正移动盘子，而只是打印出移盘的方案(从哪一个座移到哪一个座)。
