/*
上阶梯，你可以一个一个阶梯上，也可以两个两个地来，
也可以一个和二个间隔着上，甚至可以一次k个阶梯
问题是，上一个阶梯数为n，每步能上1至k个阶的话，
你有多少种方法走完它？

如 n = 5 , k = 2，可以
1,1,1,1,1
2,1,1,1
1,2,1,1
1,1,2,1
1,1,1,2
2,2,1
2,1,2
1,2,2
共8种

输入阶梯数n(1 <= n <= 30)和每步最大阶数k(1<=k<=n)：
5 2
5 3

输出：
8
13

难度：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;
}

评论