匿名使用者
匿名使用者 發問時間: 電腦與網際網路程式設計 · 2 0 年前

【求救】費氏級數(FIBONACCI NUMBERS)的演算

費氏級數(FIBONACCI NUMBERS)的演算並且請分析他的時間複雜度

3 個解答

評分
  • 匿名使用者
    2 0 年前
    最佳解答

     費氏級數  費波納奇數列是13世紀一個數學家費波納奇發現的.可以用的範圍很多,比方說藝術上的黃金比率,建築設計,甚至艾略特波浪理論(使用費氏級數對股票波動進行分析),而我們可以使用遞迴來求取答案.例:一對兔子被生下後第二個月會繁殖一對兔子,求一年後有多少兔子?(單位:對)月份123456789101112兔子1123581321345589144有繁殖能力的兔子01123581321345589請注意單位是"對",而且新生的兔子要2個月才能交配.而且沒有兔子會死.第一個月兔子還沒長大,所以無生殖能力.所以第二的月總數為1對.第二個月有生殖能力的兔子有1對,所以第三的月總數為2對.第三個月有生殖能力的兔子有1對,所以第四的月總數為3對.第四個月有生殖能力的兔子有2對,所以第五的月總數為5對.第五個月有生殖能力的兔子有3對,所以第六的月總數為8對.第六個月有生殖能力的兔子有5對,所以第七的月總數為13對.第七個月有生殖能力的兔子有8對,所以第八的月總數為21對.第八個月有生殖能力的兔子有13對,所以第九的月總數為34對.第九個月有生殖能力的兔子有21對,所以第十的月總數為55對.第十個月有生殖能力的兔子有34對,所以第十一的月總數為89對.第十一個月有生殖能力的兔子有55對,所以第十二的月總數為144對.第十二個月有生殖能力的兔子有89對以上引用:http://residence.educities.edu.tw/peterhuang1/Data... = 1fib(2) = 1fib(3) = fib(2) + fib(1) = 1 + 1 = 2 fib(4) = fib(3) + fib(2) = 2 + 1 = 3 fib(5) = fib(4) + fib(3) = 3 + 2 = 5 fib(6) = fib(5) + fib(4) = 5 + 3 = 8 fib(7) = fib(6) + fib(5) = 8 + 5 = 13 ...fib(10) = fib(9) + fib(8) = 24 + 21 = 55  ...fib(12) = fib(11) + fib(10) = 89 + 55 = 144  ...可得到:fib(n) = fib (n-1) + fib(n - 2) ,式中 n 表示月份,fib(n) 表示每月總數 程式(以Basic Language為例)fib(1)=1fib(2)=1for i=3 to n  fib(i) = fib(i-1) + fib(i-2)next i

    參考資料: 上述網頁+整理
  • 匿名使用者
    2 0 年前

    如果我沒記錯,可以用特徵方程式來解,可在polynomial time解決.

  • 匿名使用者
    2 0 年前

    請教一下 那時間複雜度?

還有問題?馬上發問,尋求解答。