Hanoi 塔问题在 C++ 中的递归实现

Hanoi 塔问题想必是很多同学在大一都会接触到的，它是一个很经典的算法问题，这里主要阐释 Hanoi 问题在 C++ 中的递归实现。当然你也可以查阅一些其他资料来理解它的非递归实现过程，这里就不再叙述了。有兴趣的同学可以参考：迭代式汉诺塔(利用栈实现非递归) 汉诺塔问题的递归和非递归算法

本文意旨解决“为何圆盘的移动的位置不对？”的问题，用两组代码来分析圆盘的移动位置。

PS: 当然，如果想更好地理解这篇博客，就需要你在阅读之前对 Hanoi 塔问题有一个清晰的了解。如果你还不知道什么是 Hanoi 塔问题，请移步百度百科。

开始分析

1. 先来看一组示例代码

在此代码块中，n 代表圆盘的个数，需要通过键盘输入。开始时圆盘都位于 a 柱，期间借助 b 柱将圆盘全部移到 c 柱

#include <iostream>

int main() {
    void hanoi(int n, char a, char b, char c);
    int n;
    std::cout << "input the number of saucers: ";
    std::cin >> n;
    hanoi(n, 'a', 'b', 'c');
    return 0;
}

void hanoi(int n, char a, char b, char c) {
    if (n == 1) {
        std::cout << "move " << n << " from " << a << " to " << c << std::endl;
        return;
    }
    hanoi(n - 1, a, c, b); // 将第 n-1 个圆盘从 a 柱借助 c 柱移动到 b 柱

    std::cout << "move " << n << " from " << a << " to " << c << std::endl; // 将第 n个圆盘从 a柱直接移动到 c柱

    hanoi(n - 1, b, a, c); // 将第 n-1个圆盘从 b柱借助 a柱移动到 c柱
}

如果你之前有成功实现过hanoi塔从 a 移动到 c (a ⟹ c) 的递归算法，应该很容易就能看懂。但是你试过将圆盘从 a 柱全部移动到 b 柱上的情况吗？

如果你已经清楚了代码的含义，那么你可以试着实现另外的几种情况

a ⟹ b

b ⟹ c

c ⟹ a

c ⟹ b

2. 再来看另一组示例代码

在此代码块中，n 代表圆盘的个数，需要通过键盘输入。开始时圆盘都位于 a 柱，期间借助 c 柱将圆盘全部移到 b 柱

#include <iostream>

int main() {
    void hanoi(int n, char a, char b, char c);
    int n;
    std::cout << "input the number of saucer: ";
    std::cin >> n;
    hanoi(n, 'a', 'b', 'c');
    return 0;
}

void hanoi(int n, char a, char b, char c) {
    if (n == 1) {
        std::cout << n << ": " << a << " --> " << b << std::endl;
        return;
    }
    hanoi(n - 1, a, c, b); // 将第 n-1个圆盘从 a柱经由 b柱移动到 c柱

    std::cout << n << ": " << a << " --> " << b << std::endl; // 将第 n个圆盘直接移动到 b柱

    hanoi(n - 1, c, b, a); // 将第 n-1个圆盘从 c柱经由 a柱移动到 b柱
}

你可能会觉得两组代码在实现上没什么差别，那我们来看两组代码其中一行的对照：

hanoi(n - 1, a, c, b); // 将第 n-1 个圆盘从 a 柱借助 c 柱移动到 b 柱

hanoi(n - 1, a, c, b); // 将第 n-1个圆盘从 a柱经由 b柱移动到 c柱

我们可以发现，两组代码中这一行代码都是相同的，但为什么实现的操作是不一样的呢？

3. 其中两行代码的对比

std::cout << "move " << n << " from " << a << " to " << c << std::endl; // 将第 n个圆盘从 a柱直接移动到 c柱

std::cout << n << ": " << a << " --> " << b << std::endl; // 将第 n个圆盘直接移动到 b柱

我们可以看到第一行代码时从 a位置 指向 c位置，第二行代码则是从 a位置 指向 b位置，而第一行代码中的 “a位置” 和 “c位置” 对应了第一组代码 hanoi(n - 1, a, c, b); 中的 c 和 b，第二行代码中的 “a位置” 和 “b位置”对应了第二组代码 hanoi(n - 1, a, c, b); 中的 c 和 b

整组代码中实现输出是依靠 输出流语句，所以 hanoi(n - 1, a, c, b); 中的字母顺序要根据 输出流语句 的变化而变化以达到正确调用递归的目的。

也是大一刚开始接触编程语言，希望我的分享能给大家带来帮助 (｡･∀･)ﾉﾞ

到这里如果你还没有弄明白，这里能以图的形式更直观地理解 Hanoi 塔问题的递归实现，请参考：汉诺塔的图解递归算法

# C++, Hanoi, 算法

Hanoi 塔问题在 C++ 中的递归实现

开始分析

1. 先来看一组示例代码

2. 再来看另一组示例代码

3. 其中两行代码的对比

评论

最新文章

标签云

Your browser is out-of-date!