C 语言搞定汉诺塔问题：算法、程序及时空复杂度揭秘

以下是用 C 语言解决汉诺塔问题的程序： ```c #include <stdio.h> // 移动盘子的函数 void hanoi(int n, char from_rod, char to_rod, char aux_rod) { if (n == 1) { printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod); return; } hanoi(n - 1, from_rod, aux_rod, to_rod); printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod); hanoi(n - 1, aux_rod, to_rod, from_rod); } int main() { int n = 3; // 要移动的盘子数量，可修改 hanoi(n, 'A', 'C', 'B'); return 0; } ``` 汉诺塔问题的时间复杂度为 $O(2^n)$ ，空间复杂度为 $O(n)$ 。这是因为汉诺塔问题的递归调用次数呈现指数增长，而递归调用栈的深度最大为盘子的数量 $n$ 。 ######[AI写代码神器 | 275点数解答 | 2024-11-08 12:44:23]