Hanoi Tower - 题解

标签与难度

标签: 递归, 分治, 汉诺塔, 构造, 动态规划, 递推难度: 2000

题目大意喵~

各位看官，乃好呀！这道题是经典汉诺塔问题的一个超级可爱的变种哦，主角是我们猫猫家族的成员呢，喵~

事情是这样的：有 $n$ 只编号从 1 到 $n$ 的小猫，还有 A、B、C 三个盘子（或者叫格子）。

初始状态：
- 所有奇数编号的小猫（1, 3, 5, ...）都在 A 盘上，从上到下按编号从小到大叠好（1在最上面）。
- 所有偶数编号的小猫（2, 4, 6, ...）都在 C 盘上，也是从上到下按编号从小到大叠好（2在最上面）。
- B 盘是空的。
目标状态：
- 所有小猫（1 到 $n$ ）都移动到 B 盘上，并且从上到下按编号从小到大叠好。
移动规则：
- 和经典的汉诺塔一样，一次只能移动一只位于盘子最顶端的小猫。
- 小猫只能移动到空盘子上，或者移动到另一只比自己编号大的小猫上面。

我们需要做两件事：

计算出要完成这个目标，最少需要多少步。
如果 $n \le 20$ ，还需要把每一步的移动过程打印出来，格式是 猫猫编号目标盘子。

解题思路分析

这道题呀，一看就是汉诺塔家族的成员，那解题的灵魂肯定是递归和分治思想啦，喵~

让我们先从终点倒着想。我们的最终目标是让 $1, 2, \dots, n$ 这 $n$ 只猫猫整齐地排在B盘上。这意味着，在移动的最后一步，一定是将 $1, \dots, n-1$ 这个猫猫塔，从某个辅助盘（A或C）搬到了已经安顿在B盘底部的第 $n$ 号猫猫身上。

那么，为了移动第 $n$ 号猫猫到B盘，我们必须满足两个条件：

B盘必须是空的。
所有比 $n$ 小的猫猫（也就是 $1, \dots, n-1$ ）必须全部集中在同一个盘子上（A或C），这样才能给 $n$ 号猫猫腾出移动空间。

好，现在的任务就变成了：

第一阶段：想办法把 $1, \dots, n-1$ 这些猫猫全部集合到A或C中的一个盘子上。
第二阶段：把 $n$ 号猫猫从它所在的盘子移动到B盘。
第三阶段：把在辅助盘上集合好的 $1, \dots, n-1$ 猫猫塔，利用经典汉诺塔算法，移动到B盘的 $n$ 号猫猫身上。

第三阶段很简单，就是一次标准的 $n-1$ 阶汉诺塔移动，需要 $2^{n-1}-1$ 步。第二阶段也简单，只需要1步。最难的就是第一阶段，因为 $1, \dots, n-1$ 这些猫猫一开始是分散在A和C两个盘子上的！

直接从 $n$ 递归到 $n-1$ 好像有点复杂，因为 Solve(n-1) 这个问题和 Solve(n) 的初始状态结构是一样的，但目标盘子却变了。这样递归下去，状态会变得很混乱，喵~ >.<

这时候，就需要一个天才的思路啦！让我们换个角度，不看 $n-1$ 和 $n-2$ ，我们把目光放得更远一点，看看 $n, n-1, n-2$ 这三只最大的猫猫。

猫猫 $n$ 和 $n-2$ 的编号奇偶性相同，所以它们总是在同一个起始盘子上。
猫猫 $n-1$ 的编号奇偶性与它们俩都不同，所以它总是在另一个起始盘子上。

这个发现是解决问题的金钥匙！我们可以把问题分解成处理 $1, \dots, n-3$ 的子问题，以及处理 $n-2, n-1, n$ 这三只大猫猫。

让我们以 $n$ 是奇数为例来推演一遍这个神奇的 n-3 分解过程（ $n$ 是偶数的情况是完全对称的哦）：

当 $n$ 是奇数时:

初始状态： $n$ 和 $n-2$ 在A盘, $n-1$ 在C盘。
最终目标：所有猫猫到B盘。

分解步骤：

solve(n-3): 我们先假装 $n, n-1, n-2$ 这三只大猫不存在，递归地解决前 $n-3$ 只小猫的问题。目标是把它们全部移动到B盘。
- 状态: $1..n-3$ 在B盘， $n-2, n$ 在A盘, $n-1$ 在C盘。
move(n-2, C): 现在，为了把 $1..n-1$ 全部集中到C盘，我们需要把碍事的 $n-2$ 从A盘移走。把它移到C盘，放在 $n-1$ 身上是完全合法的。
- 状态: $1..n-3$ 在B盘， $n$ 在A盘， $n-2, n-1$ 在C盘。
hanoi(n-3, B -> C): 将B盘上的 $1..n-3$ 猫猫塔，利用A盘作为中转，整体移动到C盘。
- 状态: $n$ 在A盘，B盘空了，而 $1..n-1$ 所有猫猫现在都整齐地在C盘上！这正是我们移动 $n$ 号猫猫所需要的完美局面！
move(n, B): 把孤零零的 $n$ 号大猫从A盘移动到空空的B盘。
- 状态: $n$ 在B盘底， $1..n-1$ 在C盘。
hanoi(n-1, C -> B): 最后，把C盘上的 $1..n-1$ 猫猫塔，利用A盘作为中转，整体移动到B盘的 $n$ 号猫猫身上。
- 状态: 任务完成！ $1..n$ 所有猫猫都在B盘上啦，喵~

你看，通过这个 n-3 的分解，我们把一个复杂的混合问题，拆解成了一个规模更小的同类问题 solve(n-3) 和两次标准的汉诺塔移动 hanoi(n-3) 和 hanoi(n-1)，以及两次单步移动。

移动步数递推

设 $G(n)$ 为解决 $n$ 只猫猫问题的总步数， $H(k) = 2^k - 1$ 为标准 $k$ 阶汉诺塔的步数。根据上面的分析，我们可以得到递推公式：

G(n) = G(n-3) + \underbrace{1}_{\text{move } n-2} + \underbrace{H(n-3)}_{\text{hanoi } n-3} + \underbrace{1}_{\text{move } n} + \underbrace{H(n-1)}_{\text{hanoi } n-1}

代入 $H(k) = 2^k - 1$ ：

G(n) = G(n-3) + 1 + (2^{n-3}-1) + 1 + (2^{n-1}-1)

G(n) = G(n-3) + 2^{n-3} + 2^{n-1}

基本情况 (Base Cases):

$G(1) = 1$ (猫1: A -> B)
$G(2) = 2$ (猫2: C -> B, 猫1: A -> B)
$G(3) = 5$ (猫1: A -> C, 猫3: A -> B, 然后是2阶汉诺塔从C到B)

有了这个递推公式和基本情况，我们就可以用DP或者简单的循环来计算出任何 $n$ 对应的总步数啦！

代码实现

下面是我根据上面的思路，全新编写的代码实现哦！注释写得很详细，希望能帮助你理解每一步，喵~

cpp

#include <iostream>
#include <vector>
#include <cmath>

// 使用 long long 来存储步数，因为步数会增长得非常快！
using ull = unsigned long long;

// 标准汉诺塔移动函数
// 将 num_cats 只猫猫从 src 盘，经由 aux 盘，移动到 dest 盘
void hanoi(int num_cats, char src, char dest, char aux) {
    if (num_cats <= 0) {
        return;
    }
    // 1. 将 n-1 只猫从 src 移动到 aux
    hanoi(num_cats - 1, src, aux, dest);
    // 2. 将第 n 只猫从 src 移动到 dest
    std::cout << num_cats << " " << dest << "\n";
    // 3. 将 n-1 只猫从 aux 移动到 dest
    hanoi(num_cats - 1, aux, dest, src);
}

// 解决本题的核心递归函数
void solve_cat_tower(int n) {
    if (n <= 0) {
        return;
    }
    
    // 基本情况（Base Cases）
    if (n == 1) {
        std::cout << "1 B\n"; // 奇数猫1从A到B
        return;
    }
    if (n == 2) {
        std::cout << "2 B\n"; // 偶数猫2从C到B
        std::cout << "1 B\n"; // 奇数猫1从A到B
        return;
    }

    // 递归主体，基于 n-3 的分解
    
    // 1. 递归解决前 n-3 只猫的问题，把它们都移动到目标B盘
    solve_cat_tower(n - 3);

    char src_n, src_n_minus_1, src_n_minus_2;
    if (n % 2 != 0) { // n 是奇数
        src_n = 'A';
        src_n_minus_1 = 'C';
        src_n_minus_2 = 'A';
        
        // 2. 将 n-2 从A移动到C，给n-3的猫猫腾地方
        std::cout << n - 2 << " " << src_n_minus_1 << "\n";
        // 3. 将B盘的 n-3 猫塔移动到C盘
        hanoi(n - 3, 'B', 'C', 'A');
        // 4. 将 n 从A移动到B
        std::cout << n << " " << 'B' << "\n";
        // 5. 将C盘的 n-1 猫塔移动到B
        hanoi(n - 1, 'C', 'B', 'A');

    } else { // n 是偶数
        src_n = 'C';
        src_n_minus_1 = 'A';
        src_n_minus_2 = 'C';

        // 2. 将 n-2 从C移动到A
        std::cout << n - 2 << " " << src_n_minus_1 << "\n";
        // 3. 将B盘的 n-3 猫塔移动到A盘
        hanoi(n - 3, 'B', 'A', 'C');
        // 4. 将 n 从C移动到B
        std::cout << n << " " << 'B' << "\n";
        // 5. 将A盘的 n-1 猫塔移动到B
        hanoi(n - 1, 'A', 'B', 'C');
    }
}


int main() {
    // 加速输入输出，对大数据友好
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 使用递推公式计算总步数
    std::vector<ull> dp(n + 1, 0);
    std::vector<ull> pow2(n + 1, 1);
    
    for(int i = 1; i <= n; ++i) {
        pow2[i] = pow2[i-1] * 2;
    }

    if (n >= 1) dp[1] = 1;
    if (n >= 2) dp[2] = 2;
    if (n >= 3) dp[3] = 5;

    for (int i = 4; i <= n; ++i) {
        // G(n) = G(n-3) + 2^(n-3) + 2^(n-1)
        dp[i] = dp[i-3] + pow2[i-3] + pow2[i-1];
    }
    
    std::cout << dp[n] << "\n";

    // 只有 n <= 20 时才打印步骤
    if (n <= 20) {
        solve_cat_tower(n);
    }

    return 0;
}

复杂度分析

时间复杂度: $O(2^n)$
- 计算总步数的部分，我们用了一个DP数组，时间复杂度是 $O(n)$ 。
- 打印移动步骤的部分，solve_cat_tower(n) 函数的调用次数与总移动步数 $G(n)$ 成正比。从递推公式 $G(n) = G(n-3) + 2^{n-3} + 2^{n-1}$ 可以看出， $G(n)$ 的增长速度和 $2^n$ 是同阶的。所以这部分的时间复杂度是 $O(2^n)$ 。
- 总的时间复杂度由较慢的部分决定，也就是 $O(2^n)$ 。
空间复杂度: $O(n)$
- 我们使用了DP数组和2的幂次数组来计算总步数，占用了 $O(n)$ 的空间。
- 递归函数 solve_cat_tower 和 hanoi 的最大递归深度都是 $O(n)$ ，所以函数调用栈会占用 $O(n)$ 的空间。
- 总的空间复杂度就是 $O(n)$ 啦。

知识点总结

这道题真是一次愉快的思维体操呢，喵~ 从中我们可以学到：

汉诺塔问题的变种：不要被非标准初始/目标状态吓到。核心思想通常还是分治和递归，关键是找到正确的分解方式。
创造性地分解问题：经典的汉诺塔是 n -> n-1 的分解。但这道题告诉我们，有时候 n -> n-3 或者其他不那么直观的分解方式才是正解！要敢于尝试不同的分割点。
状态分析与归纳：仔细分析问题中元素的性质（比如猫猫编号的奇偶性），找到规律，是简化问题的关键。我们正是利用了 n 和 n-2 奇偶性相同这一点才找到了突破口。
递推与动态规划：对于求解最优解的步数这类问题，一旦找到了递归结构，就可以写出递推公式，并用DP高效地计算出结果。

希望这篇题解能帮到你，如果还有问题，随时可以再来问我哦！喵~

Hanoi Tower - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​