// 猴子爬山n级，一步跨1级或3级台阶 

#include<stdio.h>

void main()

{ int k,n;  long f[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>

void main()

{ int i,j,k,m,n,t,x[10]; 

  long f[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);

  }