斐波那契數列的第n項。

第一種：遞歸函數

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<assert.h>
  4 
  5 int Fabonacci(int n)
  6 {
  7     if(n<=1&&n>=0)
  8     {
  9         return n;
 10     }
 11     return Fabonacci(n-1)+Fabonacci(n-2);
 12 }
 13 int main()
 14 {
 15     int n;
 16     printf("please input the value of n\n");
 17     scanf("%d",&n);
 18     printf("the result of %d is %d\n",n,Fabonacci(n));
 19     return 0;
 20 }      

第二種：數組實作

建立一個兩個元素的數組，初始化為1，求第n項的值，依次求出前面兩項的和。

時間複雜度：O(n) 

空間複雜度：O(1)

  1 #include<stdio.h>
  2 int fib(int n)
  3 {
  4   int a[2]={1,1};
  5   int i=3;
  6   if(n<0)
  7   {
  8       return -1;
  9   }
 10   if(n==0)
 11   {
 12       return 0;
 13   }
 14   if(n<=2)
 15   {
 16       return a[n-1];
 17   }
 18   for(;i<=n;i++)
 19   {
 20       int tmp=a[0];
 21       a[0]=a[1];
 22       a[1]=a[0]+tmp;
 23   }
 24   return a[1];
 25 }
 26 int main()
 27 {
 28     int n=0;
 29     printf("please input the value of n\n");
 30     scanf("%d",&n);
 31     printf("the num is %d\n",fib(n));
 32     return 0;
 33 }

結果：
please input the value of n
0
the num is 0
[admin@localhost KEY]$ ./test
please input the value of n
5
the num is 5
[admin@localhost KEY]$ ./test
please input the value of n
4
the num is 3
[admin@localhost KEY]$ ./test
please input the value of n
-1
the num is -1      

第三種：隊列實作

思路同第二種

#include<iostream>
#include<queue>
using namespace std;
int fib(int n)
{
	if(n<0)
	{
		return -1;
	}
	if(n<=2)
	{
		return 1;
	}
	queue<int> q;
	q.push(1);
	q.push(1);
	for(int i=2;i<n;i++)
	{
		int tmp=q.front();
		q.pop();
		q.push(tmp+q.front());
	}
	q.pop();
	return q.front();
}
void test()
{
	int n1 =-1;
	int n2=2;
	int n3=5;
	cout<<fib(n1)<<endl;
    cout<<fib(n2)<<endl;
    cout<<fib(n3)<<endl;

}
int main()
{
	test();
	system("pause");
	return 0;
}      

第四種：公式實作

int fib(int n)

{

if(n<0)

return -1;

}

 double gh5=sqrt((double)5);