递推之猴子爬山

递推是利用问题本身所具有的递推关系求解问题的方法。所谓递推，是在命题归纳时，可以由数量分别为n-k,…,n-1的情形推得数量为n的情形，或者反过来由数量分别为i+k,…,i+1的情形推出数量为i的情形。
我们大家比较熟悉的应该就是斐波那契数列了；这里给大家讲一下稍微复杂一点的递推——猴子爬山问题。

一个猴子在一座有30级台阶的小山坡上跳跃，猴子一步可以跳跃1级或者3级，试求上山一共有多少种不同的走法？

设爬k级台阶的不同爬法有f(k)种，
(1)寻找f(k)的递推关系。上山最后一步到达第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);

(2)确定初始条件
f(1)=1;
f(2)=2;
f(3)=2;

(3)code如下：

int main()
{
int k,n;
long f[1000];
printf("请输入台阶总数n:");
scanf("%d",&n);
f[1]=1;
f[2]=2;
f[3]=3;
for(int k=4;k<=n;k++)
  f[k]=f[k-1]+f[k-3];
printf("s=%1d",f[n]);
}

问题引申：设爬n级台阶，一步有m种跨法，一步跨多少级均从键盘输入，求共有多少种不同的爬法。

这是一个分级递推问题，设爬山t级台阶的不同爬法为f(t)，从键盘输入的m个整数分别为x(1),x(2),x(3),.........,x(m)    (约定x(1)<x(2)<...x(m)<n)

首先探讨f(t)的递推关系：
   当t<x(1)时，f(t)=0，f(x(1))=1  (初始条件）
   当x(1)<t<=x(2)时，第1级递推，f(t)=f(t-x(1))
   当x(2)<t<=x(3)时，第2级递推，f(t)=f(t-x(1))+f(t-x(2))
   .......
   一般地，当x(k)<t<=x(k+1)，k=1,2,,...,m-1, 有第k级递推：
     f(t)=f(t-x(1))+f(t-x(2))+....+f(t-x(k))
  当x(m)<t时，有第m级递推：
     f(t)=f(t-x(1))+f(t-x(2))+...+f(t-x(m))
  当t=x(2)或x(3)...x(m)时，还要加1，因为t本身就是一个一步到位的爬法，则 f(t)=f(t)+1;
  我们所求的目标就是
     f(n)=f(n-x(1))+f(n-x(2))+...+f(n-x(m))
再设计递推的过程中可以把台阶数记为数组x(m+1)


main()
{
int i,j,k,m,n,t,x[10];
long f[200];
printf("请输入总台阶数n:");
scamf("%d",&n);
printf("一次有几种跳法:");
scanf("%d",&m);
printf("请从小到大输入一步跳几级.n");
for(i=1;i<=m;i++)
{
printf("第%d个一步可以跳级数:",i);
scanf("%d",&x[i]);
}
for(i=1;i<=x[1]-1;i++) 
f[i]=0;  //确定初始条件
x[m+1]=n;
f[x[1]]=1; //初始条件
for(k=1;k<=m;k++)  //一共m种爬法，实现对每一种爬法的累加
for(t=x[k]+1;t<=x[m+1];t++)
{
f[t]=0;
for(j=1;j<=k;j++)
f[t]=f[t]+f[t-x[j]];//按公式实现累加
if(t==x[m+1])
f[t]=f[t]+1;
}
printf("共有不同的爬法种数为:%d",f[n]-1);  //因为用到了x[m+1],将他也看成了一步走法，所以减1

最后

以上就是简单手套为你收集整理的递推之猴子爬山的全部内容，希望文章能够帮你解决递推之猴子爬山所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。