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

請問這題用JAVA程式要怎麼寫呢..

當n<=1時,F0=1,F1=1,

當n>1,Fn=sum(Fi * F(n-i-1)), 0<= i <= n-1,

當輸入n值時,會顯示出 Fn=?

請問這題要怎麼寫ㄋ?? 請各位大大幫忙解答

1 個解答

評分
  • Jeremy
    Lv 4
    1 0 年前
    最佳解答

    if you have any questions, please contact me.

    E-mail: tsungjung411@yahoo.com.tw

    ------------------------------------------------

    相關知識:

    http://tw.knowledge.yahoo.com/question/?qid=130605...

    http://tw.knowledge.yahoo.com/question/?qid=120605...

    程式下載觀摩:

    http://home.kimo.com.tw/tsungjung411/download/java...

    說明:

    b0 = 1, b1 = 1, otherwise

    bn = sum(bi * bn-i-1), for i from 0 to n – 1

    則此序列為

    b0 = 1

    b1 = 1

    b2 = (b0) * (b1) + (b1) * (b0) = 1 + 1 = 2

    b3 = (b0) * (b2) + (b1) * (b1) + (b2) * (b0) = 2 + 1 + 2 = 5

    b4 = (b0) * (b3) + (b1) * (b2) + (b2) * (b1) + (b3) * (b0) = 5 + 2 + 2 + 5 = 14

    b5 = (b0) * (b4) + (b1) * (b3) + (b2) * (b2) + (b3) * (b1) + (b4) * (b0) = 14 + 5 + 4 + 5 + 14 = 42

    公式解:C(2*n, n) / (n + 1),其中C(n,m)意思為有n個不同相異物,取出m種的組合數‧

    C(1*2, 1) / (1 + 1) = C(2, 1) / 2 = 1

    C(2*2, 2) / (2 + 1) = C(4, 2) / 3 = 2

    C(3*2, 2) / (3 + 1) = C(6, 3) / 4 = 5

    C(4*2, 4) / (4 + 1) = C(8, 4) / 5 = 14

    C(5*2, 5) / (5 + 1) = C(10, 5) / 6 = 42

    公式解堆導請參考 ’謝樹明’ – ‘資料結構’一書‧

    此遞迴版本時間複雜度為***,篇幅有限不加以推導,並且n越大執行越慢‧

    此迴圈版本時間複雜度為線性O(n),因此執行起來根本沒感覺!

    但要注意的是”小心溢位”

    執行結果:

    Please input an non-negative integer. (otherwise will exit loop)

    n = 14

    recursion: f(n)=2674440 elapsed time(ms):47

    iteration: f(n)=2674440 elapsed time(ms):0

    Please input an non-negative integer. (otherwise will exit loop)

    n = 15

    recursion: f(n)=9694845    elapsed time(ms):125

    iteration: f(n)=9694845    elapsed time(ms):0

    Please input an non-negative integer. (otherwise will exit loop)

    n = 16

    recursion: f(n)=35357670    elapsed time(ms):359

    iteration: f(n)=35357670    elapsed time(ms):0

    Please input an non-negative integer. (otherwise will exit loop)

    n = 17

    recursion: f(n)=129644790    elapsed time(ms):1078

    iteration: f(n)=129644790    elapsed time(ms):0

    Please input an non-negative integer. (otherwise will exit loop)

    n = 18

    recursion: f(n)=477638700    elapsed time(ms):3235

    iteration: f(n)=477638700    elapsed time(ms):0

    Please input an non-negative integer. (otherwise will exit loop)

    n = -1

    Press any key to continue...

    參考資料: me & 資料結構應試寶典 – 謝樹明著
    • Commenter avatar登入以對解答發表意見
還有問題?馬上發問,尋求解答。