斐波那契數(shù)列算法分析(已修改)
2025-06-28 12:41 本頁面
【正文】 斐波那契數(shù)列算法分析背景：假定你有一雄一雌一對剛出生的兔子，它們在長到一個月大小時開始交配，在第二月結(jié)束時，雌兔子產(chǎn)下另一對兔子，過了一個月后它們也開始繁殖，如此這般持續(xù)下去。每只雌兔在開始繁殖時每月都產(chǎn)下一對兔子，假定沒有兔子死亡，在一年后總共會有多少對兔子？在一月底，最初的一對兔子交配，但是還只有1對兔子；在二月底，雌兔產(chǎn)下一對兔子，共有2對兔子；在三月底，最老的雌兔產(chǎn)下第二對兔子，共有3對兔子；在四月底，最老的雌兔產(chǎn)下第三對兔子，兩個月前生的雌兔產(chǎn)下一對兔子，共有5對兔子；……如此這般計算下去，兔子對數(shù)分別是：1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89, 144, ...看出規(guī)律了嗎？從第3個數(shù)目開始，每個數(shù)目都是前面兩個數(shù)目之和。這就是著名的斐波那契（Fibonacci）數(shù)列。有趣問題：1，有一段樓梯有10級臺階,規(guī)定每一步只能跨一級或兩級,要登上第10級臺階有幾種不同的走法?答：這就是一個斐波那契數(shù)列：登上第一級臺階有一種登法；登上兩級臺階，有兩種登法；登上三級臺階，有三種登法；登上四級臺階，有五種方法……所以，1，2，3，5，8，13……登上十級，有89種。2，數(shù)列中相鄰兩項的前項比后項的極限是多少，就是問，當(dāng)n趨于無窮大時，F(xiàn)(n)/F(n+1)的極限是多少？答：這個可由它的通項公式直接得到，極限是(1+√5)/2，這個就是所謂的黃金分割點，也是代表大自然的和諧的一個數(shù)字。數(shù)學(xué)表示：Fibonacci數(shù)列的數(shù)學(xué)表達(dá)式就是：F(n) = F(n1) + F(n2)F(1) = 1F(2) = 1遞歸程序1：Fibonacci數(shù)列可以用很直觀的二叉遞歸程序來寫，用C++語言的描述如下：long fib1(int n){ if (n = 2){ return 1。}else{ return fib1(n1) + fib1(n2)。}}看上去程序的遞歸使用很恰當(dāng)，可是在用VC2005的環(huán)境下測試n=37的時候用了大約3s，而n=45的時候基本下樓打完飯也看不到結(jié)果……顯然這種遞歸的效率太低了??！遞歸效率分析：例如，用下面一個測試函數(shù)：long fib1(int n, int* arr){ arr[n]++。 if (n = 2) { return 1。 } else { return fib1(n1, arr) + fib1(n2, arr)。 }}這時，可以得到每個fib(i)被計算的次數(shù)：fib(10) = 1 fib(9) = 1 fib(8) = 2 fib(7) = 3fib(6) = 5 fib(5) = 8 fib(4) = 13 fib(3) = 21fib(2) =
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1