//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;
}
评论