數學題︰小明有多少種方法上樓梯?(加強版)

數學題︰小明有多少種方法上樓梯?(加強版)

我們想讓你知道的是

小明上樓梯的時候,如果容許一步跨50級,他能夠有多少種走法?

(完整證明較難在此打出來,就此略過。)

由此可推出 gk+2−gk+1 = gk+1+2k,並得出 gk+2 = 2×gk+1+2k。不斷代換下去,最終可得出以下公式︰gk+2 = 2k+1 + (k+1)×2k = (k+3)×2k
(同樣因為不方便打數學公式而略去細節,如不明白請親手計算一次。)

終於到計算答案的一刻︰

f50 + f51 + f52 + … + f98 + f99
= 249 + 250−g1 + 251−g2 + … + 297−g48 + 298−g49
= 249 + 250 + 251 + … +297 + 298−[g1+ g2 + … + g49 ]
= (20 + 21 + … + 248) + 249 + 250 + … + 297 + 298 −(20 + 21 + … + 248) −[g50−249]
= 299−1−(249−1)−[51×248−249]
= 299−1−249 + 1−51×248 + 249
= 299−51×248

* * *

若把小明可以跨的級數再減少,例如減少最多只能跨30級,上述兩個方法都可以推廣來計算答案。

使用第一個方法時須注意,不要重複點算了上樓梯方法,因為這時候小明可以跨兩次甚至三次超過30級。簡單來說,小明開始跨超過30級時在第0級(即地下)、第1至30級、第31至60級以及在第61至69級的情況,需要分開計算。在排除重複的情況時,只要再按上述思路點算便可,雖然煩瑣但不太困難。

使用第二個方法時須注意,在最多跨30級的情況下,要在 f31 而非 f51 開始計算 gk(注意此處的f、g跟跨50步的情況是不同的數列),而且在 k 的值較大時不能使用 gk = g1 + g2 + … + gk + 2k 這條公式。

雖然在小明最多可以跨50級時,第二個方法麻煩得多,但小明可以跨的級數越少時,我猜想第一個方法會越麻煩(因為要減去的上樓梯方法越多),第二個方法則會變得簡單。不過我怕麻煩沒有找出一般的公式,也不肯定數字要多小時才會改變,僅提出一個極端例子作佐證︰假如小明只能跨最多兩級,用第二個方法思考,不難得出公式 fn+1 = fn + fn−1,而且 f1 = 1 和 f2 = 2——也不妨定義 f0 = 1——正是費波那契數列(Fibonacci sequence)。

原文見作者 Medium

相關文章︰

責任編輯:tnlhk
核稿編輯︰王陽翎