7種方式實現斐波那契數列

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;
        }

vector實現

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);
        }

queue實現

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);
        }

posted @ 2011-07-15 14:29 古文觀芷閱讀(22609) 評論(18) 收藏舉報

刷新頁面返回頂部

7種方式實現斐波那契數列

公告