Hanoi 塔问题求解（递归与非递归算法）

Hanoi塔是经典的递归算法的应用，但是有意思的是我之前学习的算法或数据结构的课都漏掉了这个例子，补一下吧，包括两类三种算法实现。

问题介绍

Hanoi塔问题为：考虑三根杆子A，B，C，A杆上有 N 个 (N>1) 穿孔圆盘，圆盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。

问：如何移动？最少要移动多少次？

递归分析

重点关注最大的圆盘，它是整个任务的核心：虽然它在最底层不会影响别的圆盘的操作，但是将它从A移动到C时，必然其他N-1个盘都处于B。
据此可以把问题分解为三个子任务：

1. 将N-1个圆盘从A移动到B，此时C可以用作临时存放区
2. 将最大的圆盘从A直接移动到C
3. 将N-1个圆盘从B移动到C，此时A可以用作临时存放区（和第一步的任务是等价的）

记$f(n)$为n个圆盘时最少的移动次数，显然有初值$f(1)=1$，以及递推关系
$$
f(n) = 1 + 2f(n-1)
$$
因此解得$f(n)=2^n-1$为最少移动次数。

这里的理论分析直接提供了递归算法的思路，但是理论分析的结果并非仅仅对递归算法有效，对非递归算法也是成立的，即始终有$2^n-1$的最小步数限制，无论采用任何算法都是如此。

递归算法（Python 实现）

通过简要分析，递归实现的求解是水到渠成的

step = 1


def hanoi(n, a, b, c, depth=0):
    def move(n, a, c):
        global step
        print("    " * depth, end="")
        print(f"{step=}: move [{n}] from {a} to {c}")
        step += 1

    if n == 1:
        move(n, a, c)
    else:
        hanoi(n - 1, a, c, b, depth=depth + 1)
        move(n, a, c)
        hanoi(n - 1, b, a, c, depth=depth + 1)


if __name__ == "__main__":
    n = int(input("Hanoi Problem, N = "))
    hanoi(n, "A", "B", "C")

这里可以记录步数，并且通过缩进的不同展示了递归的关系。例如N=4的结果如下

Hanoi Problem, N = 4
            step=1: move [1] from A to B
        step=2: move [2] from A to C
            step=3: move [1] from B to C
    step=4: move [3] from A to B
            step=5: move [1] from C to A
        step=6: move [2] from C to B
            step=7: move [1] from A to B
step=8: move [4] from A to C
            step=9: move [1] from B to C
        step=10: move [2] from B to A
            step=11: move [1] from C to A
    step=12: move [3] from B to C
            step=13: move [1] from A to B
        step=14: move [2] from A to C
            step=15: move [1] from B to C

模拟递归算法（C 实现）

函数递归依赖于函数调用栈，我们可以绕过函数调用栈，自己建立和维护一个栈结构，从而实现一个模拟递归的算法求解。
（这是一种普适的做法，可以将所有的递归求解都转化为非递归求解，虽然本质上还是一样的）

下面的C语言程序修改自南京大学2022操作系统-蒋炎炎，
由于只使用了非常原始的工具——通过数组和指针模拟栈，因此显得比较复杂（改成C++就会简略很多）。
在源文件中添加了很多注释并提高了可读性，同时调整输出格式以保持与前文一致。

#include <assert.h>
#include <stdio.h>

// 模拟栈帧，pc指向下一条执行指令，其他的都是传递的参数
typedef struct {
    int pc;
    int n;
    char from, via, to;
    int depth;
} Frame;

#define CALL_HANOI(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
#define MOVE(x1, x2, x3, x4, x5)                                               \
    do {                                                                       \
        printf("%*s", 4 * (x5), "");                                           \
        printf("step=%d: move [%d] from %c to %c\n", (x1), (x2), (x3), (x4));  \
    } while (0)

#define RET() ({ top--; })

void virtual_hanoi(int n, char from, char via, char to) {
    Frame stk[64];         // 用数组模拟调用栈
    Frame *top = stk - 1;  // 栈顶指针

    int step = 1;  // 步数记录

    // 创建第一个栈帧并初始化
    // 相当于调用hanoi(n,from,via,to)
    CALL_HANOI(n, from, via, to, 0);

    // f指向栈顶，仅当调用栈为空时才会退出
    for (Frame *f = top; (f = top) >= stk; f->pc++) {
        // 根据f->pc的值来执行具体指令
        switch (f->pc) {
        case 0:  // 函数第一步指令，如果当前n==1则直接移动，并从模拟栈中弹出当前栈帧
            if (f->n == 1) {
                MOVE(step++, f->n, f->from, f->to, f->depth);
                RET();
            }
            break;
        case 1:  // 函数第二步指令，调用hanoi(n-1,from,to,via,depth+1)
            CALL_HANOI(f->n - 1, f->from, f->to, f->via, f->depth + 1);
            break;
        case 2:  // 函数第三步指令，直接移动
            MOVE(step++, f->n, f->from, f->to, f->depth);
            break;
        case 3:  // 函数第四步指令，调用hanoi(n-1,via,from,to,depth+1)
            CALL_HANOI(f->n - 1, f->via, f->from, f->to, f->depth + 1);
            break;
        case 4:  // 函数第五步指令，弹出当前栈帧
            RET();
            break;
        default: assert(0);
        }
    }
}

int main() {
    virtual_hanoi(4, 'A', 'B', 'C');
    return 0;
}

程序刻意地没有使用任何的子函数，只在同一个函数内部实现，两种子过程使用宏进行了简化，从而可以很容易地将其与递归版算法一一对应。运行结果如下：

            step=1: move [1] from A to B
        step=2: move [2] from A to C
            step=3: move [1] from B to C
    step=4: move [3] from A to B
            step=5: move [1] from C to A
        step=6: move [2] from C to B
            step=7: move [1] from A to B
step=8: move [4] from A to C
            step=9: move [1] from B to C
        step=10: move [2] from B to A
            step=11: move [1] from C to A
    step=12: move [3] from B to C
            step=13: move [1] from A to B
        step=14: move [2] from A to C
            step=15: move [1] from B to C

非递归分析

首先定义每一个杆子的后继：（有的描述中是将三个杆子排列为品字形，实质是一样的）

• 如果N为偶数，后继关系为：A->B->C->A
• 如果N为奇数，后继关系为：A->C->B->A

我们可以断言，汉诺塔的非递归算法只要依次进行如下的基本操作即可：

1. 由于最小圆盘的移动是自由的，必然可以将最小的圆盘从当前杆子移动到后继上
2. 对于最小圆盘位置之外的两个杆子：（这里允许的操作其实是唯一的）
   • 如果有一个为空，将另一个杆子顶端圆盘移动到空杆子
   • 如果均非空，必然有一个杆子的顶端圆盘较小（从而可移动），将其移动到另一个杆子上
3. 检查是否完成，如果尚未完成，回到第一步继续重复

最后就可以在最优步数时完成汉诺塔的移动。

非递归算法包含一个死循环，不能直接判断需要多少次操作，但是事实上仍然只需要最少步数就可以退出循环，提供的解仍然是最优解。
至于非递归算法的原理，直接从递归算法得到的结果中找规律即可。

非递归算法（C++ 实现）

这里采用C++实现，可以避免手动维护三个栈的麻烦。

#include <iostream>
#include <stack>

struct Tower {
    char id;
    Tower *next = nullptr;
    std::stack<size_t> data{};
};

void move(Tower *from, Tower *to) {  // 移动并记录
    static int step = 1;

    size_t top = from->data.top();
    std::cout << "step=" << step++ << " move [" << top << "] from " << from->id
              << " to " << to->id << "\n";

    from->data.pop();
    to->data.push(top);
}

void compare_and_move(Tower *t1, Tower *t2) {
    if (t1->data.empty() && t2->data.empty()) return;

    if (t1->data.empty()) { move(t2, t1); }
    else if (t2->data.empty()) { move(t1, t2); }
    else {
        if (t1->data.top() < t2->data.top()) { move(t1, t2); }
        else { move(t2, t1); }
    }
}

void hanoi(size_t n, char from, char via, char to) {
    Tower a{from};
    Tower b{via};
    Tower c{to};

    if (n % 2 == 0) {  // 定义后继关系
        a.next = &b;
        b.next = &c;
        c.next = &a;
    }
    else {
        a.next = &c;
        c.next = &b;
        b.next = &a;
    }

    for (size_t i = 0; i < n; i++) { a.data.push(n - i); }

    Tower *cur = &a;  // cur始终指向最小盘所在的塔
    while (cur->data.size() != n || (cur != &c)) {
        move(cur, cur->next);
        compare_and_move(cur, cur->next->next);
        cur = cur->next;
    }
}

int main(int argc, char *argv[]) {
    hanoi(4, 'A', 'B', 'C');
    return 0;
}

由于不存在递归层级的概念，在输出信息中没有包含不同的缩进，程序运行结果如下

step=1 move [1] from A to B
step=2 move [2] from A to C
step=3 move [1] from B to C
step=4 move [3] from A to B
step=5 move [1] from C to A
step=6 move [2] from C to B
step=7 move [1] from A to B
step=8 move [4] from A to C
step=9 move [1] from B to C
step=10 move [2] from B to A
step=11 move [1] from C to A
step=12 move [3] from B to C
step=13 move [1] from A to B
step=14 move [2] from A to C
step=15 move [1] from B to C