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
     
       * Q = new queue
      
       ; 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 
     
      
#include 
      
        #include 
       
         #include 
        
          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="<
         
           * Q = new queue
          
           ; 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]; }