少年班中王大法計算樓梯上法(續(xù))

1、階梯上法（續(xù)）前言： 在少年班電影第 6 分 58 秒孫紅雷向王大法提問： 有 20 級階梯，每次只能上 1 級或 2 級，總共有多少種上法？正文： 在上一次我們用數(shù)學(xué)中的排列組合計算的方法驗證了少年班 電影王大法計算階梯上法結(jié)果 10946 種，但是王大法是用排列組合的 方法計算的嗎？在少年班電影中王大法念念有詞： “最高階非零 子式的階數(shù) =n-2，任何 n-1 階子式均為零”僅用了 8 秒鐘計算出結(jié) 果 10946 種。我們在上一次用排列組合計算時， 計算分為三個大步驟， 第一步、 先把上階梯的方法分為 11 類，第二步、 又用排列組合分別計算 11 類 上階梯的上法數(shù)量， 第三步、 把

2、第二步計算的階梯數(shù)量相加求得總上 法數(shù)量，顯然這種計算方法原理上沒錯，符合邏輯關(guān)系，但是計算步 驟多，排列組合分別計算 11 類的上法數(shù)量，計算量大，總的來說用 這種方法在 8 秒鐘算出結(jié)果的可能性不大， 這個問題是不是有其它解 法，王大法是不是有更快的計算方法哪？我的回答是王大法應(yīng)該有更 快的方法，王大法在 8 秒之內(nèi)計算出結(jié)果很可能用了 -斐波那契數(shù)列 的推導(dǎo)法， 用斐波那契數(shù)列的推導(dǎo)法計算速度大大提高， 下面我來介 紹一下斐波那契數(shù)列的推導(dǎo)法的計算方法：根據(jù)斐波那契數(shù)列：如果設(shè) an 為該數(shù)列的第 n項（ ），那么這句話可以寫成如下形式：（n3）上階梯總數(shù)與階梯上法列表如下：上階梯總階梯

3、上法數(shù)（數(shù)量）（n3）1122332+1453+2585+36138+572113+883421+1395534+21108955+341114489+5512233144+891337723323315987610+377161597987+6101725841597+9871841812584+15971967654181+258420109466765+4181根據(jù)上表發(fā)現(xiàn)階梯總數(shù) a20對應(yīng) 10946答： 20級階梯，每次只能上 1級或 2級，總共有 10946種上法 大家也都看到了， 用斐波那契數(shù)列的推導(dǎo)法與用排列組合法計算速度 快多了，但用斐波那契數(shù)列的

4、推導(dǎo)法邏輯關(guān)系上比排列組合難理解， 用斐波那契數(shù)列的推導(dǎo)法是得出的上表到總階梯對應(yīng)階梯上法為 10946，是巧合，還是每一個階梯總數(shù)對應(yīng)的階梯上法都是對的？下 面我們隨機抽取一個對應(yīng)數(shù)據(jù)用排列組合計算法進行驗證： 例如階梯總數(shù)為 15 時，階梯上法用排列組合計算步驟如下： 第一步先把 15個階梯按每次上 1階或 2階分類如下： 第 1 類：每次上 1 階 的有 15 次，上 2 階的有 0 次； 第 2 類：每次上 1 階 的有 13 次，上 2 階的有 1 次； 第 3 類：每次上 1 階 的有 11 次，上 2 階的有 2 次； 第 4 類：每次上 1 階 的有 9 次，上 2 階的有 3

5、 次； 第 5 類：每次上 1 階 的有 7 次，上 2 階的有 4 次； 第 6 類：每次上 1 階 的有 5 次，上 2 階的有 5 次； 第 7 類：每次上 1 階 的有 3 次，上 2 階的有 6 次； 第 8 類：每次上 1 階 的有 1 次，上 2 階的有 7 次； 第二步運用排列組合分別計算上述 8 類階梯上法的種類第 1 類階梯上法的種類很明顯是 1 種；因每次上 1階有 15次，即為 15個相同元素在 15個位置排列組合 用排列組合公式即為： m!=15！=1，第 1類上法有 1 種；n! 15！第 2 類因每次上 1 階有 13 次，上 2 階有 1 次，即為兩種不同元素在

6、 14個位數(shù)上排列組合，一種元素有 13 個，另一種元素有 1個。用排列組合公式即為： m! =14! =14，第 2 類上法有 14種；n! 13!第 3 類因每次上 1 階有 11 次，上 2 階有 2 次，即為兩種不同元素在 13個位數(shù)上排列組合，一種元素有 11 個，另一種元素有 2 個。 用排列組合公式即為： m!= 13! =78，第 3 類上法有 78 種；n! 11!* 2！同理求得其他類階梯上法：第 4 類： m!= 12! =220，第 4 類上法有 220種；n! 9!*3！第 5 類： m!= 11! =330，第 5 類上法有 330種；n! 7!*4！第 6 類： m!= 10! =252，第 6 類上法有 252種；n! 5!*5！第 7 類： m!= 9! =84，第 7 類上法有 84種；n! 3!*6！第 8 類： m!= 8! =8，第 8 類上法有 8 種；n! 1!*7！第三步，把上面 8 類階梯的上法數(shù)量相加就得到階梯總數(shù)為 15 時的 階梯上法數(shù)量：1+14+78+220+330+252+84+8=987得到的答案和斐波那契數(shù)列的推導(dǎo)法對應(yīng)階梯為 15 時的階梯上法數(shù) 量