汉诺塔问题
问题描述
汉诺塔问题描述：相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
解题思路
要把A杆的64个金盘全部移动到C杆中，且要保持自下而上由大到小的顺序，可以考虑先将A杆中上面63个金盘移动到过度杆B中，然后将A杆中剩下的一个金盘移动到C杆中，最后把过度杆B中的63个金盘移动到C杆中，而要想把B杆中的63个金盘移动到C杆，此时可以把A杆看作是过度杆，即先将B杆上面的62个金盘移动到过度杆A中，再将B杆中剩下的一个金盘移动到C杆，最后把A杆中的62个金盘移动到C杆中......如此反复，最终即可把A杆中的64个金盘全部移动到C盘中。
我们现在假设有n个盘子，自上而下的编号为1,2,3...n,可以将上述过程总结为以下3个步骤：
- 以C杆为中介，将A杆中编号为1~n-1号的金盘移至B杆；
- 将A杆中剩下的第n号金盘移至C盘；
- 以A杆为中介，将B杆中的n-1个金盘移至C盘。
代码实现
1 #include<stdio.h>
2 int i = 1;//记录步数
3 void move(char A, char B)//将A中的盘子移动到B中
4 {
5 printf("第%d步：%c -> %c\n",i++, A, B);
6 }
7 void hanoi(int n, char A, char B, char C)//以B为中介，把A中的n个金盘移动到C中
8 {
9 if (n == 1) {
10 move(A, C);
11 }
12 else {
13 hanoi(n - 1, A,C,B);//以C为中介，把A中的n=1个金盘移动到B中
14 move(A, C);
15 hanoi(n - 1, B, A, C);//以A为中介，把B中的n-1个金盘移动到C中
16 }
17 }
18
19 int main()
20 {
21 int n;
22 scanf_s("%d", &n);
23 hanoi(n, 'A', 'B', 'C');
24 return 0;
25 } 执行结果
递归算法
汉诺塔问题本质上运用了递归的思想，即将一个大型复杂的问题转化为若干个与原问题相似但规模较小的问题。
- 必须存在终止条件（即递归出口）；
- 过程的描述包含它本身，就是在过程或函数中调用自身。