面试题：C语言递归解决汉诺塔问题

Question

汉诺塔问题是一个经典的递归问题。假设有三根柱子A、B、C，在A柱上有n个大小不同的圆盘，按照从小到大的顺序叠放。要求将所有圆盘从A柱移动到C柱，每次只能移动一个圆盘，且在移动过程中，大圆盘不能放在小圆盘上面。请用C语言编写递归函数解决这个问题，并分析该递归算法的时间复杂度。

Answer 1

#include <stdio.h>

// 递归函数解决汉诺塔问题
void hanoi(int n, char source, char auxiliary, char target) {
    if (n > 0) {
        // 将n - 1个圆盘从source移动到auxiliary
        hanoi(n - 1, source, target, auxiliary);
        // 将第n个圆盘从source移动到target
        printf("Move disk %d from %c to %c\n", n, source, target);
        // 将n - 1个圆盘从auxiliary移动到target
        hanoi(n - 1, auxiliary, source, target);
    }
}

int main() {
    int n = 3; // 假设有3个圆盘
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

时间复杂度分析

设移动 n 个圆盘所需的时间为 T(n)。

1. 第一步，将 n - 1 个圆盘从 source 移动到 auxiliary，所需时间为 T(n - 1)。
2. 第二步，将第 n 个圆盘从 source 移动到 target，所需时间为常数时间，记为 O(1)。
3. 第三步，将 n - 1 个圆盘从 auxiliary 移动到 target，所需时间为 T(n - 1)。

因此，T(n) = 2T(n - 1) + O(1)。

根据递归式求解，可得 T(n) = 2^n - 1，所以汉诺塔递归算法的时间复杂度为 O(2^n)。