廈門(mén)大學(xué)短學(xué)期acm班4

廈門(mén)大學(xué)ACM班2023/9/62第四講遞推求解2023/9/63先來(lái)看一個(gè)超級(jí)簡(jiǎn)單的例題:有5人坐在一起，當(dāng)問(wèn)第5個(gè)人多少歲,他說(shuō)比第4個(gè)人大2歲，問(wèn)第4個(gè)人多少歲,他說(shuō)比第3個(gè)人大2歲，依此下去，問(wèn)第一個(gè)人多少歲，他說(shuō)他10歲，最后求第5個(gè)人多少歲？如果所坐的不是5人而是n人，寫(xiě)出第n個(gè)人的年齡表達(dá)式。

2023/9/64顯然可以得到如下公式:化簡(jiǎn)后的公式:F(n)=10+(n-1)*22023/9/65Fibnacci數(shù)列：即：1、2、3、5、8、13、21、34…2023/9/66思考:有了公式，人工計(jì)算的方法？常見(jiàn)的編程實(shí)現(xiàn)方法？（優(yōu)缺點(diǎn)？）2023/9/67簡(jiǎn)單思考題:在一個(gè)平面上有一個(gè)圓和n條直線，這些直線中每一條在圓內(nèi)同其他直線相交，假設(shè)沒(méi)有3條直線相交于一點(diǎn)，試問(wèn)這些直線將圓分成多少區(qū)域。2023/9/68是不是這個(gè)——F(1)=2;F(n)=F(n-1)+n;化簡(jiǎn)后：F(n)=n(n+1)/2+1;2023/9/69例:（2050）折線分割平面問(wèn)題描述：平面上有n條折線，問(wèn)這些折線最多能將平面分割成多少塊?樣例輸入

1 2樣例輸出

2 72023/9/610思考:如何用遞推解決?結(jié)論——F(n)=F(n-1)+4(n-1)+12023/9/611另外一種結(jié)論:Zn=2n(2n+1)/2+1-2n =2n^2–n+1為什么?2023/9/612總結(jié)：遞推求解的基本方法：首先，確認(rèn)：能否容易的得到簡(jiǎn)單情況的解？然后，假設(shè)：規(guī)模為N-1的情況已經(jīng)得到解決。最后，重點(diǎn)分析：當(dāng)規(guī)模擴(kuò)大到N時(shí)，如何枚舉出所有的情況，并且要確保對(duì)于每一種子情況都能用已經(jīng)得到的數(shù)據(jù)解決。強(qiáng)調(diào)： 1、編程中的空間換時(shí)間的思想 2、并不一定只是從N-1到N的分析2023/9/613問(wèn)題的提出：設(shè)有n條封閉曲線畫(huà)在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問(wèn)這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。思考題：平面分割方法2023/9/614F(1)=2F(n)=F(n-1)+2(n-1)簡(jiǎn)單分析——11324123465781234567108911121314n=1n=2n=3n=422023/9/615在2×n的長(zhǎng)方形方格中,用n個(gè)1×2的骨牌鋪滿方格,例如n=3時(shí),為2×3方格，骨牌的鋪放方案有三種(如圖),輸入n,輸出鋪放方案的總數(shù)思考題（2046）：2023/9/616有1×n的一個(gè)長(zhǎng)方形，用1×1、1×2、1×3的骨牌鋪滿方格。例如當(dāng)n=3時(shí)為1×3的方格（如圖），此時(shí)用1×1，1×2，1×3的骨牌鋪滿方格，共有四種鋪法。

輸入：n（0<=n<=30）;輸出：鋪法總數(shù)再思考題：2023/9/617仔細(xì)分析最后一個(gè)格的鋪法,發(fā)現(xiàn)無(wú)非是用1×1,1×2,1×3三種鋪法,很容易就可以得出：f(n)=f(n-1)+f(n-2)+f(n-3);其中f(1)=1,f(2)=2,f(3)=4典型例題分析過(guò)程：2023/9/618最后一個(gè)思考題（有點(diǎn)難度）2023/9/619分析過(guò)程（1）設(shè)：F(n)表示n個(gè)人的合法隊(duì)列，則：

按照最后一個(gè)人的性別分析，他要么是男，要么是女，所以可以分兩大類(lèi)討論：

1、如果n個(gè)人的合法隊(duì)列的最后一個(gè)人是男，則對(duì)前面n-1個(gè)人的隊(duì)列沒(méi)有任何限制，他只要站在最后即可，所以，這種情況一共有F(n-1);2023/9/6