/*
* 求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");
}