汉诺塔问题 C++ 代码实现

题目描述

给定 A 、 B 、 C 三根足够长的细柱，在 A 柱上放有 2n 个中间有孔的圆盘，共有 n 个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的，现要将这些圆盘移到 C 柱上，在移动过程中可放在 B 柱上暂存。要求：

每次只能移动一个圆盘；
A 、 B 、 C 三根细柱上的圆盘都要保持上小下大的顺序；

设 A_n 为 2n 个圆盘完成上述任务所需的最少移动次数，对于输入的 n，输出 A_n 。

输入格式

一个正整数 n，表示在 A 柱上放有 2n 个圆盘。

输出格式

一个正整数, 为完成上述任务所需的最少移动次数 A_n 。

解题思路

汉诺塔问题是经典的递归问题，我们可以将将 n 个圆盘从 A 移到 C 分为以下三个步骤：

将 n - 1 个圆盘从 A 移到 B，可借助 C 暂存；
将编号为 n 的圆盘从 A 移到 C；
将 n - 1 个圆盘从 B 移到 C，可借助 A 暂存。

然后递归处理子问题即可。

具体实现细节见代码。

时间复杂度

每个圆盘最多被移动一次，总共需要移动 2^n - 1 次，因此时间复杂度为 O(2^n)。

C++ 代码

#include <iostream>
using namespace std;

int hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        cout << "Move disk 1 from " << A << " to " << C << endl;
        return 1;
    } else {
        int count = hanoi(n - 1, A, C, B);
        cout << "Move disk " << n << " from " << A << " to " << C << endl;
        count += hanoi(n - 1, B, A, C) + 1;
        return count;
    }
}

int main() {
    int n;
    cin >> n;
    cout << "Total steps: " << hanoi(n, 'A', 'B', 'C') << endl;
    return 0;
}