汉诺塔（Tower of Hanoi） 是一个经典的递归问题。它的规则如下：

1. 有三根柱子，分别称为源柱（A）、辅助柱（B）和目标柱（C）。
2. 在源柱上有若干个大小不同的盘子，初始时按大小顺序叠放（最小的在上，最大的在下）。
3. 目标是将所有盘子从源柱移动到目标柱，且在移动过程中遵循以下规则：

• 每次只能移动一个盘子。
• 盘子只能放在柱子的顶端。
• 不能将较大的盘子放在较小的盘子上面。

实现思路

1. 递归思想：
2. 将 nn 个盘子从源柱移动到目标柱，可以分解为以下步骤：
1. 将前 n-1 个盘子从源柱移动到辅助柱。
2. 将第 n 个盘子从源柱移动到目标柱。
3. 将前 n-1 个盘子从辅助柱移动到目标柱。
3. 终止条件：

当只有一个盘子时，直接将其从源柱移动到目标柱。

代码实现

以下是汉诺塔问题的C语言实现：

#include <stdio.h>

// 汉诺塔递归函数
void hanoi(int n, char source, char target, char auxiliary) {
    if (n == 1) {
        // 只有一个盘子时，直接移动
        printf("将盘子 1 从 %c 移动到 %c\n", source, target);
    } else {
        // 将前 n-1 个盘子从源柱移动到辅助柱
        hanoi(n - 1, source, auxiliary, target);

        // 将第 n 个盘子从源柱移动到目标柱
        printf("将盘子 %d 从 %c 移动到 %c\n", n, source, target);

        // 将前 n-1 个盘子从辅助柱移动到目标柱
        hanoi(n - 1, auxiliary, target, source);
    }
}

int main() {
    int n;

    // 输入盘子的数量
    printf("请输入盘子的数量: ");
    scanf("%d", &n);

    // 调用汉诺塔函数
    hanoi(n, 'A', 'C', 'B');

    return 0;
}

代码说明

1. hanoi() 函数：

• 参数：

n：当前需要移动的盘子数量。

source：源柱。

target：目标柱。

auxiliary：辅助柱

• 递归地将盘子从源柱移动到目标柱。

2. 主函数 main()：

输入盘子的数量。

调用 hanoi() 函数，开始移动盘子。

示例运行

输入：

请输入盘子的数量: 3

输出：

将盘子 1 从 A 移动到 C
将盘子 2 从 A 移动到 B
将盘子 1 从 C 移动到 B
将盘子 3 从 A 移动到 C
将盘子 1 从 B 移动到 A
将盘子 2 从 B 移动到 C
将盘子 1 从 A 移动到 C

时间复杂度

汉诺塔问题的时间复杂度为 O(2^n)，其中 n是盘子的数量。这是因为每一步都需要递归地移动 n-1 个盘子。

扩展功能

如果需要统计移动步数，可以修改代码如下：

#include <stdio.h>

int step_count = 0; // 全局变量，记录移动步数

void hanoi(int n, char source, char target, char auxiliary) {
    if (n == 1) {
        printf("将盘子 1 从 %c 移动到 %c\n", source, target);
        step_count++; // 步数加1
    } else {
        hanoi(n - 1, source, auxiliary, target);
        printf("将盘子 %d 从 %c 移动到 %c\n", n, source, target);
        step_count++; // 步数加1
        hanoi(n - 1, auxiliary, target, source);
    }
}

int main() {
    int n;

    printf("请输入盘子的数量: ");
    scanf("%d", &n);

    hanoi(n, 'A', 'C', 'B');

    printf("总移动步数: %d\n", step_count);

    return 0;
}

总结

通过上述代码，可以轻松实现以下功能：

1. 解决汉诺塔问题。
2. 输出每一步的移动过程。
3. 统计总移动步数。