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

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

2、第二步計(jì)算的階梯數(shù)量相加求得總上 法數(shù)量，顯然這種計(jì)算方法原理上沒(méi)錯(cuò)，符合邏輯關(guān)系，但是計(jì)算步 驟多，排列組合分別計(jì)算 11 類(lèi)的上法數(shù)量，計(jì)算量大，總的來(lái)說(shuō)用 這種方法在 8 秒鐘算出結(jié)果的可能性不大， 這個(gè)問(wèn)題是不是有其它解 法，王大法是不是有更快的計(jì)算方法哪？我的回答是王大法應(yīng)該有更 快的方法，王大法在 8 秒之內(nèi)計(jì)算出結(jié)果很可能用了 -斐波那契數(shù)列 的推導(dǎo)法， 用斐波那契數(shù)列的推導(dǎo)法計(jì)算速度大大提高， 下面我來(lái)介 紹一下斐波那契數(shù)列的推導(dǎo)法的計(jì)算方法：根據(jù)斐波那契數(shù)列：如果設(shè) an 為該數(shù)列的第 n項(xiàng)（ ），那么這句話可以寫(xiě)成如下形式：（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對(duì)應(yīng) 10946答： 20級(jí)階梯，每次只能上 1級(jí)或 2級(jí)，總共有 10946種上法 大家也都看到了， 用斐波那契數(shù)列的推導(dǎo)法與用排列組合法計(jì)算速度 快多了，但用斐波那契數(shù)列的

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

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

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