已知k阶斐波那契序列的定义为
f(0)=0,f(1)=0,...f(k-2)=0,f(k-1)=1;
f(n)=f(n-1)+f(n-2)+...+f(n-k),n=k,k+1,...
试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。
k阶斐波那契序列定义：第k和k+1项为1，前k - 1项为0，从k项之后每一项都是前k项的和
如：k=2时，斐波那契序列为：0,1,1,2,3,5,...
k=3时，斐波那契序列为：0,0,1,1,2,4,7,13,...
算法一：数组法
判断m和k-1的大小，通过数组来存储斐波那契序列：
m<=k-1时，所有项均为0；
m>k-1时，前k-1项为0，k项之后的值通过循环和叠加依次写入数组，注意：数组中的下标从0开始；
#include <stdio.h>
#include <stdlib.h> int E[],f; //数列E用来存储斐波那契序列，f表示第m项的值
int Fibonacci(int k,int m){
int i,j,sum;
if (m<=k-) f=;
else {
for(i=;i<k-;i++)
E[i]=; //前k-1项为0
E[k-]=; //第k项为1
for(i=k;i<=m;i++){ //前k项的和
sum=;
for(j=i-k;j<=i;j++)
sum +=E[j];
E[i]=sum;
}
f=E[m-]; //第m项
}
}
int main() {
int k,m;
scanf("%d%d",&k,&m);
Fibonacci(k,m);
printf("%d",f);
system("PAUSE"); //防止程序运行结束后编辑窗口关闭，此函数包含在stblib.h中
return ;
}
方法二：递归法
由定义知递推公式：f(n)=f(n-1)+f(n-2)+...+f(n-k)
又：f(n-1)=f(n-2)+f(n-3)+...+f(n-k)+f(n-k-1) (n>k+1时成立）
由以上两式可得：f(n)=2f(n-1)-f(n-k-1) (n>k+1)
所以：
m<=k-1时,f(n)=0;
m=k,k+1时，f(n)=1;
m>k+1时，f(n)=2f(n-1)-f(n-k-1).
#include<stdio.h>
#include<stdlib.h> int Fibonacci(int k,int m){
if(m<=k-) return ;
else if((m==k)||(m==k+)) return ;
else return *Fibonacci(k,m-)-Fibonacci(k,m-k-); // m>k+1时,公式成立
}
int main(){
int k,m;
scanf("%d%d",&k,&m);
printf("%d",Fibonacci(k,m));
system("PAUSE");
}