實(shí)現(xiàn)斐波拉契數(shù)列：1,1,2,3,5,8...，當(dāng)n>=3時(shí)，f(n)=f(n-1)+f(n-2)。

我們提供的服務(wù)有：網(wǎng)站設(shè)計(jì)制作、網(wǎng)站制作、微信公眾號(hào)開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、江津ssl等。為上千余家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的江津網(wǎng)站制作公司

解：求解斐波拉契數(shù)列方法很多，這里提供了4種實(shí)現(xiàn)方法和代碼，由于第5種數(shù)學(xué)公式方法代碼太過繁瑣，只做簡單介紹

方法一：遞歸調(diào)用,每次遞歸的時(shí)候有大量重復(fù)計(jì)算，效率低，可將其調(diào)用的過程轉(zhuǎn)化成一顆二叉樹進(jìn)行分析，二叉樹的總結(jié)點(diǎn)個(gè)數(shù)不超過(2^n-1)個(gè)，由于其是不完全二叉樹，那么函數(shù)計(jì)算的次數(shù)必小于(2^n-1)，時(shí)間復(fù)雜度為O(2^n)；遞歸調(diào)用的深度為n,空間復(fù)雜度為O(n)

方法二：非遞歸數(shù)組方式,循環(huán)中仍然有重復(fù)計(jì)算，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)

方法三：非遞歸循環(huán)方式，將前兩項(xiàng)的計(jì)算結(jié)果保存起來，無重復(fù)計(jì)算，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)

方法四：直接利用數(shù)學(xué)公式法：f(n)={[(1+5^0.5)/2]^n - [(1-5^0.5)/2]^n}/(5^0.5)，時(shí)間復(fù)雜度為O(1)，空間復(fù)雜度為O(1)

實(shí)現(xiàn)代碼如下：

#include

#include

using namespace std;

//方法一：遞歸調(diào)用,有大量重復(fù)計(jì)算，效率低

long long Fibonacci1(int n)

{

return (n < 2) ? n : Fibonacci1(n - 1) + Fibonacci1(n - 2);

}

//方法二：非遞歸數(shù)組方式,循環(huán)中仍然有重復(fù)計(jì)算

long long Fibonacci2(int n)

{

long long *fibArray = new long long[n + 1];

fibArray[0] = 0;

fibArray[1] = 1;

for (int i = 2; i <= n; i++)

{

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

}

long long ret = fibArray[n];

delete[] fibArray;

return ret;

}

//方法三：非遞歸循環(huán)方式，將前兩項(xiàng)的計(jì)算結(jié)果保存起來，無重復(fù)計(jì)算

long long Fibonacci3(int n)

{

long long fibArray[3] = { 0, 1, n };//給fibArray數(shù)組賦初值

for (int i = 2; i <= n; i++)

{

fibArray[2] = fibArray[1] + fibArray[0];

fibArray[0] = fibArray[1];

fibArray[1] = fibArray[2];

}

return fibArray[2];

}

//方法四：直接利用數(shù)學(xué)公式法：f(n)={[(1+5^0.5)/2]^n - [(1-5^0.5)/2]^n}/(5^0.5)

long long Fibonacci4(int n)

{

return (pow((1 + sqrt(5.0)) / 2, n) - pow((1 - sqrt(5.0)) / 2, n)) / sqrt(5.0);

}

//測(cè)試代碼

int main()

{

int num = 0;

int ret = 0;

cout << "請(qǐng)輸入斐波拉契數(shù)列的序號(hào):";

cin >> num;

ret = Fibonacci1(num);

/*ret = Fibonacci2(num);*/

/*ret = Fibonacci3(num);*/

/*ret = Fibonacci4(num);*/

cout << ret << endl;

system("pause");

return 0;

}

方法5：生僻的數(shù)學(xué)公式法

 f(n)      f(n-1)        1    1

[                 ] = [          ]^(n-1)

 f(n-1)    f(n-2)        1    0

該公式可用數(shù)學(xué)歸納法進(jìn)行證明，在矩陣乘法的變換證明過程中，要注意運(yùn)用斐波拉契數(shù)列的性質(zhì)：后一項(xiàng)為前面兩項(xiàng)之和；該數(shù)學(xué)公式，應(yīng)用矩陣的乘法，時(shí)間復(fù)雜度僅為O(log n),時(shí)間效率雖然低，但不夠?qū)嵱?，源碼太過繁瑣，參考劍指0ffer面試題9的源碼