對于斐波那契數(shù)列的求解過程的幾種方法的比較
（1）最基本的方法：遞歸實(shí)現(xiàn)，使用公式為f[n] = f[n-1] + f[n-2];遞歸
結(jié)束條件是f[1]=1，f[2]=1。
（2）數(shù)組實(shí)現(xiàn)：空間復(fù)雜度和時(shí)間復(fù)雜度都是O（N），效率一般，比遞歸來
的快。
（3）vector<int>實(shí)現(xiàn)，時(shí)間復(fù)雜度是O(N)，空間復(fù)雜度O(1)，但是不知道
效率會(huì)高不高，當(dāng)然vector有自己的屬性會(huì)占用資源。
（4）queue<int>實(shí)現(xiàn)，當(dāng)然隊(duì)列數(shù)組更適合實(shí)現(xiàn)斐波那契數(shù)列，時(shí)間復(fù)雜度
和空間復(fù)雜度和vector一樣。但是queue太合適這里了，
f(n)=f(n-1)+f(n-2)，f(n)只和f(n-1)和f(n-2)有關(guān)，f(n)入隊(duì)列后，f(n-
2)就可以出隊(duì)列了。
（5）迭代實(shí)現(xiàn)：迭代效率最高，時(shí)間復(fù)雜度是O(N)，空間復(fù)雜度是O(1)，
（6）百度的提供的一種公式法。 由于double類型的精度還不夠，所以程
序算出來的結(jié)果會(huì)有誤差，如果把公式展開計(jì)算，得出的結(jié)果就是正確的。
具體代碼如下：
//遞歸
int fib1(int num)
{
if(num<1)
return -1;
if(num == 1 || num == 2)
return 1;
return f(n-1)+f(n-2);
}
//數(shù)組實(shí)現(xiàn)
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>實(shí)現(xiàn)
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();
}
//迭代實(shí)現(xiàn)
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;
}
//公式實(shí)現(xiàn)
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 閱讀(909)
評論(0) 編輯 收藏 引用 所屬分類:
algorithm