Re: [中學] 排列組合 階梯走法數的問題

[Desperato (TimcApple)]

※ 引述《Tiderus (修煉人生)》之銘言：
: ※ 引述《dreamer15 ()》之銘言：
: : Q:一樓梯，共x階，每次可跨1階2階或3階
: : 問共有___種上樓方式?
: : A:設f(n)表第n階樓梯之上樓方法數
: : 先算出第1 2 3階，f(1)=1 f(2)=2 f(3)=4
: : 之後的公式是:f(n)=f(n-1)+f(n-2)+f(n-3)
: : 如:f(4)=f(1)+f(2)+f(3)=1+2+4=7
: :    f(5)=f(2)+f(3)+f(4)=2+4+7=13  ....
: 嗯，想了一下發現：
: 1.如果上階方法第1步是跨1階，還有(n-1)階，所以剩下階數的上階方法為f(n-1)
: 2.如果上階方法第1步是跨2階，還有(n-2)階，所以剩下階數的上階方法為f(n-2)
: 3.如果上階方法第1步是跨3階，還有(n-3)階，所以剩下階數的上階方法為f(n-3)
: 全部相加。
: : (若每次只能跨1階或2階，則f(n)=f(n-1)+f(n-2) 除f(1)f(2)外
: : 同理 可跨1 2 3 4階 f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4)  )
: 同理。
: : 我的問題:
: : (1)這個公式是怎麼來的?? 不懂~"~
: 同理。
: : (2)若階數很大，或可跨階數較多
: : 如:100階，每次可跨1 2 3 4 5階，問f(100)  該怎麼算??


(2) 完全是一樣的模式...

如果有 n 階，每次可以跨a_1, a_2, a_3, ... a_k 階 (a_i<a_j if i<j)

那麼總共會有f(n)種跨法:
n < 0, f(n) = 0
n = 0, f(n) = 1
n > 0, f(n) = f(n-a_1) + f(n-a_2) + ... + f(n-a_n)

原理都是一樣的，跨a_1階之後，有f(n-a_1)種跨法，以此類推

這不就是遞迴嗎XD


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.229.31.29
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1442393870.A.134.html
※ 編輯: Desperato (36.229.31.29), 09/16/2015 16:58:40
→ Tiderus     : 是說，f(100)數字好大，想說f(n)能不能弄成n為唯一
→ Tiderus     : 變數的函數。
推 Tiderus     : 就是把遞迴式轉成一般式。
→ Desperato   : 一般式通常可以 但也通常解決不了問題XD

舉個例子，一次可以走1,2階上去，走到100階

根據遞迴式就是f(1)=1, f(2)=2, f(n)=f(n-1)+f(n-2), 求f(100)
這個東西事實上就是Fibonacci數列，一般式求法如下

把f(n)都換成x^n，得到x^2 = x + 1, x的兩根是a, b
那麼f(n) = A a^n + B b^n
(為什麼可以這樣做...可能要拉出線性代數救援，現在好懶
現在你可以把f(n)那式代回去看看對不對)

然後以f(1), f(2)的初始條件代入，會得到

        1    1+√5            1    1-√5
f(n) = --- ( ----- )^(n+1) - --- ( ----- )^(n+1)
       √5     2             √5     2


這是Fibonacci數列的一般式(那個n+1是因為前幾項常數不一樣)
可以看出來，基本上拿這式代f(100)也不是開玩笑的
更不要說像 x^3 = x^2 + x + 1 這種三根醜不拉幾還有虛數的
還有更高次那些解已經無法用加減乘除和次方表示了
一個一個遞迴上去可能都還比較快，至少還是正整數

※ 編輯: Desperato (106.65.17.68), 09/16/2015 18:10:16