51CTO-lecture_03遞推求解090302

1、ACM程序設(shè)計,2020/8/17,2,今天，,你 了嗎？,AC,2020/8/17,3,每周一星（2）：,dragon,2020/8/17,4,第三講,遞推求解,2020/8/17,5,先來看一個超級簡單的例題:,有5人坐在一起，當(dāng)問第5個人多少歲,他說比第4個人大2歲，問第4個人多少歲,他說比第3個人大2歲，依此下去，問第一個人多少歲，他說他10歲，最后求第5個人多少歲？,如果所坐的不是5人而是n人，寫出第n個人的年齡表達式。,2020/8/17,6,顯然可以得到如下公式:,化簡后的公式: F(n)=10+(n-1)*2,2020/8/17,7,Fibnacci 數(shù)列：,即：1、2、3、5

2、、8、13、21、34,2020/8/17,8,思考:,遞推公式的偉大意義？,有了公式，人工計算的方法？,常見的編程實現(xiàn)方法？（優(yōu)缺點？）,2020/8/17,9,簡單思考題:,在一個平面上有一個圓和n條直線，這些直線中每一條在圓內(nèi)同其他直線相交，假設(shè)沒有3條直線相交于一點，試問這些直線將圓分成多少區(qū)域。,2020/8/17,10,是不是這個,F(1)=2; F(n) = F(n-1)+n;,化簡后： F(n) = n(n+1)/2 +1;,2020/8/17,11,太簡單了?,來個稍微麻煩一些的,2020/8/17,12,例:（2050）折線分割平面,問題描述： 平面上有n條折線，問這些折線

3、最多能將平面分割成多少塊? 樣例輸入 1 2 樣例輸出 2 7,2020/8/17,13,思考:如何用遞推解決?,結(jié)論,F(n)=F(n-1)+4(n-1)+1,2020/8/17,14,另外一種結(jié)論:,Zn = 2n ( 2n + 1 ) / 2 + 1 - 2n = 2 n2 n + 1,為什么?,2020/8/17,15,趁熱打鐵，,來個差不多的,2020/8/17,16,“佐羅”的煩惱 說起佐羅，大家首先想到的除了他臉上的面具，恐怕還有他每次刻下的“Z”字。我們知道，一個“Z”可以把平面分為2部分，兩個“Z”可以把平面分為12部分，那么，現(xiàn)在的問題是：如果平面上有n個“Z”,平面最多可

4、以分割為幾部分呢？ 說明1：“Z”的兩端應(yīng)看成射線 說明2：“Z”的兩條射線規(guī)定為平行的,附加思考題（還沒加到OJ）：,2020/8/17,17,總結(jié)：遞推求解的基本方法：,首先，確認：能否容易的得到簡單情況的解？,然后，假設(shè)：規(guī)模為N-1的情況已經(jīng)得到解決。,最后，重點分析：當(dāng)規(guī)模擴大到N時，如何枚舉出所有的情況，并且要確保對于每一種子情況都能用已經(jīng)得到的數(shù)據(jù)解決。,強調(diào)： 1、編程中的空間換時間的思想 2、并不一定只是從N-1到N的分析,2020/8/17,18,問題的提出： 設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點，且任何三條封閉曲線不相交于同一點，問這些封閉曲線把平

5、面分割成的區(qū)域個數(shù)。,思考題：平面分割方法,2020/8/17,19,F(1)=2 F(n)=F(n-1)+2(n-1),簡單分析,2020/8/17,20,某人寫了n封信和n個信封，如果所有的信都裝錯了信封。求所有的信都裝錯信封,共有多少種不同情況。,1465 不容易系列之一,2020/8/17,21,分析思路：,1、當(dāng)N=1和2時，易得解，假設(shè)F(N-1)和F(N-2)已經(jīng)得到，重點分析下面的情況：,4、后者簡單，只能是沒裝錯的那封和第N封交換信封，沒裝錯的那封可以是前面N-1封中的任意一個，故= F(N-2) * (N-1),3、前者，對于每種錯裝，可從N-1封信中任意取一封和第N封錯裝

6、，故=F(N-1)*(N-1),2、當(dāng)有N封信的時候，前面N-1封信可以有N-1或者 N-2封錯裝,2020/8/17,22,得到如下遞推公式：,基本形式：d1=0; d2=1遞歸式：dn= (n-1)*( dn-1 + dn-2),這就是著名的錯排公式,2020/8/17,23,在2n的長方形方格中,用n個12的骨牌鋪滿方格, 例如n=3時,為23方格，骨牌的鋪放方案有三種(如圖), 輸入n ,輸出鋪放方案的總數(shù),思考題（2046）：,2020/8/17,24,有1n的一個長方形，用11、12、13的骨牌鋪滿方格。例如當(dāng)n=3時為13的方格（如圖），此時用11，12，13的骨牌鋪滿方格，共有

7、四種鋪法。,輸入： n（0=n=30）; 輸出： 鋪法總數(shù),再思考題：,2020/8/17,25,仔細分析最后一個格的鋪法,發(fā) 現(xiàn)無非是用11,12,13三種鋪法,很容易就可以得出： f(n)=f(n-1)+f(n-2)+f(n-3); 其中f(1)=1,f(2)=2,f(3)=4,典型例題,分析過程：,2020/8/17,26,最后一個思考題（有點難度）,2020/8/17,27,分析過程（1）,設(shè)：F(n)表示n個人的合法隊列，則： 按照最后一個人的性別分析，他要么是男，要么是女，所以可以分兩大類討論： 1、如果n個人的合法隊列的最后一個人是男，則對前面n-1個人的隊列沒有任何限制，他只要

8、站在最后即可，所以，這種情況一共有F(n-1);,2020/8/17,28,2、如果n個人的合法隊列的最后一個人是女，則要求隊列的第n-1個人務(wù)必也是女生，這就是說，限定了最后兩個人必須都是女生，這又可以分兩種情況：,分析過程（2）,2020/8/17,29,2.1、如果隊列的前n-2個人是合法的隊列，則顯然后面再加兩個女生，也一定是合法的，這種情況有F(n-2);,分析過程（3）,2020/8/17,30,2.2、但是，難點在于，即使前面n-2個人不是合法的隊列，加上兩個女生也有可能是合法的，當(dāng)然，這種長度為n-2的不合法隊列，不合法的地方必須是尾巴，就是說，這里說的長度是n-2的不合法串的

9、形式必須是“F(n-4)+男+女”，這種情況一共有F(n-4).,分析過程（4）,2020/8/17,31,結(jié)論：,所以，通過以上的分析，可以得到遞推的通項公式：F(n)=F(n-1)+F(n-2)+F(n-4) (n3)然后就是對n=3 的一些特殊情況的處理了，顯然：F(0)=1 (沒有人也是合法的，這個可以特殊處理，就像0的階乘定義為1一樣) F(1)=1 F(2)=2 F(3)=4,2020/8/17,32,不容易系列之(3) LELE的RPG難題 有排成一行的個方格，用紅(Red)、粉(Pink)、綠(Green)三色涂每個格子，每格涂一色，要求任何相鄰的方格不能同色，且首尾兩格也不同色求全部的滿足要求的涂法.,附加題（看看效果）：,2020/8/17,33,一把鑰匙有N個槽，2N26槽深為1，2，3，4,5,6。每鑰匙至少有3個不同的深度且相連的槽其深度之差不得為5。求這樣的鑰匙的總數(shù)。 本題無輸入 對2N26，輸出滿足要求的鑰匙的總數(shù)。,附加思考題：1480_鑰匙計數(shù)之二,2020/8/17,34,詳見解題報告：, 仔細閱讀，耐心品味，關(guān)鍵掌握從n-1到n的推導(dǎo)過程。,2020/8/17,35,課后任務(wù)：,1290 獻給杭電五十周年校慶的禮物 1297 Childrens Queue 1438 鑰匙計數(shù)之一 1465 不容易