C++ 递归算法实战：汉诺塔问题详解

汉诺塔问题

汉诺塔是学习递归算法绕不开的经典题目。给定三根柱子 A、B、C 和 n 个大小不同的圆盘，初始时所有盘子按大小顺序叠放在 A 柱上。目标是将所有盘子移动到 C 柱，过程中需遵守大盘不能压在小盘上的规则。

递归思路解析

解决这个问题的关键在于'分治'。面对 n 个盘子的任务，我们可以将其拆解为更小的子问题：

1. 基准情况：如果只有一个盘子（n=1），直接从 A 移到 C，无需借助 B。
2. 递归步骤：当盘子数量大于 1 时，我们需要借助辅助柱 B 来完成转移：
   • 第一步：将 A 柱顶部的 n-1 个盘子视为整体，移动到 B 柱（此时 C 作为辅助）。
   • 第二步：将 A 柱剩余的最大盘子直接移动到 C 柱。
   • 第三步：将 B 柱上的 n-1 个盘子移动到 C 柱（此时 A 作为辅助）。

这种策略之所以有效，是因为在移动最大盘之前，A 柱上剩下的就是那个最大的盘子，而 B 柱上存放的是较小的盘子集合，保证了任何时候大盘都不会被小盘覆盖。

C++ 代码实现

下面是一个基于 LeetCode 风格的 C++ 实现。我们定义一个辅助函数 dfs 来处理具体的移动逻辑，主函数 hanota 负责初始化规模。

class Solution {
public:
    // 辅助函数：将 n 个盘子从 src 移动到 dest，aux 作为辅助
    void dfs(vector<int>& src, vector<int>& aux, vector<int>& dest, int n) {
        if (n == 1) {
            dest.push_back(src.back());
            src.pop_back();
            return;
        }
        
        // 1. 将 n-1 个盘子从 src 移到 aux
        dfs(src, dest, aux, n - 1);
        
        // 2. 将最大的盘子从 src 移到 dest
        dest.push_back(src.back());
        src.pop_back();
        
        // 3. 将 n-1 个盘子从 aux 移到 dest
        dfs(aux, src, dest, n - 1);
    }

    void hanota(vector<int>& A, vector<>& B, vector<>& C) {
         n = A.();
        (A, B, C, n);
    }
};