第10周遞歸與遞推數(shù)論基礎(chǔ)

1、遞推和遞歸遞 推 有些問(wèn)題中，相鄰兩項(xiàng)或多項(xiàng)數(shù)字（或狀態(tài)）之間存在某種關(guān)系，可以通過(guò)前一項(xiàng)或多項(xiàng)按照某一規(guī)律推出其后一項(xiàng)數(shù)字（或狀態(tài)），或者是通過(guò)后一項(xiàng)或多項(xiàng)按照某一規(guī)律推出其前一項(xiàng)數(shù)字（或狀態(tài)）。我們可將這種規(guī)律歸納成如下遞推關(guān)系式：Fn=g(Fn-1)或者Fn-1=g(Fn)遞 推已知初始值F1，通過(guò)遞推關(guān)系式Fn=g(Fn-1)求出最終結(jié)果Fn的遞推方式稱為順推法；同理，把已知最終結(jié)果為Fn，通過(guò)遞推關(guān)系式Fn-1=g(Fn)求出初始值F1的遞推方式稱為倒推法。遞 推Fibonacci數(shù)列：Hn = Hn-1 + Hn-2Fibonacci數(shù)列大家都非常熟悉，來(lái)源于中世紀(jì)數(shù)學(xué)家Fibon

2、acci提出的一個(gè)問(wèn)題：一對(duì)剛出生的兔子過(guò)兩個(gè)月后,可以繁殖一對(duì)新兔子,問(wèn)原有雌雄各一只兔子，經(jīng)過(guò)十一個(gè)月后，能繁殖多少只兔子。遞 推【例題1】平面分割在一個(gè)平面上有一個(gè)圓和n條直線，這些直線中每一條在圓內(nèi)同其他直線相交，假設(shè)沒(méi)有3條直線相交于一點(diǎn)，試問(wèn)這些直線將圓分成多少區(qū)域。遞 推【問(wèn)題分析】F(1)=2; F(n) = F(n-1)+n;第n根線段被分為n段化簡(jiǎn)后：F(n) = n(n+1)/2 +1;遞 推【引申：折線分割平面】問(wèn)題描述 平面上有n條折線，問(wèn)這些折線最多能將平面分割成多少塊?樣例輸入 樣例輸出1 22 7遞 推【引申：折線分割平面】第n根折線被分為2*2(n-1)段結(jié)論

3、F(n)=F(n-1)+4(n-1)+1遞 推【思考題：平面分割方法】問(wèn)題的提出： 設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問(wèn)這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。2022/10/610F(1)=2F(n)=F(n-1)+2(n-1)簡(jiǎn)單分析遞 推2022/10/611【例2：錯(cuò)排問(wèn)題】某人寫了n封信和n個(gè)信封，如果所有的信都裝錯(cuò)了信封。求所有的信都裝錯(cuò)信封,共有多少種不同情況。 遞 推2022/10/6121、當(dāng)N=1和2時(shí)，易得解，假設(shè)F(N-1)和F(N-2)已經(jīng)得到，重點(diǎn)分析下面的情況：4、后者簡(jiǎn)單，只能是沒(méi)裝錯(cuò)的那封和第N封交換信

4、封，沒(méi)裝錯(cuò)的那封可以是前面N-1封中的任意一個(gè)，故= F(N-2) * (N-1)3、前者，對(duì)于每種錯(cuò)裝，可從N-1封信中任意取一封和第N封錯(cuò)裝，故=F(N-1)*(N-1)2、當(dāng)有N封信的時(shí)候，前面N-1封信可以有N-1或者 N-2封錯(cuò)裝(為什么要考慮N-2?)遞 推2022/10/613【例3：填充問(wèn)題】在2n的長(zhǎng)方形方格中,用n個(gè)12的骨牌鋪滿方格,例如n=3時(shí),為23方格，骨牌的鋪放方案有三種(如圖), 輸入n ,輸出鋪放方案的總數(shù)遞 推2022/10/614【例3的延伸】有1n的一個(gè)長(zhǎng)方形，用11、12、13的骨牌鋪滿方格。例如當(dāng)n=3時(shí)為13的方格（如圖），此時(shí)用11，12，13的

5、骨牌鋪滿方格，共有四種鋪法。 輸入： n（0=n0f(0)=a n=0則稱函數(shù)f為遞歸函數(shù)（遞歸公式），為了求f(n)，我們必須先求f(n-1)，為了求f(n-1),又必須去求f(n-2)，為了求f(1),必須先求f(0),而f(0)是已知的。這種定義函數(shù)的方式稱為遞歸定義。遞 歸一個(gè)遞歸定義必須是有確切含義的，也就是說(shuō)一步比一步簡(jiǎn)單，最終是有終結(jié)的，決不能無(wú)限循環(huán)下去。比如上例中的f(0)=a，這種最簡(jiǎn)單的情況（終結(jié)條件），稱為遞歸邊界，它是遞歸定義必不可少的一部分。 描述遞歸定義的函數(shù)或求解遞歸問(wèn)題的過(guò)程稱為遞歸算法。遞 歸不論是遞歸過(guò)程，還是遞歸函數(shù)，按其調(diào)用的方式一般分為直接遞歸（子程

6、序P直接調(diào)用自己）和間接遞歸（子程序P調(diào)用其它子程序，其它子程序又調(diào)用P）。 遞 歸遞歸算法一般適用在三個(gè)場(chǎng)合：一是數(shù)據(jù)的定義形式是遞歸的，如求Fibonacci數(shù)列問(wèn)題；二是數(shù)據(jù)之間的邏輯關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）是遞歸的，如樹、圖等的定義和操作；三是某些問(wèn)題雖然沒(méi)有明顯的遞歸關(guān)系或結(jié)構(gòu)，但問(wèn)題的解法是不斷重復(fù)執(zhí)行一種操作，只是問(wèn)題規(guī)模由大化小，直至某個(gè)原操作（基本操作）就結(jié)束，如漢諾塔問(wèn)題，這種問(wèn)題使用遞歸思想來(lái)求解比其它方法更簡(jiǎn)單。 遞 歸遞歸不僅可用于計(jì)算、計(jì)數(shù)，而且還可用于枚舉，即把所有具有各某種特性的對(duì)象完全枚舉出來(lái)，關(guān)鍵是如何從輸入?yún)?shù)與輸出結(jié)果之間的對(duì)應(yīng)關(guān)系中歸納出遞歸公式和邊界條件。

7、 遞歸的應(yīng)用舉例 【例題4】集合的劃分【問(wèn)題描述】設(shè)是一個(gè)具有n個(gè)元素的集合，a1，a2，an，現(xiàn)將劃分成K個(gè)滿足下列條件的子集合s1，s2，sk ，且滿足：1si2sisj (1i，jk ij)3s1s2s3sk則稱s1，s2，sk是集合的一個(gè)劃分。它相當(dāng)于把集合中的n個(gè)元素a1 ，a2，an 放入k個(gè)（0knk，k0)。 遞歸的應(yīng)用舉例確定s(n，k)的邊界條件,首先不能把n個(gè)元素不放進(jìn)任何一個(gè)集合中去，即k=0時(shí)，(n，k)0；也不可能在不允許空盒的情況下把n個(gè)元素放進(jìn)多于n的k個(gè)集合中去，即kn時(shí),(n，k)0；再者，把n個(gè)元素放進(jìn)一個(gè)集合或把n個(gè)元素放進(jìn)n個(gè)集合，方案數(shù)顯然都是1，即k=1或k=n時(shí)，s(n,k)=1。因此，我們可以得出劃分?jǐn)?shù)(n，k)的遞歸關(guān)系式為：s(n，k)s(n1，k1)+k*s(n1，k) (nk，k0)s(n，k)0 (n=2，則 hanoi(n-1，A，C，B) AC hanoi(n-1，B，A，C) 運(yùn)行結(jié)果：Enter the number of disks in Hanoi tower：3ACABCBACBABCAC語(yǔ)句： Hanoi(3，A，B，C)在執(zhí)行過(guò)程中，遞歸工作棧要為每一層的遞歸保留數(shù)據(jù)，由于遞歸過(guò)程hanoi只含有四個(gè)值參數(shù)，也無(wú)其它局部變量，因