/*
* 求k阶Fibonacci序列的第m项的值f,O(m^2)
* Fibonacci数列: 数字0, 1，1，2，3，5，8－－－构成了一个序列。这个数列前面相邻两项之和，构成了后一项.
* K阶Fibonacci数列的前K-1项均为0,第k项为1,以后的每一项都是前K项的和.
*/
#include<stdio.h>
#define MAX_LENGTH 50 //k,m<50
void main()
{
int temp[MAX_LENGTH];
int k,m,f; //k阶Fibonacci数列,第m项,值为f
int i,j,sum;
scanf("%d,%d",&k,&m);
if(k < 2 || m < 0)
return;
if(m < k-1)
f = 0;
else if(m == k-1)
f = 1;
else
{
//初始化
for(i = 0; i <= k-2; i++)
temp[i] = 0;
temp[k-1] = 1;
for(i = k; i <= m; i++) //求出序列第k至第m个元素的值
{
sum = 0;
for(j = i-k; j < i; j++) sum += temp[j];
temp[i] = sum;
}
f = temp[m];
}
printf("%d\n",f);
system("pause");
}