遞歸算法練習(xí)

當(dāng)我們遇到復(fù)雜問題時(shí)，最好能通過分析理解題目找出簡(jiǎn)單的方法來解決問題。今天我們一起來做一道Scratch競(jìng)賽題——“爬臺(tái)階問題”。

小明要上二樓，從一樓到二樓共十級(jí)臺(tái)階。這次小明突然想到一個(gè)問題：“我上樓時(shí)一步可以爬一級(jí)臺(tái)階也可以跨兩級(jí)臺(tái)階，那么從一樓到二樓一共有多少種走法呢？”那么聰明的你可以幫小明用編程來解決這個(gè)問題嗎？

首先要分析題目：假設(shè)每次爬1級(jí)臺(tái)階需要10步，這種解法用數(shù)字化來表示為1、1、1……1。如果每次爬2級(jí)臺(tái)階則表示為2、2、2、2、2。當(dāng)然我們還可以1級(jí)2級(jí)臺(tái)階交叉走……怎樣才能把所有可能性找出來呢？我們用編程的思路來解決，最簡(jiǎn)單算法是多層嵌套循環(huán)，這是用最基礎(chǔ)的枚舉法。還可以想一想我們講過的遞歸算法，這種方法更加高效。

這道題要從后往前思考，假設(shè)小明只差最后一步就可以上第10級(jí)臺(tái)階了，這個(gè)時(shí)候只會(huì)出現(xiàn)兩種情況：第一種是只需要走1步（步長為1）從臺(tái)階9走到臺(tái)階10;第二種是需要走2步（步長為2）從臺(tái)階8走到臺(tái)階10。這樣最后一步就是從臺(tái)階9或者臺(tái)階8開始的，如果我從臺(tái)階0-8有X種辦法，從臺(tái)階0-9有Y種方法，那么從0-10級(jí)臺(tái)階有多少種解法呢？那么最后一步的走法數(shù)量就等于X+Y種。這樣得出結(jié)論：臺(tái)階0-10的走法等于臺(tái)階0-9的走法加臺(tái)階0-8的走法。依據(jù)這個(gè)結(jié)論繼續(xù)向前思考，臺(tái)階8的走法是臺(tái)階6+臺(tái)階7;臺(tái)階9的走法是臺(tái)階8+臺(tái)階7。這樣我們把這個(gè)復(fù)雜的問題就通過從后向前分段簡(jiǎn)化了，這是一種特別有趣的解題技巧。依次往前推導(dǎo)，直到只剩1級(jí)或2級(jí)臺(tái)階。如果我們的數(shù)學(xué)水平足夠就可很直接地聯(lián)想到遞歸公式F（n）=F（n-1）+F（n-2），這個(gè)公式剛剛好可以用到這個(gè)題目中。（圖1）

有了數(shù)學(xué)公式再轉(zhuǎn)為編程代碼就簡(jiǎn)單多了。我們這個(gè)程序更加通用，可以計(jì)算任意臺(tái)階數(shù)的方法數(shù)量，這樣需要詢問臺(tái)階總數(shù)。用變量“方法數(shù)”統(tǒng)計(jì)走法數(shù)量。（圖2）

在自定義積木模塊中，需要先判斷幾種特殊情況，當(dāng)爬臺(tái)階數(shù)小于1時(shí)顯示“臺(tái)階數(shù)小于1，不符合題目要求”直接退出循環(huán);當(dāng)臺(tái)階數(shù)等于1時(shí)有1種走法;臺(tái)階數(shù)等于2時(shí)有2種走法（步長1或步長2）。下面就是利用遞歸算法不停調(diào)用自身。這樣就滿足公式F（n）=F（n-1）+F（n-2）。（圖3）

這樣程序就完成了。運(yùn)行程序可以算出小明走10級(jí)臺(tái)階一共有89種方法。沒想到方法居然有這么多，不知道小明有沒有興趣把89種都走一遍。

下面問題升級(jí)了，可否把每一步的步長都列出來，保存在列表中，那么你該如何修改代碼呢？