如果我每一步迈上1个或两个台阶，先迈左脚，然后左右交换，最后一步迈右脚，也就是一共要走偶数步，
那么，上完39级台阶，有多少种不同的算法
1 #include "stdio.h" 2 int total=0;//计数 3 int Sum(int num,int step) 4 { 5 if(num<0) 6 return 0; 7 if(num==0&&step%2==0)//不管走的是左脚还是右脚，只要走的步数是偶数即可 8 { 9 total++; 10 return 0; 11 } 12 Sum(num-1,step+1); 13 Sum(num-2,step+1); 14 } 15 16 17 //首先我们用逆向的思维 其实上楼下楼在这道题没有太大区别 18 //然后 因为num-1无论还是-2都是在递归函数中 也无关左右脚 只要走的步数是偶数即可 19 //每次step都+1 20 int main(void) 21 { 22 int n; 23 printf("Enter n:"); 24 scanf("%d",&n); 25 Sum(n,0); //从顶部算 26 printf("Total=%d ",total); 27 return 0; 28 }
1 #include "stdio.h" 2 int total=0;//计数 3 int Sum(int num,int step) 4 { 5 if(num>39) 6 return 0; 7 if(num==39&&step%2==0)//不管走的是左脚还是右脚，只要走的步数是偶数即可 8 { 9 total++; 10 return 0; 11 } 12 Sum(num+1,step+1); 13 Sum(num+2,step+1); 14 } 15 int main(void) 16 { 17 Sum(0,0); //从底部算 18 printf("Total=%d ",total); 19 return 0; 20 }
非递归：
1 #include "stdio.h" 2 long fact(int m,int n) 3 { 4 int i; 5 double a,b,c;//因为阶乘数 m，n 稍大，阶乘结果变大 6 a=b=c=1; 7 printf("a=%.0f,b=%.0f,c=%.0f ",a,b,c); 8 for(i=m+n;i>=1;i--)//求 m+n 的阶乘 9 a=a*i; 10 for(i=m;i>=1;i--)//求 m 的阶乘 11 b=b*i; 12 for(i=n;i>=1;i--)//求 n 的阶乘 13 c=c*i; 14 return a/(b*c); 15 } 16 int main(void) 17 { 18 int i,j; 19 long sum=0; 20 for(i=1;i<=37;i++) 21 for(j=1;j<=19;j++) 22 { 23 if((i+j)%2==0&&(i+2*j)==39)//满足两只脚的走的总的步数为偶数且走的阶 24 梯数总和为 39 25 { 26 sum+=fact(i,j);//求总的组合数 27 printf("%d %d ",i,j);//输出两只脚的种类数 28 } 29 } 30 printf("%ld ",sum); 31 return 0; 32 }
这么写可能有人看不懂 大体说一下
从1 到40 实际上了39个台阶 （好比从1到2上了一个台阶 那么从1到40上了39个）
这其中 如果第一步确定了左脚右脚 最后一步随之确定 也就是说 这两种情况压缩成了一种确定的情况
第一步是左 脚 只迈一步 我们要循环37次 因为39次中 最开始一次和最后一次的情况完全确定 39-2
如果迈两步 38次是可变的 /2 = 19 所以循环19次 我们都遍历一遍 无非就是40*20的数量级罢了