C++递归实现汉诺塔问题（附详细代码讲解）

C++递归实现汉诺塔问题

汉诺塔问题是计算机科学中一个经典的递归问题。该问题描述如下：

有三根柱子（通常标记为A、B、C），在柱子A上堆叠着不同大小的n个盘子，其中较小的盘子位于较大的盘子之上。目标是将所有盘子从柱子A移动到柱子C，遵循以下规则：

1. 每次只能移动一个盘子。
2. 较大的盘子不能放在较小的盘子上面。
3. 盘子可以移动到任何柱子上。

C++代码实现

#include <iostream>
using namespace std;

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << 'No.1 disk: ' << from << '->' << to << endl;
    } else {
        hanoi(n - 1, from, aux, to);
        cout << 'No.' << n << ' disk: ' << from << '->' << to << endl;
        hanoi(n - 1, aux, to, from);
    }
}

int main() {
    int n;
    cin >> n; // 输入盘子数量n
    hanoi(n, 'a', 'c', 'b'); // 调用递归函数解决汉诺塔问题
    return 0;
}

代码讲解

1. 函数hanoi(int n, char from, char to, char aux): 该函数递归地解决了汉诺塔问题。

   • n：表示要移动的盘子数量。
   • from：表示源柱子（初始为'a'）。
   • to：表示目标柱子（初始为'c'）。
   • aux：表示辅助柱子（初始为'b'）。

2. 递归基础情况: 当n为1时，直接将盘子从from移动到to。

3. 递归步骤: 当n大于1时，执行以下步骤：

   • 将n-1个盘子从from移动到aux（使用to作为辅助柱子）。
   • 将第n个盘子（最大的盘子）从from移动到to。
   • 将n-1个盘子从aux移动到to（使用from作为辅助柱子）。

4. 主函数main():

   • 获取用户输入的盘子数量n。
   • 调用hanoi函数，传入初始参数，开始解决汉诺塔问题。

示例

输入：

3

输出：

No.1 disk: a->c
No.2 disk: a->b
No.1 disk: c->b
No.3 disk: a->c
No.1 disk: b->a
No.2 disk: b->c
No.1 disk: a->c

这段代码清晰地展示了如何使用递归算法解决汉诺塔问题。通过不断地将问题分解为更小的子问题，最终实现了将所有盘子从源柱子移动到目标柱子的目标。