猴子爬山问题：猴子每次跳一步或者三步，要上一个n阶的小山可选择的方案种数。

狸花鼠

猴子爬山问题：猴子每次跳一步或者三步，要上一个n阶的小山可选择的方案种数。
#include<stdio.h>
int main()
{
        int n,i,f1,f2,f3,f4;
        scanf("%d",&n);
        f1=1;f2=1;f3=2;
        for(i=4;i<=n;i++)
        {
                f4=f3+f1;
                f1=f2;
                f2=f3;
                f3=f4;
        }
        printf("%d\n",f4);
        return 0;
}
红色这段是答案，但是我看不懂为什么是这种算法。有大佬能解释下吗。

ba21

先把你的题意说清楚再来问吧

狸花鼠

ba21 发表于 2019-11-18 18:12
先把你的题意说清楚再来问吧

就是为什么是这种算法

ba21

狸花鼠 发表于 2019-11-18 19:08
就是为什么是这种算法

猴子每次跳一步或者三步，要上一个n阶的小山可选择的方案种数？
你这是要说什么？？？？？？？？？？？？？？？？？？？？？

狸花鼠

ba21 发表于 2019-11-18 19:13
猴子每次跳一步或者三步，要上一个n阶的小山可选择的方案种数？
你这是要说什么？？？？？？？？？？？ ...

比如说n是4，猴子上山的方式就有1111，13，31这三种方案

ba21

狸花鼠 发表于 2019-11-20 10:21
比如说n是4，猴子上山的方式就有1111，13，31这三种方案

对于你这个问题，无耐只好上网找了下相关资料。
人家的题目是这么说的：一个猴子在一座不超过30级的小山上爬山跳跃，猴子上山一步可跳1级或跳3级，试求上山有多少种不同的爬法；当然这个30可以是n。

你的提供代码使用了算法。
设爬n级台阶的不同爬法有f(n)种？
则：
f(1) = 1; 即  1=1
f(2) = 1; 即  2=1+1
f(3) = 2; 即  3=1+1+1; 3
f(4) = 3; 即  4=1+1+1+1;  3+1;  1+3 ( f(4)=f(3) + f(1) )
也就是f(n)=f(n-1)+f(n-3);

代码中 初始化   f1=1; f2=1; f3=2; 也就是说小于等于3阶的你都初始化好了，所以计算是从4开始 i = 4
然后根据上面的运算法则
                f4=f3+f1; // 算得f4 f(n)=f(n-1)+f(n-3);
                f1=f2; // 依次重新初始化f1 第1次循环这个f1也就是f(4)
                f2=f3; // 依次重新初始化f2 第1次循环这个f2也就是f(5)
                f3=f4; // 依次重新初始化f3 第1次循环这个f2也就是f(6)

狸花鼠

ba21 发表于 2019-11-20 18:46
对于你这个问题，无耐只好上网找了下相关资料。
人家的题目是这么说的：一个猴子在一座不超过30级的小 ...

emmmm先还是要谢谢你，但是那个f(n)=f(n-1)+f(n-3)这个式子的推导我还没懂。。。。。。

ba21

狸花鼠 发表于 2019-11-20 22:33
emmmm先还是要谢谢你，但是那个f(n)=f(n-1)+f(n-3)这个式子的推导我还没懂。。。。。。

n=5
f(n)=f(n-1)+f(n-3) //把n带进去你不会？

狸花鼠

ba21 发表于 2019-11-20 22:37
n=5
f(n)=f(n-1)+f(n-3) //把n带进去你不会？

好吧，谢谢你了