《算法設(shè)計與分析基礎(chǔ)》（Python語言描述） 課件 第3章基本算法設(shè)計方法

第3章必備技能—基本算法設(shè)計方法3.1窮舉法3.2歸納法CONTENTS提綱3.3迭代法3.4遞歸法3.5遞推式計算1/58窮舉法又稱枚舉法或者列舉法，是一種簡單而直接地解決問題的方法?；舅枷胧窍却_定有哪些窮舉對象和窮舉對象的順序，按窮舉對象的順序逐一列舉每個窮舉對象的所有情況，再根據(jù)問題提出的約束條件檢驗?zāi)男┦菃栴}的解，哪些應(yīng)予排除。3.1.1窮舉法概述3.1窮舉法1.什么是窮舉法2/58常用的列舉方法順序列舉。是指答案范圍內(nèi)的各種情況很容易與自然數(shù)對應(yīng)甚至就是自然數(shù)，可以按自然數(shù)的變化順序去列舉。排列列舉。有時答案的數(shù)據(jù)形式是一組數(shù)的排列，列舉出所有答案所在范圍內(nèi)的排列，為排列列舉。組合列舉。當答案的數(shù)據(jù)形式為一些元素的組合時，往往需要用組合列舉。組合是無序的。3/58窮舉法的作用理論上講窮舉法可以解決可計算領(lǐng)域中的各種問題。在實際應(yīng)用中，通常要解決的問題規(guī)模不大，用窮舉法設(shè)計的算法其運算速度是可以接受的。舉法算法一般邏輯清晰，編寫的程序簡潔明了。窮舉法算法一般不需要特別證明算法的正確性。窮舉法可作為某類問題時間性能的底限，用來衡量同樣問題的更高效率的算法。4/582.窮舉法框架defExhaustive(x,n,y,m): #窮舉法框架 foriinrange(1,n+1): #枚舉x的所有可能的值 forjinrange(1,m+1): #枚舉y的所有可能的值

… ifp(x[i],y[j]):輸出一個解

…x和y所有可能的搜索范圍是笛卡爾積即（[x1，y1]，[x1，y2]，…，[x1，ym]，…，[xn，y1]，[xn，y2]，…，[xn，ym]）。這樣的搜索范圍可以用一棵樹表示，稱為解空間樹。5/58【例3-1】雞兔同籠問題?，F(xiàn)有一籠子，里面有雞和兔子若干只，數(shù)一數(shù)，共有a個頭，b條腿。設(shè)計一個算法求雞和兔子各有多少只？解x表示雞的只數(shù)，y表示兔的只數(shù)，那么窮舉對象就是x和y，假設(shè)窮舉對象的順序是先x后y（本問題中也可以先y后x）。x和y的取值范圍都是0～a，約束條件

p(x，y)為x+y=aand2x+4y=b。6/58解空間樹中共21個結(jié)點，顯然結(jié)點個數(shù)越多時間性能越差！a=3，b=812300123×××0123××××0123×××0123××××x的可能取值y的可能取值滿足條件×1 defsolve1(a,b):2 forxinrange(0,a+1):3 foryinrange(0,a+1):4 ifx+y==aand2*x+4*y==b:5 print("x=%d,y=%d"%(x,y))7/58優(yōu)化：雞的只數(shù)最多為min(a，b/2)，兔的只數(shù)最多為min(a，b/4)1 defsolve2(a,b):2forxinrange(0,min(a,b//2)+1):3 foryinrange(0,min(a,b//4)+1):4 ifx+y==aand2*x+4*y==b:5 print("x=%d,y=%d"%(x,y))8/581230012××012×××012××012×××x的可能取值y的可能取值滿足條件以a=3，b=8為例，x的取值范圍是0～3，y的取值范圍是0～2。共17個結(jié)點！盡管窮舉法算法通常性能較差，但可以以它為基礎(chǔ)進行優(yōu)化繼而得到高性能的算法，優(yōu)化的關(guān)鍵是能夠找出求解問題的優(yōu)化點！×9/58給定一個含n（n≥1）個整數(shù)的序列，要求求出其中最大連續(xù)子序列的和。序列（-2，11，-4，13，-5，-2）的最大連續(xù)子序列和為20。序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大連續(xù)子序列和為16。規(guī)定一個序列最大連續(xù)子序列和至少是0，如果小于0，其結(jié)果為0。3.1.2最大連續(xù)子序列和10/58-20i9152183134115117201513-211-413-5-2初始序列-49421386-2-5-7j012345a[0..5]={-2，11，-4，13，-5，-2}解法1：設(shè)整數(shù)序列為a[0..n-1]，枚舉所有連續(xù)子序列a[i..j]。11/581 defmaxSubSum1(a): #解法12 n,maxsum=len(a),03 foriinrange(0,n): #兩重循環(huán)窮舉所有的連續(xù)子序列4 forjinrange(i,n):5 cursum=0;6 forkinrange(i,j+1):cursum+=a[k]7 maxsum=max(maxsum,cursum) #比較求最大maxsum8 returnmaxsum12/58解法2：優(yōu)化點利用前綴和用presum[i]表示子序列a[0..i-1]元素和即a中前i個元素和，顯然有如下遞推關(guān)系：

presum[0]=0presum[i]=presum(i-1)+a[i-1] 當i>0時假設(shè)j≥i，則有：

presum[i]=a[0]+a[1]+…+a[i-1]presum[j]=a[0]+a[1]+…+a[i-1]+a[i]+…+a[j-1]兩式相減得的presum[j]-presum[i]=a[i]+…+a[j-1]。這樣i從0到n-1、j-1從i到n-1（即j從i+1到n）循環(huán)可以求出所有連續(xù)子序列a[i..j]之和，比較求出最大值maxsum即可。13/581 defmaxSubSum2(a): #解法22 n=len(a)3 presum=[0]*(n+1)4 presum[0]=05 foriinrange(1,n+1):6 presum[i]=presum[i-1]+a[i-1]7 maxsum=08 foriinrange(0,n):9 forjinrange(i+1,n+1):10 cursum=presum[j]-presum[i]11 maxsum=max(maxsum,cursum) #比較求最大maxsum12 returnmaxsum14/58解法3：優(yōu)化點避免起始下標i開始的子序列的重復(fù)計算。用Sum(a[i..j])表示子序列a[i..j]元素和，初始時置Sum(a[i..j])=0，顯然有如下遞推關(guān)系：

Sum(a[i..j])=Sum(a[i..j-1])+a[j] 當j≥i時連續(xù)求a[i..j]子序列和（j=i，i+1，…，n-1）時沒有必要使用循環(huán)變量為k的第3重循環(huán)。-20i9152183134115117201513-211-413-5-2初始序列-49421386-2-5-7j012345Sum[1]=Sum[0]+a[1]=915/581 defmaxSubSum3(a): #解法32 n,maxsum=len(a),03 foriinrange(0,n):4 cursum=05 forjinrange(i,n):6 cursum+=a[j]7 maxsum=max(maxsum,cursum) #比較求最大maxsum8 returnmaxsum16/58解法4：優(yōu)化點

maxsum至少為0。a[0..5]={-2， 11， -4， 13， -5， -2}maxsum=0,cursum=0（cursum表示以a[i]結(jié)尾的最大和）cursum=0+(-2)=-2maxsum=0cursum<0從頭開始cursum=0cursum=0+11=11maxsum=11cursum=11+(-4)=7maxsum=11cursum=7+13=20maxsum=20cursum=20+(-5)=15maxsum=20cursum=15+(-2)=13maxsum=20結(jié)果：maxsum=2017/581 defmaxSubSum4(a): #解法42 n,maxsum,cursum=len(a),0,03 foriinrange(0,n):4 cursum+=a[i];5 maxsum=max(maxsum,cursum) #比較求最大maxsum6 ifcursum<0:cursum=0 #若cursum<0，從下一個位置開始7 returnmaxsumT(n)=O(n)18/58問題描述：給定一個含n（1≤n≤10^5）個整數(shù)的數(shù)組

nums，設(shè)計一個算法找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

例如，nums={-2，1，-3，4，-1，2，1，-5，4}，答案為6，對應(yīng)的連續(xù)子數(shù)組是{4，-1，2，1}。

要求設(shè)計如下方法：

def

maxSubArray(self,

nums:

List[int])

->

int:3.1.3實戰(zhàn)—最大子序列和（LeetCode53）19/58本題的最大連續(xù)子序列和至少包含一個元素，也就是說最大連續(xù)子序列和可能為負數(shù)。例如，nums={-1，-2}，結(jié)果為-1，因此不能直接采用3.1.2節(jié)解法4，需要做修改：

將表示結(jié)果的maxsum初始化為nums[0]而不是0。解20/581 class

Solution:2

def

maxSubArray(self,

nums:

List[int])

->

int:3

n,maxsum,cursum=len(nums),nums[0],04

for

i

in

range(0,n):5

cursum+=nums[i]6

maxsum=max(maxsum,cursum)

#比較求最大maxsum7

if

cursum<0:cursum=0

#cursum<0從下個位置開始8

return

maxsum上述程序提交時通過，運行時間為128ms，內(nèi)存消耗為29.8MB。21/583.2.1歸納法概述3.2歸納法1.什么是數(shù)學歸納法第一數(shù)學歸納法原理：若{P(1)，P(2)，P(3)，P(4)，…}是命題序列且滿足以下兩個性質(zhì)，則所有命題均為真：①P(1)為真。②任何命題均可以從它的前一個命題推導(dǎo)得出。第二數(shù)學歸納法原理：若{P(1)，P(2)，P(3)，P(4)，…}是滿足以下兩個性質(zhì)的命題序列，則對于其他自然數(shù)，該命題序列均為真：①P(1)為真。②任何命題均可以從它的前面所有命題推導(dǎo)得出。22/582.什么是歸納法23/5824/58歸納法

遞推關(guān)系基本流程：按推導(dǎo)問題方向研究最初最原始的若干問題。按推導(dǎo)問題方向?qū)で髥栴}間的轉(zhuǎn)換規(guī)律即遞推關(guān)系，使問題逐次轉(zhuǎn)化成較低層級或簡單的且能解決問題的或已解決的問題。順推法和逆推法：順推法是從已知條件出發(fā)逐步推算出要解決問題的結(jié)果。逆推法從已知問題的結(jié)果出發(fā)逐步推算出問題的開始條件。25/58數(shù)學歸納法不是歸納法，但它與歸納法有著一定程度的關(guān)聯(lián)。在結(jié)論的發(fā)現(xiàn)過程中，往往先通過對大量個別事實的觀察，通過不完全歸納法歸納形成一般性的結(jié)論，最終利用數(shù)學歸納法對結(jié)論的正確性予以證明。26/583.2.2直接插入排序有一個整數(shù)序列R[0..n-1]，采用直接插入排序?qū)崿F(xiàn)R的遞增有序排序。直接插入排序的過程是，i從1到n-1循環(huán)，將R[i]有序插入到R[0..i-1]中。27/58

采用不完全歸納法產(chǎn)生直接插入排序的遞推關(guān)系。

例如R=（2，5，4，1，3），這里n=5，用[]表示有序區(qū)，各趟的排序結(jié)果如下：初始：

（[2]，5，4，1，3）i=1：

（[2，5]，4，1，3）i=2：

（[2，4，5]，1，3）i=3：

（[1，2，4，5]，3）i=4：

（[1，2，3，4，5]）解28/58

設(shè)f(R，i)用于實現(xiàn)R[0..i]（共i+1個元素）的遞增排序，它是大問題，則f(R，i-1)實現(xiàn)R[0..i-1]（共i-1個元素）的排序，它是小問題。對應(yīng)的遞推關(guān)系：f(R，i)≡不做任何事情

當i=0f(R，i)≡f(R，i-1);將R[i]有序插入到R[0..i-1]中; 其他29/58f(R，i)≡不做任何事情

當i=0f(R，i)≡f(R，i-1);將R[i]有序插入到R[0..i-1]中; 其他顯然f(R，n-1)用于實現(xiàn)R[0..n-1]的遞增排序。采用不完全歸納法得到的結(jié)論是否正確呢？

①證明歸納基礎(chǔ)成立。當n=1時直接返回，由于此時R中只有一個元素，它是遞增有序的，所以結(jié)論成立。

②證明歸納遞推成立。假設(shè)n=k時成立，也就是說f(R，k-1)用于實現(xiàn)R[0..k-1]的遞增排序。

當n=k+1時對應(yīng)f(R，k)，先調(diào)用f(R，k-1)將R[0..k-1]排序，再將R[k]有序插入到R[0..k-1]中，這樣R[0..k]變成遞增有序序列了，所以f(R，k)實現(xiàn)R[0..k]的遞增排序，結(jié)論成立。30/581 defInsert(a,i): #將a[i]有序插入到a[0..i-1]中2 tmp=a[i]3 j=i-14 whileTrue: #找a[i]的插入位置5 a[j+1]=a[j] #將關(guān)鍵字大于a[i]的元素后移6 j-=17 ifnot(j>=0anda[j]>tmp):8 break #循環(huán)到a[j]<=tmp為止9 a[j+1]=tmp

#在j+1處插入a[i]1011 defInsertSort1(a): #迭代算法：直接插入排序12 n=len(a)13 foriinrange(1,n):14 ifa[i]<a[i-1]:Insert(a,i) #反序時調(diào)用Insert31/58問題描述：一個機器人位于一個m×n（1≤m，n≤100）網(wǎng)格的左上角（起始點標記為“Start”）。機器人每次只能向下或者向右移動一步。

設(shè)計一個算法求機器人達到網(wǎng)格的右下角（標記為“Finish”）總共有多少條不同的路徑。

例如，m=3，n=3，對應(yīng)的網(wǎng)格如下圖所示，答案為6。StartFinish3.2.3實戰(zhàn)—不同路徑（LeetCode62★★）32/58解從左上角到右下角的任意路徑中，一定是向下走m-1步向右走n-1步，不妨置x=m-1，y=n-1，路徑長度為x+y。StartFinishmn歸納：不同路徑條數(shù)等于x+y個選擇中挑選x個“下”或者y個“右”的組合數(shù)，即

或者，為了方便假設(shè)x≤y，結(jié)果取33/58所有路徑長度為4，=6條不同的路徑如下：

①右右下下

②右下右下

③右下下右

④下右右下

⑤下右下右

⑥下下右右StartFinishmn例如：m=n=334/58上式中分子分母均為x個連乘，可以進一步轉(zhuǎn)換為：由于除法的結(jié)果是實數(shù)，而不同的路徑數(shù)一定是整數(shù)，所以最后需要將計算的結(jié)果四舍五入得到整數(shù)答案。x+y→y-1x→1求（x≤y）35/581 class

Solution:2

def

uniquePaths(self,

m:

int,

n:

int)

->

int:3

return

self.comp(m-1,n-1)45

def

comp(self,x,y):6

a,b=x+y,min(x,y)7

ans=1.08

while

b>0:9

ans*=1.0*a/b10

a-=1;b-=111

return

round(ans)上述程序提交時通過，執(zhí)行時間為40ms，內(nèi)存消耗14.9MB。x+y→y-1x→136/583.2.4猴子摘桃子問題自學（歸納法中的逆推法）37/583.3.1迭代法概述3.3迭代法迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值推出新值的過程。通過讓計算機對一組指令（或一定步驟）進行重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。38/58迭代法算法框架defIterative(): #迭代法框架

迭代變量賦初值 while(迭代條件成立:

根據(jù)遞推關(guān)系式由舊值計算出新值

新值取代舊值，為下一次迭代做準備39/58迭代法算法包含循環(huán)，對循環(huán)的證明引入循環(huán)不變量的概念。循環(huán)不變量是指在每輪迭代開始前后要操作的數(shù)據(jù)必須保持的某種特性（比如在直接插入排序中，排序表前面部分必須是有序的）。循環(huán)不變量是進行循環(huán)的必備條件，因為它保證了循環(huán)進行的有效性，有助于理解算法的正確性。循環(huán)體循環(huán)不變量：每輪迭代前后保持不變，從而保證了算法的正確性40/58循環(huán)不變量必須證明它的三個性質(zhì)：初始化：在循環(huán)的第一輪迭代開始之前，應(yīng)該是正確的。保持：如果循環(huán)的第一次迭代開始之前正確，那么在下一次迭代開始之前它也應(yīng)該保持正確。終止：當循環(huán)結(jié)束時，循環(huán)不變量給了我們一個有用的性質(zhì)，它有助于表明算法是正確的。41/58【例3-3】采用循環(huán)不變量方法證明3.2.2節(jié)直接插入排序算法的正確性。證明：直接插入排序算法中循環(huán)不變量為R[0..i-1]是遞增有序的。初始化：循環(huán)時i從1開始，循環(huán)之前R[0..0]只有一個元素，顯然成立。保持：需要證明每一輪循環(huán)都能使循環(huán)不變量保持成立。對于R[i]排序的這一趟，之前R[0..i-1]是遞增有序的：①如果R[i]≥R[i-1]即正序，則該趟結(jié)束，結(jié)束后循環(huán)不變量R[0..i]顯然是遞增有序的。②如果R[i]<R[i-1]即反序，則在R[0..i-1]中從后向前找到第一個R[j]≤R[i]，將R[j+1..i-1]均后移一個位置，并且將原R[i]放在R[j+1]位置，這樣結(jié)束后循環(huán)不變量R[0..i]顯然也是遞增有序的。終止：循環(huán)結(jié)束時i=n，在循環(huán)不變量中用i替換n，就有R[0..n-1]包含原來的全部元素，現(xiàn)在已經(jīng)排好序了，即說循環(huán)不變量也是成立的。42/583.3.2簡單選擇排序有一個整數(shù)序列R[0..n-1]，采用簡單選擇排序?qū)崿F(xiàn)R的遞增有序排序。簡單選擇排序的過程是：i從0到n-2循環(huán)，R[0..i-1]是有序區(qū)，R[i..n-1]是無序區(qū)，并且前者的所有元素均小于等于后者的任意元素，在R[i..n-1]無序區(qū)通過簡單比較找到最小元素R[minj]，通過交換將其放在R[i]位置。43/58采用不完全歸納法產(chǎn)生簡單選擇排序的遞推關(guān)系。例如R=（2，5，4，1，3），這里n=5，用[]表示有序區(qū)，各趟的排序結(jié)果如下：初始：

（[]2，5，4，1，3）i=0：

（[1]，5，4，2，3）i=1：

（[1，2]，4，5，3）i=2：

（[1，2，3]，5，4）i=3：

（[1，2，3，4]，5）解44/58設(shè)f(R，i)用于實現(xiàn)R[i..n-1]（共n-i個元素）的遞增排序，它是大問題，則f(R，i-1)實現(xiàn)R[i-1..n-1]（共n-i-1個元素）的排序，它是小問題。f(R，i)≡不做任何事情

當i=n-1時f(R，i)≡在R[i..n-1]中選擇最小元素交換到R[i]位置; 否則

f(R，i+1);45/581 defSelect(a,i): #一趟排序：在a[i..n-1]中選擇最小元素交換到a[i]位置2 n,minj=len(a),i #minj表示a[i..n-1]中最小元素的下標3 forjinrange(i+1,n): #在a[i..n-1]中找最小元素4 ifa[j]<a[minj]:minj=j5 ifminj!=i: #若最小元素不是a[i]6 a[minj],a[i]=a[i],a[minj] #交換78 defSelectSort1(a): #迭代法：簡單選擇排序9 foriinrange(0,len(a)): #進行n-1趟排序10 Select(a,i)46/58問題描述：給定一個大小為n的數(shù)組nums，設(shè)計一個算法求其中的多數(shù)元素。

多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于

n/2

的元素?？梢约僭O(shè)中給定的非空數(shù)組中總是存在多數(shù)元素。

例如數(shù)組為{3，2，3}，結(jié)果為3。

要求設(shè)計如下方法：

def

majorityElement(self,

nums:

List[int])

->

int3.3.4實戰(zhàn)—多數(shù)元素（LeetCode169）47/58第2章采用哈希映射求解，這里采用迭代法求解。解48/58依題意nums中一定存在多數(shù)元素。通過觀察可以歸納出這樣的結(jié)論：刪除nums中任意兩個不同的元素，則刪除后多數(shù)元素依然存在且不變。設(shè)候選多數(shù)元素為c=nums[0]，計數(shù)器cnt表示c出現(xiàn)的次數(shù)（初始為1），i從1開始遍歷nums，若兩個元素（nums[i]，c）相同，cnt增1，否則cnt減少1，相當于刪除這兩個元素（nums[i]刪除一次，c也只刪除一次）。如果cnt為0說明前面沒有找到多數(shù)元素，從nums[i+1]開始重復(fù)查找即重置c=nums[i+1]，cnt=1。遍歷結(jié)束后c就是nums中的多數(shù)元素。證明略49/581 class

Solution:2

def

majorityElement(self,

nums:

List[int])

->

int:3

n=len(nums)4

if

n==1:return

nums[0]5

c,cnt=nums[0],16

i=17

while

i<n:8

if

nums[i]==c:

#選擇兩個元素(R[i],c)9

cnt+=1

#相同時累加次數(shù)10

else:11

cnt-=1

#不同遞減cnt，相當于刪除這兩個元素12

if

cnt==0:

#cnt為0時對剩余元素從頭開始查找13

i+=114

c=nums[i];cnt+=115

i+=116

return

c50/58上述程序提交結(jié)果為通過，運行時間為40ms，消耗空間為16.9MB。如果改為存在多數(shù)元素時返回多數(shù)元素，否則返回-151/582013年全國考研題41.（13分）已知一個整數(shù)序列A=（a0，a1，

…，an-1)，其中0≤ai<n（0≤i<n）。若存在ap1=ap2=…=apm=x且m>n/2（0≤pk<n,1≤k≤m），則稱x為A的主元素。

例如A=(0，5，5，3，5，7，5，5)，則5為主元素；又如A=(0，5，5，3，5，1，5，7)，則A中沒有主元素。假設(shè)A中的n個元素保存在一個一維數(shù)組中，請設(shè)計一個盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出-1。要求：

（1）給出算法的基本設(shè)計思想。（2）根據(jù)設(shè)計思想，采用C或C++或Java語言描述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。52/58問題描述：給定正整數(shù)n（n≥1），求{1～n}的冪集的遞歸模型和迭代算法。例如，n=3時，{1，2，3}的冪集合為{{}，{1}，{2}，{1，2}，{3}，{1，3}，{2，3}，{1，2，3}}（子集順序任意）。3.3.4求冪集53/58解以n=3為例，求1～3的冪集的過程1的冪集M1：{{},{1}}M1中每個集合元素添加2得到A2A2：{{2},{1,2}}1～2的冪集M2：{{},{1},{2},{1,2}}M2=M1∪A2M2中每個集合元素添加3得到A3A3：{{3},{1,3},{2,3},{1,2,3}}1～3的冪集M3：{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}M3=M2∪A354/58定義運算appendi(Mi-1，i)返回在Mi-1中每個集合元素末尾插入整數(shù)i的結(jié)果這樣求{1～n}的冪集的遞推關(guān)系如下：M1={{}，{1}}Mi=Mi-1∪Ai

當i>1時55/58Ai=1 importcopy2 defappendi(Mi_1,e): #向Mi_1中每個集合元素末尾添加e3 Ai=Mi_14 forxinAi:x.append(e)5 returnAi656/587 defsubsets(n): #迭代法：求1-n的冪集8 Mi_1=[[],[1]] #Mi_1初始化為1的冪集9 ifn==1:returnMi_1 #處理特殊情況10 foriinrange(2,n+1):11 Mi=copy.deepcopy(Mi_1)12 Ai=appendi(Mi_1,i)13 forxinAi:Mi.append(x)#將Ai所有元素添加到Mi中14 Mi_1=copy.deepcopy(Mi)15 returnMi迭代算法57/583.3.5實戰(zhàn)—子集（LeetCode78★）問題描述：給定一個整數(shù)數(shù)組

nums，長度范圍是1～10，其中所有元素互不相同。求該數(shù)組所有可能的子集（冪集），結(jié)果中不能包含重復(fù)的子集，可以按任意順序返回冪集。

例如，nums=[1，2，3]，結(jié)果為[[]，[1]，[2]，[1，2]，[3]，[1，3]，[2，3]，[1，2，3]]。

自學！58/583.1窮舉法3.2歸納法CONTENTS提綱3.3迭代法3.4遞歸法3.5遞推式計算第3章必備技能—基本算法設(shè)計方法59/403.4.1遞歸法概述3.4遞歸法遞歸算法是指在算法定義中又調(diào)用自身的算法。遞歸算法通常把一個大的復(fù)雜問題層層轉(zhuǎn)化為一個或多個與原問題相似的規(guī)模較小的問題來求解，具有思路清晰和代碼少的優(yōu)點。1.什么是遞歸60/40原問題可以轉(zhuǎn)化為一個或多個子問題來求解，而這些子問題的求解方法與原問題完全相同，只是在數(shù)量規(guī)模上不同。遞歸調(diào)用的次數(shù)必須是有限的。必須有結(jié)束遞歸的條件來終止遞歸。一般來說，能夠用遞歸解決的問題應(yīng)該滿足以下3個條件：61/402.遞歸模型f(s1)=mf(sn)=g(f(sn-1)，c)簡化的遞歸模型：f(sn)

f(sn-1)62/403.提取求解問題的遞歸模型對大問題f(s)進行分析，假設(shè)出合理的“小問題”f(s')。假設(shè)小問題f(s')是可解的，在此基礎(chǔ)上確定大問題f(s)的解，即給出f(s)與f(s')之間的遞推關(guān)系，也就是提取遞歸體（與數(shù)學歸納法中假設(shè)i=n-1時等式成立，再求證i=n時等式成立的過程相似）。確定一個特定情況（如f(1)或f(0)）的解，由此作為遞歸出口（與數(shù)學歸納法中求證i=1或i=0時等式成立相似）。63/404.遞歸算法框架defrecursion1(n): #先遞后合的遞歸框架 if滿足出口條件:

直接解決 else:

recursion1(m) #遞去，遞到最深處

merge() #歸來時執(zhí)行合并操作defrecursion2(n): #先合后遞的遞歸框架 if滿足出口條件:

直接解決 else:

merge() #合并

recursion2(m) #遞到最深處后，再不斷地歸來64/40【例3-4】假設(shè)二叉樹采用二叉鏈存儲，設(shè)計一個算法判斷兩棵二叉樹t1和t2是否相同，所謂相同是指它們的形態(tài)相同并且對應(yīng)結(jié)點值相同。1234t11234t2t1和t2相同1234t11234t2t1和t2不相同65/40解設(shè)f(t1，t2)表示二叉樹t1和t2是否相同，它們的左右子樹的判斷是兩個小問題。t1f(t1.left,t2.left)t2f(t1.right,t2.right)f(t1，t2)=true 當t1和t2均為空f(t1，t2)=false 當t1、t2中一空一非空f(t1，t2)=false 當均不空但結(jié)點值不同f(t1，t2)=f(t1.left,t2.left)&&f(t1.right,t2.right) 其他66/401 defsame(r1,r2): #遞歸算法：判斷r1和r2是否相同2 ifr1==Noneandr2==None:3 returnTrue4 elifr1==Noneorr2==None:5 returnFalse6 ifr1.val!=r2.val:7 returnFalse8 leftans=same(r1.left,r2.left) #遞歸調(diào)用19 rightans=same(r1.right,r2.right) #遞歸調(diào)用210 returnleftansandrightansf(t1，t2)=true 當t1和t2均為空f(t1，t2)=false 當t1、t2中一空一非空f(t1，t2)=false 當均不空但結(jié)點值不同f(t1，t2)=f(t1.left,t2.left)&&f(t1.right,t2.right)其他end67/403.4.2冒泡排序有一個整數(shù)序列R[0..n-1]，采用冒泡排序?qū)崿F(xiàn)R的遞增有序排序。冒泡排序的過程是，i從0到n-2循環(huán)，R[0..i-1]是有序區(qū)，R[i..n-1]是無序區(qū)，并且前者的所有元素均小于等于后者的任意元素，在R[i..n-1]無序區(qū)通過冒泡方式將最小元素放在R[i]位置。68/401 defBubble(a,i): #一趟排序:在a[i..n-1]中冒泡最小元素到a[i]位置2 exchange=False3 forjinrange(len(a)-1,i,-1): #無序區(qū)元素比較,找出最小元素4 ifa[j-1]>a[j]:

#當相鄰元素反序時5 a[j],a[j-1]=a[j-1],a[j] #a[j]與a[j-1]進行交換6 exchange=True

#本趟排序發(fā)生交換置exchange為真7 returnexchange

#返回是否存在交換89 defBubbleSort1(a): #迭代算法：冒泡排序10 foriinrange(0,len(a)-1): #進行n-1趟排序11 ifnotBubble(a,i):return #本趟未發(fā)生交換時結(jié)束算法冒泡排序的迭代算法如下，改為單個算法。69/40采用不完全歸納法產(chǎn)生冒泡排序的遞推關(guān)系。例如R=（2，5，4，1，3），這里n=5，用[]表示有序區(qū)，各趟的排序結(jié)果如下：初始：

（[]2，5，4，1，3）i=0：

（[1]，2，5，4，3）i=1：

（[1，2]，3，5，4）i=2：

（[1，2，3]，4，5）i=3：

（[1，2，3，4]，5）解70/40

設(shè)f(R，i)用于實現(xiàn)R[0..i]（共i+1個元素）的遞增排序，它是大問題，則f(R，i-1)實現(xiàn)R[0..i-1]（共i個元素）的排序，它是小問題。當i=-1時，R[0..i]為空，看成是有序的。f(R，i)≡不做任何事情

當i=-1f(R，i)≡f(R，i-1); 否則

在R[i..n-1]中冒泡最小元素到R[i]位置;先遞后合R[0]…

R[i-1]R[i]…

R[n-1]f(R,i-1)f(R,i)Bubble(R,i)遞推方向71/401 defBubbleSort21(a,i): #遞歸冒泡排序12 ifi==-1:return #滿足遞歸出口條件3 BubbleSort21(a,i-1) #遞歸調(diào)用4 Bubble(a,i)56 defBubbleSort2(a): #冒泡排序7 BubbleSort21(a,len(a)-2)72/40

設(shè)f(R，i)用于實現(xiàn)R[i..n-1]（共n-i個元素）的遞增排序，它是大問題，則f(R，i-1)實現(xiàn)R[i-1..n-1]（共n-i-1個元素）的排序，它是小問題。當i=n-1時，R[n-1..n-1]僅包含最后一個元素，它一定是最大元素，排序結(jié)束。f(R，i)≡不做任何事情

當i=n-1f(R，i)≡在R[i..n-1]中冒泡最小元素到R[i]位置; 否則

f(R，i+1);先合后遞R[0]…

R[i]R[i+1]…

R[n-1]f(R,i+1)f(R,i)Bubble(R,i)遞推方向73/401 defBubbleSort31(a,i): #遞歸冒泡排序22 ifi==len(a)-1:return #滿足遞歸出口條件3 ifBubble(a,i):BubbleSort31(a,i+1)

#一趟中發(fā)生交換時遞歸調(diào)用45 defBubbleSort3(a): #冒泡排序6 BubbleSort31(a,0)74/40給定正整數(shù)n（n≥1），給出求1～n的全排序的遞歸模型和遞歸算法。例如，n=3時，全排列是{{1，2，3}，{1，3，2}，{3，1，2}，{2，1，3}，{2，3，1}，{3，2，1}}。3.4.3求全排列75/40以n=3為例，求1～3的全排列的步驟。解將2插入到各位上將3插入到各位上1初始時為1求解中間結(jié)果求解的最終結(jié)果122112313231221323132176/40

設(shè)Pi表示1～i（i≥1，共i個元素）的全排列（是一個兩層集合，其中每個集合元素表示1～i的某個排列），為大問題。Pi-1為1～i-1（共i-1個元素）的全排列，為小問題。顯然有P1={{1}}。P1={{1}}

當i>1時77/401 importcopy2 defInsert(s,i,j): #在s的位置j插入i3 tmp=copy.deepcopy(s)4 tmp.insert(j,i) #位置j插入整數(shù)i5 returntmp67 defCreatePi(s,i): #在s集合中i-1到0位置插入i8 tmp=[]9 forjinrange(len(s),-1,-1):10 s1=Insert(s,i,j) #在s(含i-1個整數(shù))的每個位置插入i11 tmp.append(s1) #s1添加到Pi中12 returntmp78/4014 defperm11(n,i): #遞歸算法15 ifi==1:16 return[[1]]17 else:18 Pi=[] #存放1～i的全排列19 Pi_1=perm11(n,i-1) #求出Pi_120 forxinPi_1:21 tmp1=CreatePi(x,i) #在x集合中插入i得到tmp122 foryintmp1:Pi.append(y) #將tmp1添加到Pi中23 returnPi2425 defperm1(n): #遞歸法求1-n的全排列26 returnperm11(n,n)79/403.4.4實戰(zhàn)—字符串解碼（LeetCode394★★）問題描述：給定一個經(jīng)過編碼的有效字符串s，設(shè)計一個算法返回s解碼后的字符串。編碼規(guī)則是用“k[encoded_string]”表示方括號內(nèi)的

encoded_string

（僅包含小寫字母）正好重復(fù)k（k

保證為正整數(shù)）

次。

例如，s="3[a]2[bc]"，答案為"aaabcbc"，若s="abc3[cd]xyz"，答案為"abccdcdcdxyz"。

要求設(shè)計如下方法：public

String

decodeString(String

s)

{}80/40問題描述：給定一個經(jīng)過編碼的有效字符串s，設(shè)計一個算法返回s解碼后的字符串。編碼規(guī)則是用“k[encoded_string]”表示方括號內(nèi)的encoded_string

（僅包含小寫字母）正好重復(fù)k（k

保證為正整數(shù)）次。

例如，s="3[a]2[bc]"，答案為"aaabcbc"，若s="abc3[cd]xyz"，答案為"abccdcdcdxyz"。

要求設(shè)計如下方法：def

decodeString(self,s:str)->str3.4.4實戰(zhàn)—字符串解碼（LeetCode394★★）81/40采用遞歸法求解，設(shè)f(s)求字符串s解碼字符串。

（1）遞歸出口：對于不包含數(shù)字和括號的字符串s，直接連接到ans中。例如s="abc"，則ans="abc"。解82/40（2）遞歸體：依題意s是一個合法的字符串，分為如下幾種情況：s=“k[encoded_string]”，其中encoded_string是一個合法的字符串，先提取整數(shù)k，再調(diào)用f(encoded_string)求出小問題的結(jié)果，則ans為k個f(encoded_string)的連接。例如s=“3[a]”，則ans="aaa"。s="s1…sn"，其中si是合法的子串，則ans=f(s1)+…+f(sn)。例如，s="abc3[cd]xyz"，則 ans="abc"+"cdcdcd"+"xyz"="abccdcdcdxyz"。83/401 class

Solution:2

def

decodeString(self,s:str)->str:

#求解算法3

self.i=0

#類變量i從0開始遍歷s4

return

self.unfold(s)584/406

def

unfold(self,s):

#遞歸算法7

ans=""8

while

self.i<len(s)

and

s[self.i]!=']':

#處理到']'為止9

if

s[self.i]>='a'

and

s[self.i]<='z': #遇到字母10

ans+=s[self.i];

self.i+=111

else:12

k=013 while

self.i<len(s)

and

s[self.i]>='0'

and

s[self.i]<='9':

14

k=k*10+ord(s[self.i])-ord('0');self.i+=115

self.i+=1

#數(shù)字符后面為'['，跳過該'['16

tmp=self.unfold(s)

#求子串解碼結(jié)果tmp17

self.i+=1

#后面是一個']'，跳過該']'18

while

k>0:

#連接tmp字符串k次19

ans+=tmp;k-=120

return

ans;

#s處理完畢返回ans85/40上述程序提交時通過，執(zhí)行用時為32ms，內(nèi)存消耗為15MB。86/403.5.1直接展開法3.5遞推式計算求解遞推式最自然的方法是將其反復(fù)展開。即直接從遞歸式出發(fā)，一層一層地往前遞推，直到最前面的初始條件為止，就得到了問題的解。87/40【例3-8】求解梵塔問題的遞歸算法如下，分析移動n盤片的時間復(fù)雜度。voidHanoi(intn,charx,chary,charz){if(n==1)System.out.printf("將盤片%d從%c搬到%c\n",n,x,z);else

{

Hanoi(n-1,x,z,y);System.out.printf("將盤片%d從%c搬到%c\n",n,x,z);

Hanoi(n-1,y,x,z);}}88/40解Hanoi(n，x，y，z)的執(zhí)行時間為T(n)T(n)=1 當n=1T(n)=2T(n-1)+1 當n>1T(n)=2[2T(n-2)+1]+1=22T(n-2)+1+21=23T(n-3)+1+21+22=…=2n-1T(1)+1+21+22+…+2n-2=2n-1=O(2n)voidHanoi(intn,charx,chary,charz){if(n==1)System.out.printf("將盤片%d從%c搬到%c\n",n,x,z);else

{

Hanoi(n-1,x,z,y);System.out.printf("將盤片%d從%c搬到%c\n",n,x,z);

Hanoi