有三根柱子 A,B,C
A 柱子上穿着 N 个 (N>1) 穿孔圆盘, 盘的尺寸由下到上依次变小. 要将所有圆盘移至 C 柱子, 遵循以下规则:
1. 每次只能移动一个圆盘;
2. 小的上面不能放大的.
拆解问题, N 个盘子, 把最下面的那个大的看做地面, 看成不存在, 问题变为 N-1 汉诺塔问题
把下面两层看做不存在, 就是 N-2....
方法就是:
先移动一个盘子(解决 1 汉诺塔问题)
在此基础上, 解决 2 汉诺塔问题
....
....
解决 N-1 汉诺塔问题
最终解决 N 汉诺塔问题
当然, 递归是倒过来的, 虽然思维是倒过来的, 但实际顺序还是正的
递归思想:
1. 将 A 柱子上的 n-1 个圆盘都移到 B 柱子上(n-1 汉诺塔)
2. 将 A 柱子上的第 n 个圆盘移到 C 上
3. 将 B 上的 n-1 个圆盘移动到 C 上了(n-1 汉诺塔)
以 4 为例
将 A 上前三个盘子移动到 B(3 汉诺塔)
将最后一个移动到 C
将 B 上的 3 个盘子移动到 C(3 汉诺塔)
下面解决 3 汉诺塔, 这里是 A 到 B
将上面两个盘子移动到 C(2 汉诺塔)
将第三个移动到 B
将 C 上的两个移动到 B
2 汉诺塔问题, 这里是 A 到 C
将上面第一个盘子移动到 B
将第二个盘子移动到 C
将 B 上的盘子移动到 C
好, 上 c++ 代码
- // 从 X1 柱子移动 num 个盘子到 X2 柱子, X3 是中转
- // 原本函数参数是 char from,char to,char zhongzhuan,int num
- // 但这样写有时候还会被变量英文含义所误导, 所以无所谓啦
- void hanTower(char X1, char X2, char X3, int num)
- {
- if (num == 0)
- return;
- hanTower(X1, X3, X2, num - 1);// 中转移动 N-1 个盘子
- cout <<"Move" << X1 << "->"<<X2<<endl;// 移动剩下的那个盘子
- hanTower(X3, X2, X1, num - 1);// 移动到目标
- }
来源: http://www.bubuko.com/infodetail-2989880.html