汉诺塔问题是一个递归的经典问题.
问题描述:
有 x,y,z 三根柱子, 在 x 柱子上有按照大在下, 小在上的规则, 放着 64 个套筒, 现在要将 64 个套筒借助柱子 y 移到柱子 z 上, 且每次只能移动一个套筒, 每个柱子上的套筒每时每刻只能按照大套筒在下面, 小套筒在上面的规则放着, 请问一共要移动多少次才能完成该项任务?
解题思路:
我们一般会这样想, 先把上面 63 个套筒从 x 移到 y, 然后再将第 64 个从 x 移到 z, 最后再将 63 个从 y 移动到 z, 任务完成.
那么 63 个套筒怎么移动呢? 同样, 先把 62 个套筒从 x 移到 y.....
代码详解:
- // 一共 64 个盘子
- void hanota(char a, char b, char c,int n) {
- if (n == 1)
- cout <<a << "->" << c << endl; // 将第 64 个从 a, 移到 c
- else {
- hanota(a, c, b, n - 1);// 先将上面 63 个盘子移到 b
- hanota(a, b, c, 1);// 然后将第 64 个从 a, 移到 c
- hanota(b, a, c, n - 1);// 最后将 b 上的 63 个移到 c
- }
- }
- void T014() {
- char a = 'x';
- char b = 'y';
- char c = 'z';
- hanota(a, b, c, 64);
- }
来源: http://www.bubuko.com/infodetail-2988556.html