已知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阶斐波那契序列的第n项值的函数算法,k和n均以值调用的形式在函数参数表中出现。
代码如下:
int fibonacci(int k,int n) { int *p,x,i,j; if(k<1) exit(OVERFLOW); p=new int[k+1]; if(!p) exit(OVERFLOW); for(i=0;i<k+1;++i) { if(i<k-1) p[i]=0; else p[i]=1; } for(i=k+1;i<=n;++i) { x=p[0]; for(j=0;j<k;++j) p[j]=p[j+1]; p[k]=2*p[k-1]-x; } return p[k]; }
这里用到了下面的推理:
f(n)=f(n-1)+f(n-2)+...+f(n-k)=f(n-1)+f(n-1)-f(n-k-1)=2f(n-1)-f(n-k-1);
所以只需要求出第n-1项以及n-k-1项便能求出第n项,此算法时间复杂度为O( (n-k)k ),只需O(k)空间。