对于斐波那契数列的求解过程的几种方法的比较
（1）最基本的方法：递归实现，使用公式为f[n] = f[n-1] + f[n-2];递归
结束条件是f[1]=1，f[2]=1。
（2）数组实现：空间复杂度和时间复杂度都是O（N），效率一般，比递归来
的快。
（3）vector<int>实现，时间复杂度是O(N)，空间复杂度O(1)，但是不知道
效率会高不高，当然vector有自己的属性会占用资源。
（4）queue<int>实现，当然队列数组更适合实现斐波那契数列，时间复杂度
和空间复杂度和vector一样。但是queue太合适这里了，
f(n)=f(n-1)+f(n-2)，f(n)只和f(n-1)和f(n-2)有关，f(n)入队列后，f(n-
2)就可以出队列了。
（5）迭代实现：迭代效率最高，时间复杂度是O(N)，空间复杂度是O(1)，
（6）百度的提供的一种公式法。 由于double类型的精度还不够，所以程
序算出来的结果会有误差，如果把公式展开计算，得出的结果就是正确的。
具体代码如下：
//递归
int fib1(int num)
{
if(num<1)
return -1;
if(num == 1 || num == 2)
return 1;
return f(n-1)+f(n-2);
}
//数组实现
int fib2(int num)
{
if(num<1)
return -1;
if(num<3)
{
return 1;
}
int *a = new int[num];
a[0] = a[1] = 1;
for(int i = 2;i<num;i++)
a[i] = a[i-1] + a[i-2];
int ret = a[num-1];
delete[] a;
return ret;
}
//vector<int>
int fib3(int num)
{
if(num<1)
return -1;
vector<int>a(2,1);
a.reserve(3);
for(int i = 2;i<num;i++)
{
a.insert(a.begin(),a.at(0)+a.at(1));
a.pop_back();
}
return a.at(0);
}
//queue<int>实现
int fib4(int num)
{
if(num<1)
return -1;
queue<int>q;
q.push(1);
q.push(1);
for(int i = 2;i<num;i++)
{
q.push(q.front()+q.back());
q.pop();
}
return q.pop();
}
//迭代实现
int fib5(int num)
{
int i,a=1,b = 1,c = 1;
if(num<1)
return -1;
for(i = 2;i<num;i++)
{
c= a + b;
a = b;
b = c;
}
return c;
}
//公式实现
int fib6(int num)
{
double gh = sqrt((double)5);
return pow(1+(1+gh),n-pow(1-gh))/(pow((double)2,n)*gh);
}
posted on 2011-10-26 17:46
mengkai 阅读(892)
评论(0) 编辑 收藏 引用 所属分类:
algorithm