1.17.c

来自「部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)」· C语言 代码 · 共 33 行

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 temp[200],i,j,sum;
  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++) temp[i]=0;
    temp[k-1]=1;                      //初始化
    for(i=k;i<=m;i++)                 //求出序列第k至第m个元素的值
    {
      sum=0;
      for(j=i-k;j<=i-1;j++) sum+=temp[j];
      temp[i]=sum;
    }
    f=temp[m];
  }
  return OK;

}