/*上阶梯，你可以一个一个阶梯上，也可以两个两个地来，也可以一个和二个间隔着上，甚至可以一次k个阶梯问题是，上一个阶梯数为n，每步能上1至k个阶的话，你有多少种方法走完它？如 n = 5 , k = 2，可以1,1,1,1,12,1,1,11,2,1,11,1,2,11,1,1,22,2,12,1,21,2,2共8种输入阶梯数n(1 <= n <= 30)和每步最大阶数k(1<=k<=n)：5 25 3输出：813难度：Easy*/#include <stdio.h>#include <conio.h>#define MAX 300 int a[MAX];int in_step,in_total;  //in_step为最大步长即每次最多跨几个台阶,in_total为台阶总数int count=0;   //统计成功次数 void fun(int index){ int sum=0;   for (int i=1;i<=in_step;i++) {  a[a[0]]=i;   for (int j=1;j<=a[0];j++)   sum+=a[j];   if (sum==in_total)  {   count++;   a[a[0]--]=0;    for (a[0];a[a[0]]==in_step;a[0]--)    //如果a[a[0]]已达到最大步长则清0    a[a[0]]=0;    sum=0;   break;  }   if (sum>in_total)  {   a[a[0]--]=0;   sum=0;   break;   }   if (sum<in_total)   fun(a[0]=a[0]+1);  sum=0; }} int main(){  while (scanf("%d %d",&in_total,&in_step)!=EOF) {  a[0]=1;  fun (a[0]);  printf("%d\n",count);  count=0; }  getch(); return 0;}

评论