/*
* 求k階Fibonacci序列的第m項(xiàng)的值f,O(m^2)
* Fibonacci數(shù)列: 數(shù)字0, 1，1，2，3，5，8－－－構(gòu)成了一個(gè)序列。這個(gè)數(shù)列前面相鄰兩項(xiàng)之和，構(gòu)成了后一項(xiàng).
* K階Fibonacci數(shù)列的前K-1項(xiàng)均為0,第k項(xiàng)為1,以后的每一項(xiàng)都是前K項(xiàng)的和.
*/
#include<stdio.h>
#define MAX_LENGTH 50 //k,m<50
void main()
{
int temp[MAX_LENGTH];
int k,m,f; //k階Fibonacci數(shù)列,第m項(xiàng),值為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個(gè)元素的值
{
sum = 0;
for(j = i-k; j < i; j++) sum += temp[j];
temp[i] = sum;
}
f = temp[m];
}
printf("%d\n",f);
system("pause");
}