請房貸高手幫忙回答嚕－颱風動態

演算法的遞洄問題(爬樓梯)

一個人爬樓梯每次可以爬1格階梯或2格階梯(例如3階梯=>11,12,213種走法)1.求當樓梯為12階梯時，有幾種走法2.求當樓梯為N階梯時，有幾種走法更新:我想知道的是他的1.演算法的部分2.遞迴的算法(如果不是遞迴也可以寫出算法)

若 F(0)=1, F(1)=1, 且 F(n)=F(n-1)+F(n-2), for n >=2, 也就是 F(n) 是 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... 這 Fibonacci 數列的話 (費氏數列, 即, 費布那西數列, 由 1, 1 開始, 然後每一項是前兩項的和), 那麼, 這 F(n) 就是你要的答案.(1) n=12 時, 有 F(12)=233 種走法.(2) F(n) 的遞迴的式子如上, 非遞迴的式子見 http://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio 但是它的 n 是要用 n+1 代入的 (即, 您的 n=12 時, 用 n=13 代入它的式子)(3) 演算法可直接由 (2) 得到遞迴版本 (很花時間), 或由 (2) 的非遞迴的式子求, 或是由 1, 1 開始, 每一項是前兩項的和一直求到您要的那一項 (比較快).------------------------- 為什麼答案剛好是費氏數 ? 譬如, n=5 時, 有 F(5)=8 種走法, 如下: 11111 是一種, 1112 是一種, 但 1112 的排列也都 OK, 共 4 種 (1112, 1121, 1211, 2111), 122 是一種, 但包含其排列共 3 種 (122, 212, 221) 總共 1+4+3=8 種. 我們發現, 這其實是用 1 及 2 排成加起來為 5 的數列的總個數, 而這即是 Young–Fibonacci lattice with rank 5 的數列的個數, 見 http://en.wikipedia.org/wiki/Young%E2%80%93Fibonacci_lattice 的圖, 當中畫出的最上一層即 n=5 的情況. 而, 為何這個數剛好是費氏數列? 這可觀察Young–Fibonacci lattice 的第 n 層和 n-1 及 n-2 層的關係, 拿來和當初費氏數列的起源 -- "兔子的繁殖" 來做比較得知. 參考: 1. http://zh.wikipedia.org/zh-tw/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97#.E6.BA.90.E8.B5.B7 2. http://en.wikipedia.org/wiki/Young%E2%80%93Fibonacci_lattice 3. 程式 http://zh.wikipedia.org/zh-tw/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97 4. 每次可以爬 1格, 2格, 或 3 格: http://demonstrations.wolfram.com/WaysOfSteppingOneTwoOrThreeStairsUpAStairway/ 2010-11-08 20:35:53 補充：我想到, 您或許不清楚費氏的兔子是如何繁殖的, 因此我現在直接解釋: 為何爬 n 階的走法個數是 F(n). 假設爬 n 階的走法個數是 A(n). n=1 及 2 時, 顯然 A(1)=1, A(2)=2, n>=3 時, 如下分析: 任何爬法, 一定是底下這兩類中之一: 第一類是先爬了 n-1 階, 最後再爬一階 (一格), 第二類是先爬了 n-2 階, 最後再一次爬二格. 第一類共有 A(n-1) 個, 第二類共有 A(n-2) 個, 因此遞迴式是 A(n)=A(n-1)+A(n-2). (接下面) 2010-11-08 20:36:07 補充： (接上面) 因此 A(n) 數列是由 1, 2 開始, 然後, 每一項是前兩項的和: 1, 2, 3, 5, 8, 13, 21, 34, ... 這和著名的費氏數列 F(n) 剛好一樣.

我知道答案...但是來不及回答=ˇ=抱歉你的答案是錯的因為12階梯的答案是233種走法..(好像是288還是233忘了)就算是N趨近於無限大那麼N也要有個式子出來...1.求當樓梯為12階梯時，有幾種走法(無線多)2.求當樓梯為N階梯時，有幾種走法(無限多)因為可以第1次走1格第2次走1格第3次2格第4次1格所以是無限多第幾次走ㄉ都不一樣唷參考資料：自己

以上文章來自奇摩知識家，如有侵犯請留言告知

https://tw.answers.yahoo.com/question/index?qid=20101107000016KK07856

9D1C50A44D654017