C語(yǔ)言-遞推求解

ACM2023/6/261第五講遞推求解2023/6/262先來(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人，寫出第n個(gè)人的年齡表達(dá)式。

2023/6/263顯然可以得到如下公式:化簡(jiǎn)后的公式:F(n)=10+(n-1)*2f[n]=f[n-1]+2f[1]=102023/6/264Fibnacci數(shù)列：Description2009年到來(lái)了。經(jīng)過(guò)2008年一年的修煉，數(shù)學(xué)神童倩倩終于把0到30的Fibonacci數(shù)列(f[0]=0,f[1]=1;f[i]=f[i-1]+f[i-2](i>=2))的值全部給背了下來(lái)。接下來(lái)，Ths決定要考考他，于是每問(wèn)他一個(gè)數(shù)字，他就要把答案說(shuō)出來(lái)，可是Ths自己又記不住。于是他決定編寫一個(gè)程序來(lái)測(cè)驗(yàn)倩倩說(shuō)的是否正確。Input輸入若干數(shù)字n(0<=n<=30)，每個(gè)數(shù)字一行。讀到文件尾。Output輸出f[n]。SampleInput012345SampleOutput0112352023/6/265Fibnacci數(shù)列：即：0、1、1、2、3、5、8、13、21、34…f[0]=0f[1]=1f[n]=f[n-1]+f[n-2]2023/6/266Fibnacci數(shù)列：#include<stdio.h>intmain(){intf[40];f[0]=0;f[1]=1;for(inti=2;i<=30;++i){f[i]=f[i-1]+f[i-2];}intk;while(scanf("%d",&k)!=EOF&&k!='\n'){printf("%d\n",f[k]);}return0;}2023/6/267簡(jiǎn)單思考題:在一個(gè)平面上有一個(gè)圓和n條直線，這些直線中每一條在圓內(nèi)同其他直線相交，假設(shè)沒(méi)有3條直線相交于一點(diǎn)，試問(wèn)這些直線將圓分成多少區(qū)域。2023/6/268我們先來(lái)看一下N條相交的直線最多能把平面分割成幾塊。很明顯，當(dāng)添加第n條直線時(shí)，為了使平面最多，則第n條直線要與前面n-1條直線都相交，且沒(méi)有任何三條線交于一個(gè)點(diǎn)。這樣，第n條直線一共有n-1個(gè)交點(diǎn)。我們知道，增加n個(gè)焦點(diǎn)，則增加n+1個(gè)平面。所以n條直線分割平面最大數(shù)是f(n)=f(n-1)+n或f（n）=1+1+2+3+...+n=(n2+n+2)/22023/6/269是不是這個(gè)——F(1)=2;F(n)=F(n-1)+n;化簡(jiǎn)后：F(n)=n(n+1)/2+1;2023/6/2610太簡(jiǎn)單了?來(lái)個(gè)稍微麻煩一些的2023/6/2611例:（2050）折線分割平面問(wèn)題描述：平面上有n條折線，問(wèn)這些折線最多能將平面分割成多少塊?樣例輸入

1 2樣例輸出

2 72023/6/2612例:（2050）折線分割平面我們不忙著解這道題。我們先來(lái)看一下N條相交的直線最多能把平面分割成幾塊。很明顯，當(dāng)添加第n條直線時(shí)，為了使平面最多，則第n條直線要與前面n-1條直線都相交，切沒(méi)有任何三條線交于一個(gè)點(diǎn)。這樣，第n條直線一共有n-1個(gè)交點(diǎn)。我們知道，增加n個(gè)焦點(diǎn)，則增加n+1個(gè)平面。所以n條直線分割平面最大數(shù)是f(n)=f(n-1)+n或f（n）=1+1+2+3+...+n=(n2+n+2)/22023/6/2613例:（2050）折線分割平面我們?cè)賮?lái)看看，每次增加的不是一條直線，而是兩條相互平行的線，那又如何呢？當(dāng)?shù)贜次添加時(shí)，前面已經(jīng)有2N-2條直線了，按我們上面討論的知道，第N次添加時(shí)，第2N-1條直線和第2N條直線各能增加2(n-1)+1個(gè)平面。所以第N次添加增加的面數(shù)是2[2(n-1)+1]=4n-2個(gè)。2023/6/2614例:（2050）折線分割平面再來(lái)看如果把每次加進(jìn)來(lái)的平行邊讓它們一頭相交，情況又如何呢？我們看到，平面1、3已經(jīng)合為一個(gè)面，既少了一個(gè)面。因此，每當(dāng)一組平行線相交后，就會(huì)減少一個(gè)面。因此，本題所要求的折線分割平面，自然就是上面求的的平行線分割平面數(shù)減去N即增加4n-3個(gè)。2023/6/2615思考:如何用遞推解決?結(jié)論——F(n)=F(n-1)+4n-3F(0)=12023/6/2616另外一種結(jié)論:Zn=2n(2n+1)/2+1-2n =2n^2–n+1為什么?2023/6/2617#include<stdio.h>intmain(){ intn,i,j,f0,f1;scanf("%d",&i);while(i--&&scanf("%d",&n)) {f0=1; for(j=1;j<=n;j++){f1=f0+4*j-3;f0=f1;}printf("%d\n",f1);}return0;}2023/6/2618#include<stdio.h>intmain(){intn,i;scanf("%d",&i);while(i--&&scanf("%d",&n))printf("%d\n",2*n*n-n+1);return0;}2023/6/2619總結(jié)：遞推求解的基本方法：首先，確認(rèn)：能否容易的得到簡(jiǎn)單情況的解？然后，假設(shè)：規(guī)模為N-1的情況已經(jīng)得到解決。最后，重點(diǎn)分析：當(dāng)規(guī)模擴(kuò)大到N時(shí)，如何枚舉出所有的情況，并且要確保對(duì)于每一種子情況都能用已經(jīng)得到的數(shù)據(jù)解決。2023/6/2620問(wèn)題的提出：設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問(wèn)這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。思考題：平面分割方法2023/6/2621F(1)=2F(n)=F(n-1)+2(n-1)簡(jiǎn)單分析——11324123465781234567108911121314n=1n=2n=3n=422023/6/2622在2×n的長(zhǎng)方形方格中,用n個(gè)1×2的骨牌鋪滿方格,例如n=3時(shí),為2×3方格，骨牌的鋪放方案有三種(如圖),輸入n,輸出鋪放方案的總數(shù)思考題（2046