猴子爬山—递推算法（图文详解）
题目描述
一个猴子在一座不超过30级的小山上爬山跳跃，猴子上山一步可跳1级或跳3级，试求上山有多少种不同的爬法。
样例输入
30
样例输出
58425
解题思路：
- 首先探求f[k]递推关系 设n=30，上山最后一步到达第30级台阶，完成上山，共有f[30]种不同的爬法；到第30级之前位于哪一级呢？第一种是位于第29级（上跳1级即到），有f[29]种；第二种于第27级(上跳3级即到)，有f[27]种；于是有： f[30]=f[29]+f[27] 依此类推，一般地有递推关系： f[k]=f[k-1]+f[k-3] （k>3）
- 确定初始条件 f[1]=1；即1=1 f[2]=1；即2=1+1 f[3]=2；即3=1+1+1；3=3
- 实施递推 根据以上递推关系与初始条件，设置一重循环应用递推即可求出f[n]。
代码部分
#include<stdio.h>
long fun(int n)
{
long key;
if(n==1)
key=1;
else if(n==2)
key=1;
else if(n==3)
key=2;
else
key=fun(n-1)+fun(n-3);
return key;
}
int main()
{
int m;
long result;
scanf("%d",&m);
result=fun(m);
printf("%ld",result);
return 0;
}
这道题关键是在于理解题目中的递推关系，根据递推关系和初始条件进行求解。
下一篇：
判断链表中是否有环（C语言）