YLL討論網

小喬每天到學校要爬一段有6阶的楼梯，他每次可以任跨1阶或2阶或3阶。例如：小乔可以先跨3阶，再跨1阶，再跨2阶。试问小乔总共有多少种方法爬这段楼梯？
A 13       B18     C 20     D 22    E24

ans:E

目前想到的方法沒有很好
只有
一個1的 (1,2,3)          去排列有 6 種
二個1的 (1,1,2,2)       去排列有 6 種
三個1的 (1,1,1,3)       去排列有 4 種
四個1的(1,1,1,1,2)     去排列有 5 種
五個1跟6個1，                  只有 1 種
再來是三個2(2,2,2)           只有 1 種
         二個3(3,3)              只有 1 種
共24種

事實上，

這題是用遞回關係，比較有效率！！

不過

且可以推廣到更多層

不過概念比較難說明
----------------------------------------------------------------------
假設 a(n) 是方法數

那麼　由於小喬一次最多只能走　1 or 2  or 3 步

　　　當他要走最後一步時

只有三種情況

　　　當他站在 　第　n-1　層時　　就一次走1步就到第n層 了

　　　當他站在 　第　n-2　層時　　就一次走2步就到第n層 了

　　　當他站在 　第　n-3　層時　　就一次走3步就到第n層 了
----------------------------------------------------------------------

所以　

a(n) = a(n-1) + a(n-2) + a(n-3)


p.s

a(n-1)  是　走到　第　n-1　層 的方法數
a(n-2)  是　走到　第　n-2　層 的方法數
a (n-3)是　 走到　第　n-3　層 的方法數
------------------------------------------------------------------


再來就考慮起始條件　a(1) = 1    很明顯

                  　　　　a(2) = 2

                  　　　　a(3) = 4


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

接下來就一直加下去，
a(4) = 1 + 2 + 4 = 7

a(5) = 2 + 4 + 7 = 13

a(6) = 4 + 7 + 13 = 24  .....所求

這種方法可以一直推

a(7) = 7 + 13 + 24 = 44

a(8) = 13 + 24 + 44 = 81

..........