斐波那契數(shù)列指的是這樣一個(gè)數(shù)列：0何暇、1、1凛驮、2、3条辟、5黔夭、8、13羽嫡、21本姥、34......，仔細(xì)觀察這個(gè)數(shù)列的規(guī)律可得出杭棵，第0項(xiàng)和第一項(xiàng)分別是他們本身婚惫，從第二項(xiàng)開(kāi)始每一項(xiàng)等于前兩項(xiàng)相加之和氛赐，下面我們根據(jù)這個(gè)規(guī)律來(lái)實(shí)現(xiàn)以下求斐波那契數(shù)列的第N項(xiàng)
斐波那契數(shù)列的實(shí)現(xiàn)方法有很多種，下面我們用兩種方式實(shí)現(xiàn)一下(以下代碼都是C語(yǔ)言實(shí)現(xiàn))
一.遞歸算法實(shí)現(xiàn)
int Fibo1(int n)
{
if (n < 2) {
return n;
}
return Fibo1(n - 1) + Fibo1(n - 2);
}
二.for循環(huán)實(shí)現(xiàn)
int Fibo2(int n)
{
if (n < 2) {
return n;
}
int sum;
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
sum = first + second;
first = second;
second = sum;
}
return second;
}
以上兩種實(shí)現(xiàn)方式對(duì)比先舷，第一種的時(shí)間復(fù)雜度為O(2^n)艰管，第二種的時(shí)間復(fù)雜度為O(n)，項(xiàng)目中為了節(jié)省運(yùn)行時(shí)間和空間蒋川，我們盡量采用復(fù)雜度低的算法來(lái)實(shí)現(xiàn)功能牲芋，所以比較推薦第二種實(shí)現(xiàn)方式。
