全部 看板
Meteor TV
哈嘍各位
今天來跟大家分享一個有趣的樓梯問題解法🤗🤗
可以讓你在寫這類題目時能更快速的作答👍😃
——————————————————————————
例題：
藍槓要走12階的階梯，每次只能跨1或2階，試問有幾種走法？
大家第一次看到這個題目的時候🤔🤔
老師一開始一定是教你們窮舉
也就是討論出一次走一階或兩階的次數
之後再去排列就可以求出解答
這邊就不廢話了🤪🤪
答案算出來是233種
那接下來我想給大家另一個思路🤩🤩
就是使用「遞迴數列」
也就是找出「後項與前項關係」
這邊假設一個代數a ₙ
a ₙ 代表的是「走到第n階的方法數」
那題目要求我們只能走一階或兩階
也就是說
如果我們想走到第n階
所有的方法都可以區分成
「從(n-1)階再跨一次一階」
或是「從(n-2)階再跨一次兩階」
所以到第n階的方法數a ₙ 就等於a ₍ₙ₋₁₎﹢ a ₍ₙ₋₂₎
（也許有些人會想
為什麼不能「從(n-2)階再跨兩次一階」呢？
因為這個也算在「從(n-1)階再跨一次一階」裡
也就是包含在a ₍ₙ₋₁₎裡面了🤗🤗）
所以我們就求出了一個關係式🤩🤩
a ₙ = a ₍ₙ₋₁₎﹢ a ₍ₙ₋₂₎，n ≥ 3
那我們就可以開始列數列了！
解法如下：
走到第一階的方法數a ₁ = 1 (一次一階)
走到第二階的方法數a ₂ = 2 (兩次一階、一次兩階)
接下來走到第三階的方法數a ₃就可以直接算了！
也就是a ₃ = a ₂﹢a ₁ = 3
依此類推我們可以從a ₁寫到a ₁₂
1,2,3,5,8,13,21,34,55,89,144,233
故所求走到第十二階的方法數a ₁₂ = 233
那根據這個邏輯
若題目改成能走1、2或3階呢？
聰明的你們一定想到了😏😏
就是將遞迴關係式改成
a ₙ = a ₍ₙ₋₁₎﹢ a ₍ₙ₋₂₎﹢ a ₍ₙ₋₃₎，n ≥ 4
然後把a ₁ ～ a ₃討論出來
a ₁ = 1 (一次一階)
a ₂ = 2 (兩次一階、一次兩階)
a ₃ = 4
(三次一階、一次一階一次兩階×2、一次三階)
就可以列出數列
1,2,4,7,13,24,44,81,149,274,504,927
故a ₁₂ = 927
那我們再改個題目
若我們能走1、3或4階呢？
那我們一樣得先列出關係式
a ₙ = a ₍ₙ₋₁₎﹢ a ₍ₙ₋₃₎﹢ a ₍ₙ₋₄₎，n ≥ 5
然後把a ₁ ～ a ₄討論出來
a ₁ = 1 (一次一階)
a ₂ = 1 (兩次一階)
a ₃ = 2 (三次一階、一次三階)
a ₄ = 4
(四次一階、一次一階一次三階×2、一次四階)
就可以列出數列
1,1,2,4,6,9,15,25,40,64,104,169
故a ₁₂ = 169
而樓梯問題也可以再更靠北一點🤬🤬
像是某幾階不能走阿
這樣就要把不能走的那階視為斷點
分成兩段再將兩段方法數相乘
但我覺得應該是不會那樣考啦😂😂
反正不管如何
用遞迴數列的概念就能夠輕易的算出答案🤗🤗
唯一的敵人就是...
加法不要算錯...
好啦～
這樣大家有懂了嗎？😊😊
你可能有興趣的文章...
全部留言
阿不就剛好我在自習課玩手機😡 不然又不知道要排到哪一樓了😡 好我要去讀書了掰
展開1則留言
走一階兩階的我都前兩項相加變成第三項誒 你講的好清楚(´･Д･)」收藏起來ㄌ🤩
展開1則留言
沒有😡還有兩間還沒放榜 笨死了，學姐怎麼會選你 畢旅第二天放榜！ㄘㄨㄚˋ
展開1則留言
匿名
為什麼不能「從(n-2)階再跨兩次一階」呢？ 因為這個也算在「從(n-1)階再跨一次一階」裡 也就是包含在a ₍ₙ₋₁₎裡面了🤗🤗） 文章中這邊沒看懂，為什麼可以保證這樣
展開1則留言
