题目描述

汉诺塔由三根柱子（分别用A、B、C表示）和n个大小互不相同的空心盘子组成。一开始n个盘子都摞在柱子A上，大的在下面，小的在上面，形成了一个塔状的锥形体。
对汉诺塔的一次合法的操作是指：从一根柱子的最上层拿一个盘子放到另一根柱子的最上层，同时要保证被移动的盘子一定放在比它更大的盘子上面（如果移动到空柱子上就不需要满足这个要求）。我们可以用两个字母来描述一次操作：第一个字母代表起始柱子，第二个字母代表目标柱子。例如，AB就是把柱子A最上面的那个盘子移到柱子B。汉诺塔的游戏目标是将所有的盘子从柱子A移动到柱子C上面。
计算汉诺塔移动所需要的最少步骤数。

输入格式

输入一个整数n（1≤n≤30），代表盘子的个数。

输出格式

输出每一步操作的方法，最后输出一个数，这个数表示移动的次数。我们保证答案不会超过10的18次方。

输入输出样例 #1

输入 #1

1
1

输出 #1

1
2
Move disk 1 from A to C
1

输入输出样例 #2

输入 #2

1
2

输出 #2

1
2
3
4
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
3

思路

这里我们先约定一下，要被执行操作的圆盘所在柱子的编号为$source$，目标柱子的编号为$target$，而另外一个柱子的编号为$temp$。

我们从$n=1$开始分析：

  • 此时，只需要把唯一的圆盘从$source$移动到$target$即可。
  • 步数为$1$。

$n=2$时：

  • 先把$1$从$source$移动到$temp$。
  • 再把$2$从$source$移动到$target$。
  • 最后把$1$从$temp$移动到$target$。
  • 步数为$3$。

$n=3$时：

  • 先把除了$3$以外的圆盘从$source$移动到$temp$。
  • 再把$3$从$source$移动到$target$。
  • 最后把剩余的圆盘从$temp$移动到$target$。
  • 步数为$3+1+3=7$。

好，我们来找一下规律：
是不是对于$n$个圆盘，我们可以先把除了$n$以外的圆盘从$source$移动到$temp$，再把$n$从$source$移动到$target$，最后把剩余的圆盘从$temp$移动到$target$？一共就这大的三步，而且第一步和最后一步的步数相同，第二步的步数为$1$。

对于第一步和最后一步，不就等效于$n-1$个圆盘的移动步数吗？
因为$n$始终在最下面，不会影响到其他圆盘的移动。我们在分析$n-1$个圆盘的移动步数时，就可以直接忽略掉$n$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

void hanoi(int n, char source, char temp, char target) {
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << target << endl;
        return;
    }
    //将除了n以外的圆盘从source移动到temp
    hanoi(n-1, source, target, temp);
    //将n从source移动到target
    cout << "Move disk " << n << " from " << source << " to " << target << endl;
    //将剩余的圆盘从temp移动到target
    hanoi(n-1, temp, source, target);
}
int main() {
    int n;
    cin >> n;
    //假设柱子用A、B、C表示
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

一些思考

如果你每次学完汉诺塔问题，过一段时间后就又写不出来了。这在一定程度上不是你的问题，汉诺塔问题有它的特殊性。
特殊点在于“不可人脑模拟”
一般人的大脑无法模拟汉诺塔问题中的的全部移动过程（格式大于等于4就不行）。
这会导致人的心里非常没底。
由于无法模拟，
所以只能把希望全部放在子问题的定义和描述上。只能通过子问题的定义和描述来解决问题。