登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

秒大刀 博客

好好学习 天天向上

 
 
 

日志

 
 
 
 

k阶费波那切数列  

2006-02-23 22:03:14|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

//完成时间2005/02/26
#include<cassert>
#include<iostream>
 
class FB
{
private:
    unsigned * pspace;//
    int m,k;
public:
    FB():pspace(NULL),m(0),k(0)
    {
    };
    FB(unsigned K,unsigned M):m(M),k(K)
    {
           assert(k>=2&&"必须保证k>=2,否则根据题目要求将产生不可预料结果");
           pspace=new unsigned[m+1];
           calculate();
    };
    ~FB()
    {
           delete pspace;
    };
public:
    int Get()
    {
           return pspace[m];
    };
    int Get(int M)
    {
           assert(M<=m&&"这里的询问不能超出初始化的范围");
           if(M<0)
                  return 0;
           else
                  return pspace[M];
    };
private:
    int calculate()//按照题目的描述计算出结果,存入pspace
           //事先分配好要用的空间,然后在空间上计算,结果存入相应的位置
           //查询时只将其简单的输出
    {
           for(int i(0);i<k-1;++i)//前面0的填充
           {
                  pspace[i]=0;
           }
           pspace[i++]=1;
           pspace[i++]=1;
           for(; i<=m; ++i)//后面数据的填入
           {
                  pspace[i]=0;
                  for(int j(1);j<=k;++j)
                  {
                         pspace[i]+=Get(i-j);
                  }
           }
           return 0;
    };
};

//以下为测试函数
using namespace std;
int main()
{
    while(1)
    {
           int k,m;
           cout<<"请输入k(阶数)<输入0可退出>: "<<std::flush;
           cin>>k;
           if(k==0)
                  break;
           cout<<"请输入m(项数): "<<std::flush;
           cin>>m;

           FB fb(k,m);
           cout<<endl<<k<<"阶费波那切数列的第"<<m<<"项的值为:"<<fb.Get(m)<<endl
                  <<"-----------------------------------"<<endl;
           //以下为调试时用来观察全部取值的
           /*cout<<endl<<"k="<<k<<"\t\tm="<<m<<endl;
           for(int i(0);i<=m;++i)
           {
           (i+1)%5?cout<<fb.Get(i)<<'\t':cout<<fb.Get(i)<<"\t-----> "<<i+1<<endl;
           }
           cout<<endl<<"THE END"<<endl;*/
    }
   return 0;
}

  评论这张
 
阅读(1288)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018