加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

已知k阶裴波那契序列的定义为 f0=0, f1=0, ..., fk-2=0, fk-1=1; fn=fn

(2015-10-04 12:04:26)
标签:

it

程序

算法

斐波那契数

分类: 编程笔记

【题目】已知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均以值调用的形式在函数参数表中出现。
**********/

对于初次接触这个序列的同学来说,可能一时难以理解这个序列。
举例说明:
(1)K=2时,即2阶裴波那契序列定义为:
f0=0, f1=1;
f2=f1+f0,
f3=f2+f1,
f4=f3+f2,
.....
(2)k=3时,即3阶裴波那契序列定义为:
f0=0, f1=0,f2=1;
f3=f2+f1+f0,
f4=f3+f2+f1,
f5=f4+f3+f2,
.....

Status Fibonacci(int k, int m, int &f) 

{
   int t[100],i,j,sum;
   if(k<=1||m<0) return ERROR;//没有1阶的这个序列,m不能为负;
   if(m

   else if(m==k-1) f=1; //k的第k-1项都是1
   else
      {for(i=0;i<=k-2;i++)   //初始化k阶的第0项到k-2项都是0,k的第k-1项都是1;
         t[i]=0; 
       t[k-1]=1;  
       for(i=k;i<=m;i++) //从第k项开始遍历,第k项值为前k项之和;之后的每一项都会计算它的前面k项之和
         { sum=0; //初始化,用于统计该项的前面k项
           for(j=i-k;j<=i;j++)   //循环遍历该项前面的K项,然后累加放在sum中
              sum+=t[j]; 
           t[i]=sum;   //将 i 项前面k个数统计的结果赋值给数组的第 i 项;
         
        f=t[m];  //这是第M项统计前面k项之和后的结果;
       
   return OK;
}

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有