5、猴子跳台阶问题 有一只猴子可以向上跳1个台阶，也可以向上跳2个台阶，还可以向上跳3个台阶，有n个台阶，猴子从第1个台阶跳到第n个台阶共有多少种跳法。通过键盘输入台阶数，通过动态规划算法计算出有多少种跳法。C语言

实现如下：

#include <stdio.h>

int main()
{
int n, i;
printf("请输入台阶数：");
scanf("%d", &n);

int dp[n+1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(i=3; i<=n; i++)
{
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}

printf("共有%d种跳法。\n", dp[n]);
return 0;
}

首先，定义一个数组dp，其中dp[i]表示从第1个台阶跳到第i个台阶的跳法数。

由题意可知，当n=1时，猴子只能跳1个台阶，所以dp[1]=1；当n=2时，猴子可以跳1个台阶或者跳2个台阶，所以dp[2]=2；当n=3时，猴子可以跳1个台阶或者跳2个台阶或者跳3个台阶，所以dp[3]=4。

接下来，我们可以通过动态规划的思想，计算出dp数组中其余元素的值。具体地，对于任意的i(4<=i<=n)，有dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。即猴子从第i-1个台阶、第i-2个台阶或者第i-3个台阶跳上第i个台阶的跳法数之和。

最后，输出dp[n]即可得到答案。

相关问题

有一只猴子可以向上跳1个台阶，也可以向上跳2个台阶，还可以向上跳3个台阶，有n个台阶，猴子从第1个台阶跳到第n个台阶共有多少种跳法。通过键盘输入台阶数，通过动态规划算法计算出有多少种跳法。c语言

实现如下：

#include <stdio.h>

int main() {
    int n, i;
    printf("请输入台阶数：");
    scanf("%d", &n);
    int f[n + 1];
    f[0] = 1; // 初始化
    f[1] = 1;
    f[2] = 2;
    for (i = 3; i <= n; i++) {
        f[i] = f[i - 1] + f[i - 2] + f[i - 3]; // 状态转移方程
    }
    printf("共有%d种跳法\n", f[n]);
    return 0;
}

在这个程序中，我们定义了一个数组f来保存每个台阶的跳法数。由于猴子可以跳1个、2个、或者3个台阶，所以我们可以使用状态转移方程f[i] = f[i - 1] + f[i - 2] + f[i - 3]来计算出i个台阶的跳法数。

同时，我们也需要初始化f[0] = 1、f[1] = 1、f[2] = 2这三个值，因为这是状态转移方程的前提条件。

最后，我们输出f[n]，即为猴子从第1个台阶跳到第n个台阶共有多少种跳法。

用c语言中的迭代算法写猴子跳台阶的问题：有一只淘气的猴子一次可以跳1个台阶，也可以一次跳2个台阶，还以一次跳3个台阶，现有n个台阶，猴子从第1台阶跳到第n个台阶总共有多少种跳法。

以下是用 C 语言编写的迭代算法：

#include <stdio.h>

int main() {
    int n, i;
    int a = 1, b = 2, c = 4, d; // 初始化 a、b、c，表示跳到第 1、2、3 个台阶的跳法数量
    printf("请输入台阶数 n：");
    scanf("%d", &n);
    if (n == 1) { // 只有一个台阶时，只有一种跳法
        printf("共 %d 种跳法\n", a);
        return 0;
    }
    if (n == 2) { // 两个台阶时，有两种跳法
        printf("共 %d 种跳法\n", b);
        return 0;
    }
    if (n == 3) { // 三个台阶时，有四种跳法
        printf("共 %d 种跳法\n", c);
        return 0;
    }
    for (i = 4; i <= n; i++) { // 从第 4 个台阶开始计算跳法数量
        d = a + b + c; // 计算跳到第 i 个台阶的跳法数量
        a = b; // 更新 a、b、c 的值
        b = c;
        c = d;
    }
    printf("共 %d 种跳法\n", d); // 输出跳法数量
    return 0;
}

代码思路：先初始化跳到第 1、2、3 个台阶的跳法数量，然后从第 4 个台阶开始计算跳法数量。用变量 a、b、c 分别表示跳到第 i-2、i-1、i 个台阶的跳法数量，每次计算跳到第 i 个台阶的跳法数量时，将 a、b、c 的值更新为 b、c、d，最后输出 d 即可。注意特判 n=1、2、3 的情况。