斐波那契數(shù)列

1、斐波那契數(shù)列算法分析.斐波那契數(shù)列算法分析背景: 假定你有一雄一雌一對(duì)剛出生的兔子，它們?cè)陂L(zhǎng)到一個(gè)月大小時(shí)開始交配，在第二月結(jié)束時(shí), 雌兔子產(chǎn)下另一對(duì)兔子，過了一個(gè)月后它們也開始繁殖，如此這般持續(xù)下去。每只雌兔在開始繁殖時(shí)每月都產(chǎn)下一對(duì)兔子，假定沒有兔子死亡，在一年后總共會(huì)有多少對(duì)兔子？在一月底，最初的一對(duì)兔子交配，但是還只有1對(duì)兔子；在二月底，雌兔產(chǎn)下一對(duì)兔子，共有2對(duì)兔子;在三月底，最老的雌兔產(chǎn)下第二對(duì)兔子，共有3對(duì)兔子；在四月底，最老的雌兔產(chǎn)下第三對(duì)兔子，兩個(gè)月前生的雌兔產(chǎn)下一對(duì)兔子，共有5對(duì)兔子；如此這般計(jì)算下去，兔子對(duì)數(shù)分別是：1, 1, 2, 3, 5, 8,13, 21, 34,

2、 55,89,144, .看出規(guī)律了嗎？從第 3個(gè)數(shù)目開始，每個(gè)數(shù)目都是前面兩個(gè)數(shù)目之和。這就是著名的斐波那契(Fibonacci )數(shù)列。有趣問題：1 ,有一段樓梯有10級(jí)臺(tái)階，規(guī)定每一步只能跨一級(jí)或兩級(jí)，要登上第10級(jí)臺(tái)階有幾種不同的走法 ？答：這就是一個(gè)斐波那契數(shù)列：登上第一級(jí)臺(tái)階有一種登法；登上兩級(jí)臺(tái)階，有兩種登法；登上三級(jí)臺(tái)階，有三種登法；登上四級(jí)臺(tái)階，有五種方法所以，1,2,3, 5, 8, 13登上十級(jí)，有89種。2,數(shù)列中相鄰兩項(xiàng)的前項(xiàng)比后項(xiàng)的極限是多少，就是問，當(dāng)n趨于無(wú)窮大時(shí)，F(xiàn)(n)/F(n+1) 的極限是多少？答：這個(gè)可由它的通項(xiàng)公式直接得到，極限是 (-1+ 瓷)/2

3、 ,這個(gè)就是所謂的黃金分割點(diǎn)，也是代表大自然的和諧的一個(gè)數(shù)字。數(shù)學(xué)表示：Fibonacci數(shù)列的數(shù)學(xué)表達(dá)式就是：F(n) = F(n-1) + F(n-2)F(1) = 1F(2) = 1遞歸程序1 :Fibonacci數(shù)列可以用很直觀的二叉遞歸程序來寫，用C+語(yǔ)言的描述如下：long fib1(int n)if (n <= 2)return 1; else return fib1(n-1) + fib1(n-2); , 3s的時(shí)候用了大約看上去程序的遞歸使用很恰當(dāng)，可是在用VC2005的環(huán)境下測(cè)試n=37顯然這種遞歸的效率太低了！而n=45的時(shí)候基本下樓打完飯也看不到結(jié)果遞歸效率分析：

4、例如，用下面一個(gè)測(cè)試函數(shù)：long fib1(int n, int* arr)arrn+;if (n <= 2) return 1;else return fib1(n-1, arr) + fib1(n-2, arr);被計(jì)算的次數(shù)：fib(i) 這時(shí)，可以得到每個(gè) fib(7) = 3fib(8) = 2 fib(9) = 1 fib(10)= 1 fib(6) = 5 fib(5) = 8 fib(4) = 13 fib(3) = 21fib(2) = 34 fib(1) = 55 fib(0) = 34可見，計(jì)算次數(shù)呈反向的 Fibonacci 數(shù)列，這顯然造成了大量重復(fù)計(jì)算。我們

5、令T(N)為函數(shù)fib(n)的運(yùn)行時(shí)間，當(dāng)N>=2的時(shí)候我們分析可知:T(N) = T(N-1) + T(N-2) + 2而 fib(n) = fib(n-1) + fib(n-2),所以有 T(N) >= fib(n) ,歸納法證明可得:fib(N) < (5/3)AN當(dāng) N>4 時(shí)，fib (N) >= (3/2)AN標(biāo)準(zhǔn)寫法：O (3/2)AN)是以指數(shù)增長(zhǎng)的算法，基本上是最壞的情況。顯然這個(gè)其實(shí)，這違反了遞歸的一個(gè)規(guī)則：合成效益法則。合成效益法則(Compound interest rule):在求解一個(gè)問題的同一實(shí)例的時(shí)候，切勿在不同的遞歸調(diào)用中做重復(fù)性

6、的工作。所以在上面的彳碼中調(diào)用 fib(N-1)的時(shí)候?qū)嶋H上同時(shí)計(jì)算了fib(N-2) 。這種小的重復(fù)計(jì)算在遞歸過程中就會(huì)產(chǎn)生巨大的運(yùn)行時(shí)間。遞歸程序2:用一叉遞歸程序就可以得到近似線性的效率，用 C+語(yǔ)言的描述如下：long fib(int n, long a, long b, int count)if (count = n)return b;return fib(n, b, a+b, +count);long fib2(int n) return fib(n, 0, 1, 1);這種方法雖然是遞歸了，但是并不直觀，而且效率上相比下面的迭代循環(huán)并沒有優(yōu)勢(shì)。迭代解法:Fibonacci數(shù)列用迭

7、代程序來寫也很容易，用C+語(yǔ)言的描述如下：/也可以用數(shù)組將每次計(jì)算的f(n)存儲(chǔ)下來，用來下次計(jì)算用(空間換時(shí)間)long fib3 (int n)long x = 0, y = 1;for (int j = 1; j < n; j+)y = x + y;x = y - x; return y; ) N ( 0就能得到結(jié)果。這時(shí)程序的效率顯然為<1sN = 45,的時(shí)候矩陣乘法：我們將數(shù)列寫成：Fibonacci。 = 0, Fibonacci1 = 1Fibonaccin = Fibonaccin-1 + Fibonaccin-2 (n >= 2)可以將它寫成矩陣乘法形式：

8、弱由為比臼/町i 1皿叫權(quán)將右邊連續(xù)的展開就得到:I 1!_1 »下面就是要用O(log(n)的算法計(jì)算：顯然用二分法來求，結(jié)合一些面向?qū)ο蟮母拍睿珻+代碼如下:class Matrixpubliclong matr22;Matrix( const Matrix&rhs);long d); c, Matrix(long a, long b, long constoperator =( const *( const Matrix& Ihs, Matrix& rhs)Matrix&);Matrix& operatorfriend Matrix Ma

9、trix ret(0,0,0,0);ret.matr00 = lhs.matr00*rhs.matr00 +lhs.matr01*rhs.matr10;ret.matr01 = lhs.matr00*rhs.matr01 + lhs.matr01*rhs.matr1 1;ret.matr10 = lhs.matr10*rhs.matr00 + lhs.matr11*rhs.matr10;ret.matr11 = lhs.matr10*rhs.matr01 + lhs.matr11*rhs.matr11; ret; return ;b, a, Matrix:Matrix(this ->ma

10、tr01 = b;this ->matr10 = c;longlong d) c, longlong ->matr00 = a;->matr11 = d;this thisMatrix:Matrix(const Matrix &rhs) ->matr00 = rhs.matr00;thisthis ->matr01 = rhs.matr01;this ->matr10 = rhs.matr10;this ->matr11 = rhs.matr11;Matrix& Matrix:operator =( const Matrix &

11、rhs)this ->matr00 = rhs.matr00;this->matr01= rhs.matr01;this->matr10= rhs.matr10;this->matr11= rhs.matr11;return * this ;Matrix power( constint n) Matrix& m, (n = 1)ifm; return(n%2 = 0)ifpower(m*m, n/2); returnelsereturn power(m*m, n/2) * m;return log(NO 這時(shí)程long fib4 ( n) int Matrix

12、matrix0(1, 1, 1,0);matrixO = power(matrix0, n-1);matrix0.matr00;序的效率為。公式解法：)了： F(n)的時(shí)間就能求得到在.注意：其中x表示取距離x最近的整數(shù)用C+寫的代碼如下：long fib5(int n)double z = sqrt(5.0);double x = (1 + z)/2;double y = (1 - z)/2;return (pow(x, n) - pow(y, n)/z + 0.5;這個(gè)與數(shù)學(xué)庫(kù)實(shí)現(xiàn)開方和乘方本身效率有關(guān)的，我想應(yīng)該還是在O(log(n) 的效率?？偨Y(jié)：上面給出了 5中求解斐波那契數(shù)列的方法

13、，用測(cè)試程序主函數(shù)如下：int main()cout << fib1(45) << endl;cout << fib2(45) << endl;cout << fib3(45) << endl;cout << fib4(45) << endl;cout << fib5(45) << endl;return 0;1134903170函數(shù)由于我的程序都沒 fibl 。會(huì)等待好久，其它的都能很快得出結(jié)果，并且相同為:有涉及到高的時(shí)候會(huì)顯示出優(yōu)勢(shì)。而后面兩種只有在n = 100000

14、0000 位來測(cè)試效率與正確性。4精度,所以要是求大數(shù)據(jù)的話，可以通過取模來獲得結(jié)果的后1000很大的時(shí)候(例如：n另外斐波那契數(shù)列在實(shí)際工作中應(yīng)該用的很少，尤其是當(dāng)數(shù)據(jù)方法就很好了，沒有必'要用矩陣乘法。O(n),所以綜合考慮基本普通的非遞歸 000000 .1 、 N 皇后問題算法設(shè)計(jì)ALGORITHMprocedure PLACE(k)/ 如果一個(gè)皇后能放在第 k 行的 X(k)列，則返回 true ； 否則返回 false 。 X 是一個(gè)全程數(shù)組，進(jìn)入此過程時(shí)已置了 k 個(gè)值。 /global X(1： k) ； integer i ， k1 1while i<k doi

15、f X (i)= X(k) 在同一列有兩個(gè)皇后 /or ABS(X(i) X(k) =ABS(i k)/ 在同條斜角線上 /then return(false)endifi i+1repeatreturn(true) /滿足約束 / end PLACEprocedure NQUEENS(n)/此過程使用回溯法求出在一個(gè) n*n棋 盤上放置n個(gè)皇后，使其能互相攻擊的所有 可能位置/X(1)0； k-1 /k 是當(dāng)前行；X(k) 是當(dāng)前列/While k>0 do /對(duì)所有的行執(zhí)行以下語(yǔ)句 / X(k) -X(k)+1 /移到下一列/While X(k) < n and not PLA

16、CE(k) doX(k)如果第 k 個(gè)皇后的列 一列 /if X(k)個(gè)位置 / then完整的解嗎 / then/ 是，打印這個(gè)數(shù)組else k k+1 ; X(k) -0; 擴(kuò)展，搜 / endif索下一個(gè)皇后 / else k一X(k)十 l; X(k) 不合理，就看下< n /找到一if k=n / 是一個(gè)print(X)/k 1 / 回溯/endifend NQUEENSProgram :#include<stdio.h>#include<math.h>int k=0,a20,j=1,flag,n,c=0;/k為解的個(gè)數(shù),n為皇后的個(gè)數(shù),flag 標(biāo)記有

17、沒有放置皇后void lycQueen()/ 遞歸求解函數(shù)int i,h;/i 為行號(hào) ,h 為列號(hào)for(h=1;h<=n;h+)aj=h;for(i=1;i<j;i+)/將第 j 個(gè)皇后的位置依次跟前面j-1 個(gè)皇后比較if(ai=aj|abs(aj-ai)=abs(j-i)flag=0;break;/兩個(gè)皇后在同一行或者同一對(duì)角線上 , 沖突else flag=1;/ 沒沖突 , 放置一個(gè)皇后/forif(flag=0&&aj!=n)沒試探完 , 繼續(xù)試探 if(flag=1&&j=n)/得到一個(gè)continue;/放置完 n 個(gè)皇后 ,解k=k+1;c=1;/ 解的個(gè)數(shù)加1for(i=1;i<=n;i+)printf(%d ,ai);/輸出第 i 個(gè)皇后放置的行號(hào)printf();i