C++ 汉诺塔问题详解与代码实现

汉诺塔问题概述

汉诺塔问题是一个经典的递归问题，其目标是将一组盘子从一根柱子移动到另一根柱子，遵循以下规则：每次只能移动一个盘子，且大盘子不能放在小盘子上面。

递归思路的关键在于将问题分解为更小的子问题：假设有 n 个盘子，可以将问题分解为移动前 n-1 个盘子到辅助柱子，移动第 n 个盘子到目标柱子，再移动前 n-1 个盘子到目标柱子。

递归解法

代码实现

#include <iostream>
using namespace std;

void hanoi(int n, char source, char auxiliary, char target) {
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << target << endl;
        return;
    }
    hanoi(n - 1, source, target, auxiliary);
    cout << "Move disk " << n << " from " << source << " to " << target << endl;
    hanoi(n - 1, auxiliary, source, target);
}

int main() {
    int n;
    cout << "Enter the number of disks: ";
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

逻辑分析

1. 函数定义：hanoi 函数接受四个参数：盘子数量 n，源柱子 source，辅助柱子 auxiliary，目标柱子 target。
2. 递归终止条件：当 n == 1 时，直接移动盘子从源柱子到目标柱子。
3. 递归调用：
   • 将前 n-1 个盘子从源柱子移动到辅助柱子。
   • 移动第 n 个盘子到目标柱子。
   • 将前 n-1 个盘子从辅助柱子移动到目标柱子。

迭代解法

借助栈数据结构模拟递归过程，将每一步的操作压入栈中，逐个处理。这种方法避免了递归可能带来的栈溢出问题。

代码实现

#include <iostream>
#include <stack>
using namespace std;

struct Move {
    int n;
    char source, auxiliary, target;
};

void hanoiIterative(int n, char source, char auxiliary, char target) {
    stack<Move> s;
    s.push({n, source, auxiliary, target});
    while (!s.empty()) {
        Move current = s.top();
        s.pop();
        if (current.n == 1) {
            cout << "Move disk 1 from " << current.source << " to " << current.target << endl;
        } else {
            s.push({current.n - 1, current.auxiliary, current.source, current.target});
            s.push({1, current.source, current.auxiliary, current.target});
            s.push({current.n - 1, current.source, current.target, current.auxiliary});
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of disks: ";
    cin >> n;
    hanoiIterative(n, 'A', 'B', 'C');
    return 0;
}

逻辑分析

1. 结构体定义：Move 结构体保存每一步操作的信息。
2. 栈的使用：初始化栈，压入初始状态。
3. 循环处理：
   • 弹出栈顶操作。
   • 如果是移动单个盘子，直接输出。
   • 否则，按照递归的顺序压入子问题。

复杂度与公式

时间和空间复杂度

• 递归解法：时间复杂度为 O(2^n)，空间复杂度为 O(n)（递归栈深度）。
• 非递归解法：时间复杂度同样为 O(2^n)，空间复杂度为 O(n)（栈的最大深度）。

数学公式

汉诺塔问题的最小移动步数为 $2^n - 1$，其中 n 为盘子数量。

• 1 个盘子：$2^1 - 1 = 1$ 步。
• 2 个盘子：$2^2 - 1 = 3$ 步。
• 3 个盘子：$2^3 - 1 = 7$ 步。

变种问题

1. 双色汉诺塔：盘子分为两种颜色，移动时需遵循颜色交替规则。
2. 循环汉诺塔：柱子排列成环形，移动方向受限。

这些变种通常需要调整递归或迭代逻辑以适应额外约束条件。