1.17.txt

严蔚敏《数据结构(c语言版)习题集习题答案

1.17③ 已知k阶裴波那契序列的定义为
    f0=0,  f1=0,  ...,  fk-2=0,  fk-1=1;
    fn=fn-1+fn-2+...+fn-k,   n=k,k+1,...
试编写求k阶裴波那契序列的第m项值的函数算法，
k和m均以值调用的形式在函数参数表中出现。

要求实现下列函数：
Status Fibonacci(int k, int m, int &f);
/* 如果能求得k阶斐波那契序列的第m项的值f，则返回OK；*/
/* 否则（比如，参数k和m不合理）返回ERROR            */


Status Fibonacci(int k, int m, int &f) 
/* 求k阶斐波那契序列的第m项的值f    */
{ int a[100],sum,i,j;
 if(k<2||m<0) return ERROR;  
 if(m<k-1) f=0;  
 else if(m==k-1) f=1;  
 else  
 {for(i=0;i<=k-2;i++)  
  a[i]=0;
  a[k-1]=1;
  for(i=k;i<=m;i++)  
  { sum=0;  
   for(j=i-k;j<=i;j++)  
   sum+=a[j];
   a[i]=sum;
  }  
  f=a[m];