C语言递归之汉诺塔和青蛙跳台阶问题

下面是详细讲解“C语言递归之汉诺塔和青蛙跳台阶问题”的完整攻略。

汉诺塔

问题描述

汉诺塔是经典的递归问题，它的问题描述如下：

有三个杆子 A、B 和 C，其中 A 杆上有 N 个大小不一的圆盘，现在我们需要将这些圆盘从 A 杆移到 C 杆。每次只能移动一个圆盘，且大的圆盘不能放在小的圆盘上面。

解题方法

求解汉诺塔问题的方法可以分为三个步骤：

1. 将 A 杆上的 N-1 个圆盘移动到 B 杆上（递归调用）；
2. 将 A 杆上的第 N 个圆盘移动到 C 杆上；
3. 将 B 杆上的 N-1 个圆盘移动到 C 杆上（递归调用）。

这三个步骤就是汉诺塔问题的解题方法，它们可以用递归的方式来实现。具体代码实现如下：

void hanoi(int n, char a, char b, char c) {
    if (n == 1) { // 只有一个圆盘时，直接将其从 a 移动到 c
        printf("Move disk 1 from %c to %c\n", a, c);
    } else { // 有多个圆盘时
        hanoi(n - 1, a, c, b); // 将 a 上的 n - 1 个圆盘移动到 b 上
        printf("Move disk %d from %c to %c\n", n, a, c); // 将 a 上的第 n 个圆盘移动到 c 上
        hanoi(n - 1, b, a, c); // 将 b 上的 n - 1 个圆盘移动到 c 上
    }
}

示例说明

假设有 3 个圆盘，初始状态如下：

A: 3 2 1
B: 
C: 

调用 hanoi(3, 'A', 'B', 'C') 方法后，输出结果如下：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

移动的过程可以通过画图来帮助理解。在上面的过程中，每次只移动一个圆盘，且大的圆盘不能放在小的圆盘上面，符合汉诺塔问题的要求。

青蛙跳台阶问题

问题描述

青蛙跳台阶是一个经典的递归问题，它的问题描述如下：

一只青蛙要跳上 N 级的台阶，每次只能跳 1 级或 2 级，求这只青蛙跳上这 N 级台阶的方法数。

解题方法

对于这个问题，可以将 N 级台阶时的跳法看成是前面 N-1 级台阶时的跳法数与前面 N-2 级台阶时的跳法数之和，即：

f(N) = f(N-1) + f(N-2)

问题的结束条件是青蛙跳到了第 1 或 2 级台阶，此时结束递归，返回的结果是 1，因为此时只有一种跳法。

以下是具体的代码实现：

int jump_floor(int n) {
    if (n == 1 || n == 2) { // 站在第 1 级或第 2 级台阶时，只有一种跳法
        return 1;
    } else { // 站在第 n 级台阶时，有 f(n-1) + f(n-2) 种跳法
        return jump_floor(n - 1) + jump_floor(n - 2);
    }
}

示例说明

假设有 5 级台阶，调用 jump_floor(5) 方法后，得到的结果为：

8

这意味着青蛙跳上第 5 级台阶的方法数为 8 种。

再假设有 6 级台阶，调用 jump_floor(6) 方法后，得到的结果为：

13

这意味着青蛙跳上第 6 级台阶的方法数为 13 种。

通过这个方法可以得到任意级数的跳法数量，这就是青蛙跳台阶问题的解决方法。