猴子爬山问题：猴子每次跳一步或者三步，要上一个n阶的小山可选择的方案种数。
本帖最后由 狸花鼠 于 2019-11-18 19:09 编辑猴子爬山问题：猴子每次跳一步或者三步，要上一个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 发表于 2019-11-18 18:12
先把你的题意说清楚再来问吧
就是为什么是这种算法 狸花鼠 发表于 2019-11-18 19:08
就是为什么是这种算法
猴子每次跳一步或者三步，要上一个n阶的小山可选择的方案种数？
你这是要说什么？？？？？？？？？？？？？？？？？？？？？ ba21 发表于 2019-11-18 19:13
猴子每次跳一步或者三步，要上一个n阶的小山可选择的方案种数？
你这是要说什么？？？？？？？？？？？ ...
比如说n是4，猴子上山的方式就有1111，13，31这三种方案 本帖最后由 ba21 于 2019-11-20 18:51 编辑
狸花鼠 发表于 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)这个式子的推导我还没懂。。。。。。 狸花鼠 发表于 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带进去你不会？
好吧，谢谢你了
页:
[1]