设A,B,C是3个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座A上的这一叠圆盘移到塔座C上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：
规则1：每次只能移动1个圆盘；
规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则3：在满足规则1和2的前提下，可将圆盘移至A,B,C中任一塔座上。
主要思路：
1、将A上的n-1个盘子借助C移到B上
2、将A上的第n个盘子移到C上
3、再将B上的全部盘子移到C上
ps：显然，这是一个递归的过程。
算法思路
1、构造一个显示盘子移动路径的函数
void move (char a, char b) {
cout << a << "->" << c;
}
2、构造一个递归函数
void hanoi (int n, char a, char b, char c) {
//将A上的n个盘子借助B全部移到C上
if (n == 1) move(a, c);//如果A上只有一个盘子，将A上最后一个盘子移到C上，结束本层递归
else {
hanoi (n-1, a, c, b);//将A上n-1个盘子全部移到B上
move (a, c);//显示路径
hanoi (n-1, b, a, c);//将B上的n-1个盘子移到C上
}
}
完整代码
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
void move (char a, char b) {
cout << a << "->" << c;
}
void hanoi (int n, char a, char b, char c) {
if (n == 1) move(a, c);
else {
hanoi (n-1, a, c, b);
move (a, c);
hanoi (n-1, b, a, c);
}
}
int main ()
{
char a = 'A', b = 'B', c = 'C';
int n;
cin >> n;
hanoi (n, a, b, c)
return 0;
}
Example
4 enter
输出结果：
4
A->B
A->C
B->C
A->B
C->A
C->B
A->B
A->C
B->C
B->A
C->A
B->C
A->B
A->C
B->C
