河北大学程序设计训练营

题目描述：

借助堆栈以非递归（循环）方式求解汉诺塔的问题（n, a, b, c），即将N个盘子从起始柱（标记为“a”）通过借助柱（标记为“b”）移动到目标柱（标记为“c”），并保证每个移动符合汉诺塔问题的要求。

输入格式:

输入为一个正整数N，即起始柱上的盘数。

输出格式:

每个操作（移动）占一行，按柱1 -> 柱2的格式输出。

输入样例:

3

输出样例:

a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

解题思路：

准备：

  • 首先容易证明，当盘子的个数为n时，移动的次数应等于2^n-1。

  • 一位美国学者发现一种出人意料的方法，只要轮流进行两步操作就可以了。

  • 首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。

  • 根据圆盘的数量确定柱子的排放顺序:

    • 若n为偶数，按顺时针方向依次摆放ABC；
    • 若n为奇数，按顺时针方向依次摆放ACB。

步骤

  1. 按顺时针方向把圆盘1从现在的柱子移动到下一根柱子。

    即若n为偶数时：（奇数差不多，懒得写了😁）

    • 若圆盘1在柱子A，则把它移动到B；
    • 若圆盘1在柱子B，则把它移动到C；
    • 若圆盘1在柱子C，则把它移动到A。

  2. 把另外两根柱子上可以移动的圆盘移动到新的柱子上。

    即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。

    注意：这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性？那是不存在的，可实施的行动的确是唯一的。

  3. 反复进行第1、2步操作，最后就能按规定完成汉诺塔的移动。

参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <stack>

using namespace std;

// 移动盘子的函数
bool move(int before, int after);

// 三根柱子
char s[3] = {'a', 'b', 'c'};
stack<int> a[3];

int main() {

    int  N, count = 0;
    scanf("%d", &N);
    // 发盘子依次放在a柱子上
    for (int i = 0; i < N; i++) {
        a[0].push(N - i);
    }
    // 如果N是偶数，则三根柱子的次序为：a、b、c。
    // 如果N是奇数，则三根柱子的次序为：a、c、b。
    if (N % 2 == 1) {
        s[1] = 'c'; s[2] = 'b';
    }
    // 循环移动盘子
    while (true) {
        count++;
        // 将盘子1挪到下一个柱子上。
        move((count - 1) % 3, (count) % 3);
        // 另外两个柱子上将较小的盘子移到较大的盘子上
        if (!move((count - 1) % 3, (count + 1) % 3) && !move((count + 1) % 3, (count - 1) % 3)) {
            break;
        }
    }

    return 0;
}

// 移动盘子的函数
bool move(int before, int after) {
    // 要移出盘子的柱子是空，则返回失败。
    if (a[before].empty()) {
        return false;
    }

    // 要移入盘子的柱子不是，且移入的盘子大于柱子顶层的盘子，返回失败。
    // 先判断移入柱子是否为空是为了防止造成越界。
    // 因为先判断 "&&" 前的表达式，故不回造成 "&&" 后的表达式越界。
    if (!a[after].empty() && a[after].top() < a[before].top()) {
        return false;
    }

    //将 before 柱子上的盘子移到 after 柱子上。
    a[after].push(a[before].top());
    a[before].pop();
    // 输出
    printf("%c -> %c\n", s[before], s[after]);
    return true;
}

使用cin和cout会超时(Time Limit Exceeded, 缩写：TLE)

解决方法：

  1. 使用printf()和scant()代替
  2. 关闭同步ios::sync_with_stdio(false);。