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 时，直接移动盘子从源柱子到目标柱子。