實作求第n個斐波那契數

斐波那契數列：指的是這樣一個數列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368..這個數列從第3項開始，每一項都等于前兩項之和

求第n個斐波那契數有很多種方法

1.簡單的一種就是：求前兩個數時規定輸出1，從第三項開始，輸出前兩項之和，用a1,a2表示，每次加和求出第n值時，将a1,a2向後推移，準備下一項求值

代碼如下：

#include<stdio.h>

int main()

{

int n=0;

printf("請輸入你想得到第幾個菲波那切數:\n");

scanf("%d",&n);

if(n>2)

{

int i=0;

int fit=0;

int a1=1,a2=1;

for(i=3;i<=n;i++)

{

fit=a1+a2;

a1=a2;

a2=fit;

}

printf("%d\n",fit);

}

else

printf("1\n");

    return 0;

}

2.利用數組

#include<stdio.h>

int main()

{

int n=0;

printf("請輸入你想得到第幾個菲波那切數:\n");

scanf("%d",&n);

if(n>2)

{

int i=0;

int a[100];

for(i=3;i<=n;i++)

{

a[1]=1;

a[2]=1;

   a[i]=a[i-1]+a[i-2];

}

printf("%d\n",a[n]);

}

else

printf("1\n");

    return 0;

}

3.遞歸

說到遞歸就要多說一點了，遞歸對于這類有規律的求和使得程式代碼簡單利落

什麼叫做遞歸？ 程式調用自身的程式設計技巧就是遞歸。遞歸作為一種算法在程式設計語言中廣泛應用，一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸政策隻需少量的程式就可描述出解題過程中所需要的多次重複計算，大大的減少了程式的代碼量。

遞歸的主要思考方式：把大事化小

遞歸的兩個必要條件：1.存在限制條件，當滿足這個條件的時候，遞歸不再繼續  2.每次遞歸調用之後越來越接近這個限制條件

以下是遞歸求第n個斐波那契數

#include<stdio.h>

int fit(int n)

{

if(n<=2)

return 1;

else

return fit(n-1)+fit(n-2);

}

int main()

{

int n=0;

printf("請輸入你想得到第幾個斐波那契數:\n");

scanf("%d",&n);

fit(n);

printf("%d\n",fit(n));

return 0;

}