Fibonacci
- 真言
- 真言
no games,no movies, but music.
- 引言
- 引言
no more words, just so these. I find a website from there.
- 介绍
- 介绍
Fibonacci was so wonderful, and made a great progress with development in algorithm.There are three ways to get Fibonacci number.first one// function Fibonacci recursion int Fibonacci_re(int n) { if(n<0) return -1; else if(n==0) return 0; else if(n==1) return 1; return Fibonacci_re(n-1)+Fibonacci_re(n-2); }Running time is so bad. I have no words about it.Running space O(n),store function
second two// function Fibonacci array int Fibonacci_ar(int n) { if( n<0 ) return -1; else if( n==0 ) return 0; else if( n==1 ) return 1; int * data = new int[n+1]; data[0] = 0; data[1] = 1; for(int i = 2;i <= n;i++) { data[i] = data[i-1]+data[i-2]; } return data[n]; }Running time is O(n).Running space O(n),store number
third three// function Fibonacci dp int Fibonacci_dp(int n) { if( n<0 ) return -1; else if( n==0 ) return 0; else if( n==1 ) return 1; queue<int> * Q = new queue<int>; Q -> push(0); Q -> push(1); int head; for(int i=2;i <= n;i++) { head=Q->front(); Q->pop(); Q->push(head+Q->front()); } Q->pop(); head = Q->front(); delete Q; return head; }Running time is O(n).Running space O(2),store Fibonacci(n-1) and Fibonacci(n-2)
- 实验
- 实验
- 代码
- 代码
test.cpp#include <iostream> #include <queue> #include <Windows.h> #include <ctime> using namespace std ; // function Fibonacci recursion int Fibonacci_re(int n); // function Fibonacci dp int Fibonacci_dp(int n); // function Fibonacci array int Fibonacci_ar(int n); // function main int main( ) { DWORD s,e; int r=0; for(int i=0;i<40;i++) { s = GetTickCount(); r = Fibonacci_re(i); e = GetTickCount(); cout<<"Fibonacci n="<<i<<endl; cout<<r<<" re "<<" ms "<<e-s<<endl; s = GetTickCount(); r = Fibonacci_dp(i); e = GetTickCount(); cout<<r<<" dp "<<" ms "<<e-s<<endl; s = GetTickCount(); r = Fibonacci_ar(i); e = GetTickCount(); cout<<r<<" ar "<<" ms "<<e-s<<endl; cout<<endl; } system("pause"); return 0; } // function Fibonacci recursion int Fibonacci_re(int n) { if(n<0) return -1; else if(n==0) return 0; else if(n==1) return 1; return Fibonacci_re(n-1)+Fibonacci_re(n-2); } // function Fibonacci dp int Fibonacci_dp(int n) { if( n<0 ) return -1; else if( n==0 ) return 0; else if( n==1 ) return 1; queue<int> * Q = new queue<int>; Q -> push(0); Q -> push(1); int head; for(int i=2;i <= n;i++) { head=Q->front(); Q->pop(); Q->push(head+Q->front()); } Q->pop(); head = Q->front(); delete Q; return head; } // function Fibonacci array int Fibonacci_ar(int n) { if( n<0 ) return -1; else if( n==0 ) return 0; else if( n==1 ) return 1; int * data = new int[n+1]; data[0] = 0; data[1] = 1; for(int i = 2;i <= n;i++) { data[i] = data[i-1]+data[i-2]; } return data[n]; }