猴子爬山
//猴子爬山n级,一步跨1级或3级台阶
#include<stdio.h>
voidmain()
{intk,n;longf[1000];
printf("请输入台阶总数n:");
scanf("%d",&n);
f[1]=1;f[2]=1;f[3]=2;//数组元素赋初值
for(k=4;k<=n;k++)
f[k]=f[k-1]+f[k-3];//按递推关系实施递推
printf("s=%ld",f[n]);
}
//分级递推
#include<stdio.h>
voidmain()
{inti,j,k,m,n,t,x[10];
longf[200];
printf("请输入总台阶数:");
scanf("%d",&n);//输入台阶数
printf("一次有几种跳法:");
scanf("%d",&m);
printf("请从小到大输入一步跳几级。\n");
for(i=1;i<=m;i++) //输入m个一步跳级数
{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++)
for(t=x[k]+1;t<=x[k+1];t++)
{f[t]=0;
for(j=1;j<=k;j++) //按公式累加实现分级
f[t]=f[t]+f[t-x[j]];
if(t==x[k+1]) //t=x(k+1)时增1
f[t]=f[t]+1;
}
printf("共有不同的跳法种数为:");
printf("%d(%d",n,x[1]); //按指定格式输出结果
for(i=2;i<=m;i++)
printf(",%d",x[i]);
printf(")=%ld.\n",f[n]-1);
}
优质内容筛选与推荐>>