猴子爬山问题 C语言求解

///////////////////////////////////////////////////////////////////////////////////////////////////// // 猴子爬山问题 // // 一顽猴在一座有30级台阶的小山上爬山跳跃，猴子上山一步可跳1级，或3跳级，试求上山的30级台阶 // // 有多少种不同的走法？ // // 解：设爬上k级台阶的不同走法为f(k)种。 // // 则 f(30)=f(29)+f(27) // // 得到递推关系: f(k)=f(k-1)+f(k-3) k>3 // // 初始条件： f(1)=1 // // f(2)=1 // // f(3)=2 // // 设有n级台阶，步有m种跨法，分别为x1,x2,...,xm.求跨上n级台阶总的跨法数f(n)? // // 为方便处理令 x[m+1]=n; // // 当t<x1时， f(t)=0; f(x1)=1; // // 当x1<t<=x2时,f(t)=f(t-x1) if(t==x2) f(t)++; // // 当x2<t<=x3时,f(t)=f(t-x1)+f(t-x2) if(t==x3) f(t)++; // // 当x3<t<=x4时,f(t)=f(t-x1)+f(t-x2)+f(t-x3) if(t==x4) f(t)++; // // ...一般地， // // 当xm<t<x(m+1)时,f(t)=f(t-x1)+...+f(t-xm) if(t==x(m+1) f(t)++; // // 最后f(n)应减1。 // ///////////////////////////////////////////////////////////////////////////////////////////////////// #include<stdio.h> #define M 10 #define N 100 long Methods(long *f,int *x,int n,int m) { int i,j=x[1],k; x[m+1]=n; for(i=1;i<x[1];i++) //求 t<x1 f[i]=0; f[x[1]]=1; for(i=1;i<=m;i++) //分区段求f(k)，x1<...<x2<...<x3<...<...<xm<....<x(m+1) for(j=x[i]+1;j<=x[i+1];j++) { f[j]=0; for(k=1;k<=i;k++) // 当xm<t<x(m+1)时, f(t)=f(t-x1)+...+f(t-xm) f[j]+=f[j-x[k]]; // 当(t==x(m+1)时， f(t)++; if(j==x[i+1]) f[j]++; } return f[n]-1; //f(n)减1!!! } void main() { int i,stages,moves; int steps[M]; long way[N]; printf("Enter the stages: "); scanf("%d",&stages); printf("Enter the moves: "); scanf("%d",&moves); printf("Enter the step from small to large jump several stages:\n"); for(i=1;i<=moves;i++) scanf("%d",&steps[i]); printf("The overall method is %d\n",Methods(way,steps,stages,moves)); }