對于斐波那契數列的求解過程的幾種方法的比較
（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 閱讀(922)
評論(0) 編輯 收藏 引用 所屬分類:
algorithm