7种方式实现斐波那契数列

  1. 云栖社区>
  2. 博客>
  3. 正文

7种方式实现斐波那契数列

长征2号 2017-11-16 19:27:00 浏览622
展开阅读全文

7种方式实现斐波那契数列

一:递归实现
   在学校里学习递归的时候,老师就喜欢举斐波那契这个例子,看!多简洁清晰。其实这个例子是非常不适合作为递归举例的,
   原因就是效率太慢,除了最后一个数,每个数都被算了一遍又一遍,时间复杂度差不多是5n^2/3。
二:数组实现
   空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快。
三:vector<int>实现
   时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源。
四:queue<int>实现
   当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int>一样,但队列太适合这里了,
   f(n)=f(n-1)+f(n-2),f(n)只和f(n-1)和f(n-2)有关,前面的数就乖乖的出队列吧。
五:迭代实现
   迭代实现是最高效的,在学习斐波那契数列时,介绍了这个方法,当时不知道懂了没有,时间复杂度是0(n),时间复杂度是0(1)。
六:最难懂的实现方式
   说他难懂是因为变量的命名,怎么啊,不行啊,其实就是用迭代实现的,哈哈哈...
七:公式实现
 我靠!原来斐波那契数列有公式啊,那老师干嘛不直接教我们公式呢,教你公式,当然要告诉你推导啊,我不会,看(百度百科)斐波那契数列.
       由于double类型的精度还不够,所以程序算出来的结果有误差,如果把公式展开计算,得出的结果是正确的。

 请不要说陈太汉无聊,无聊时玩玩代码也不错。

复制代码
int Fib1(int index)
{
if(index<1)
{
return-1;
}
if(index==1|| index==2)
{
return1;
}
return Fib1(index-1)+Fib1(index-2);
}
复制代码
复制代码
int Fib2(int index)
{
if(index<1)
{
return-1;
}
if(index<3)
{
return1;
}
int*a=newint[index];
*a=*(a+1)=1;
for(int i=2;i<index;i++)
{
a[i]
=a[i-1]+a[i-2];
}
int res=a[index-1];
delete a;
//释放内存(一个new对应一个delete)
return res;
}
复制代码
复制代码
int Fib3(int index)
{
if(index<1)
{
return-1;
}
// Create a vector a with 2 elements of value 1
vector<int> a(2,1);
a.reserve(
3);
for(int i=2;i<index;i++)
{
a.insert(a.begin(),a.at(
0)+a.at(1));
a.pop_back();
}
return a.at(0);
}
复制代码
复制代码
int Fib4(int index)
{
if(index<1)
{
return-1;
}
queue
<int> a;
a.push(
1);
a.push(
1);
for(int i=2;i<index;i++)
{
a.push(a.front()
+a.back());
a.pop();
}
return a.back();
}
复制代码
复制代码
int Fib5(int index)
{
if(index<1)
{
return-1;
}

int a1=1,a2=1,a3=1;
for(int i=0;i<index-2;i++)
{
a3
=a1+a2;
a1
=a2;
a2
=a3;
}
return a3;
}
复制代码
复制代码
int Fib6(int _1_)
{
if(_1_<1)
{
return-1;
}
int _=1,__=1,___=1;
for(int i=2;i<_1_;i++)
{
___
=_+__;
_
=__;
__
=___;
}
return ___;
}
复制代码
int Fib7(int n)
{
double gh5=sqrt((double)5);
return (pow((1+gh5),n)-pow((1-gh5),n))/(pow((double)2,n)*gh5);
}

网友评论

登录后评论
0/500
评论
长征2号
+ 关注