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

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

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

…x和y所有可能的搜索范圍是笛卡爾積即（[x1，y1]，[x1，y2]，…，[x1，ym]，…，[xn，y1]，[xn，y2]，…，[xn，ym]）。這樣的搜索范圍可以用一棵樹表示，稱為解空間樹。5/58【例3-1】雞兔同籠問題?，F(xiàn)有一籠子，里面有雞和兔子若干只，數(shù)一數(shù)，共有a個(gè)頭，b條腿。設(shè)計(jì)一個(gè)算法求雞和兔子各有多少只？解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個(gè)結(jié)點(diǎn)，顯然結(jié)點(diǎn)個(gè)數(shù)越多時(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個(gè)結(jié)點(diǎn)！盡管窮舉法算法通常性能較差，但可以以它為基礎(chǔ)進(jìn)行優(yōu)化繼而得到高性能的算法，優(yōu)化的關(guān)鍵是能夠找出求解問題的優(yōu)化點(diǎn)！×9/58給定一個(gè)含n（n≥1）個(gè)整數(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ī)定一個(gè)序列最大連續(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)化點(diǎn)利用前綴和用presum[i]表示子序列a[0..i-1]元素和即a中前i個(gè)元素和，顯然有如下遞推關(guān)系：

presum[0]=0presum[i]=presum(i-1)+a[i-1] 當(dāng)i>0時(shí)假設(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)化點(diǎn)避免起始下標(biāo)i開始的子序列的重復(fù)計(jì)算。用Sum(a[i..j])表示子序列a[i..j]元素和，初始時(shí)置Sum(a[i..j])=0，顯然有如下遞推關(guān)系：

Sum(a[i..j])=Sum(a[i..j-1])+a[j] 當(dāng)j≥i時(shí)連續(xù)求a[i..j]子序列和（j=i，i+1，…，n-1）時(shí)沒有必要使用循環(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)化點(diǎn)

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，從下一個(gè)位置開始7 returnmaxsumT(n)=O(n)18/58問題描述：給定一個(gè)含n（1≤n≤10^5）個(gè)整數(shù)的數(shù)組

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

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

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

def

maxSubArray(self,

nums:

List[int])

->

int:3.1.3實(shí)戰(zhàn)—最大子序列和（LeetCode53）19/58本題的最大連續(xù)子序列和至少包含一個(gè)元素，也就是說最大連續(xù)子序列和可能為負(fù)數(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從下個(gè)位置開始8

return

maxsum上述程序提交時(shí)通過，運(yùn)行時(shí)間為128ms，內(nèi)存消耗為29.8MB。21/583.2.1歸納法概述3.2歸納法1.什么是數(shù)學(xué)歸納法第一數(shù)學(xué)歸納法原理：若{P(1)，P(2)，P(3)，P(4)，…}是命題序列且滿足以下兩個(gè)性質(zhì)，則所有命題均為真：①P(1)為真。②任何命題均可以從它的前一個(gè)命題推導(dǎo)得出。第二數(shù)學(xué)歸納法原理：若{P(1)，P(2)，P(3)，P(4)，…}是滿足以下兩個(gè)性質(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ù)學(xué)歸納法不是歸納法，但它與歸納法有著一定程度的關(guān)聯(lián)。在結(jié)論的發(fā)現(xiàn)過程中，往往先通過對大量個(gè)別事實(shí)的觀察，通過不完全歸納法歸納形成一般性的結(jié)論，最終利用數(shù)學(xué)歸納法對結(jié)論的正確性予以證明。26/583.2.2直接插入排序有一個(gè)整數(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)用于實(shí)現(xiàn)R[0..i]（共i+1個(gè)元素）的遞增排序，它是大問題，則f(R，i-1)實(shí)現(xiàn)R[0..i-1]（共i-1個(gè)元素）的排序，它是小問題。對應(yīng)的遞推關(guān)系：f(R，i)≡不做任何事情

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

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

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

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

當(dāng)n=k+1時(shí)對應(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)實(shí)現(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) #反序時(shí)調(diào)用Insert31/58問題描述：一個(gè)機(jī)器人位于一個(gè)m×n（1≤m，n≤100）網(wǎng)格的左上角（起始點(diǎn)標(biāo)記為“Start”）。機(jī)器人每次只能向下或者向右移動一步。

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

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

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

①右右下下

②右下右下

③右下下右

④下右右下

⑤下右下右

⑥下下右右StartFinishmn例如：m=n=334/58上式中分子分母均為x個(gè)連乘，可以進(jìn)一步轉(zhuǎn)換為：由于除法的結(jié)果是實(shí)數(shù)，而不同的路徑數(shù)一定是整數(shù)，所以最后需要將計(jì)算的結(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)上述程序提交時(shí)通過，執(zhí)行時(shí)間為40ms，內(nèi)存消耗14.9MB。x+y→y-1x→136/583.2.4猴子摘桃子問題自學(xué)（歸納法中的逆推法）37/583.3.1迭代法概述3.3迭代法迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值推出新值的過程。通過讓計(jì)算機(jī)對一組指令（或一定步驟）進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值。38/58迭代法算法框架defIterative(): #迭代法框架

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

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

新值取代舊值，為下一次迭代做準(zhǔn)備39/58迭代法算法包含循環(huán)，對循環(huán)的證明引入循環(huán)不變量的概念。循環(huán)不變量是指在每輪迭代開始前后要操作的數(shù)據(jù)必須保持的某種特性（比如在直接插入排序中，排序表前面部分必須是有序的）。循環(huán)不變量是進(jìn)行循環(huán)的必備條件，因?yàn)樗ＷC了循環(huán)進(jìn)行的有效性，有助于理解算法的正確性。循環(huán)體循環(huán)不變量：每輪迭代前后保持不變，從而保證了算法的正確性40/58循環(huán)不變量必須證明它的三個(gè)性質(zhì)：初始化：在循環(huán)的第一輪迭代開始之前，應(yīng)該是正確的。保持：如果循環(huán)的第一次迭代開始之前正確，那么在下一次迭代開始之前它也應(yīng)該保持正確。終止：當(dāng)循環(huán)結(jié)束時(shí)，循環(huán)不變量給了我們一個(gè)有用的性質(zhì)，它有助于表明算法是正確的。41/58【例3-3】采用循環(huán)不變量方法證明3.2.2節(jié)直接插入排序算法的正確性。證明：直接插入排序算法中循環(huán)不變量為R[0..i-1]是遞增有序的。初始化：循環(huán)時(shí)i從1開始，循環(huán)之前R[0..0]只有一個(gè)元素，顯然成立。保持：需要證明每一輪循環(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]中從后向前找到第一個(gè)R[j]≤R[i]，將R[j+1..i-1]均后移一個(gè)位置，并且將原R[i]放在R[j+1]位置，這樣結(jié)束后循環(huán)不變量R[0..i]顯然也是遞增有序的。終止：循環(huán)結(jié)束時(shí)i=n，在循環(huán)不變量中用i替換n，就有R[0..n-1]包含原來的全部元素，現(xiàn)在已經(jīng)排好序了，即說循環(huán)不變量也是成立的。42/583.3.2簡單選擇排序有一個(gè)整數(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)用于實(shí)現(xiàn)R[i..n-1]（共n-i個(gè)元素）的遞增排序，它是大問題，則f(R，i-1)實(shí)現(xiàn)R[i-1..n-1]（共n-i-1個(gè)元素）的排序，它是小問題。f(R，i)≡不做任何事情

當(dāng)i=n-1時(shí)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]中最小元素的下標(biāo)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)): #進(jìn)行n-1趟排序10 Select(a,i)46/58問題描述：給定一個(gè)大小為n的數(shù)組nums，設(shè)計(jì)一個(gè)算法求其中的多數(shù)元素。

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

n/2

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

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

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

def

majorityElement(self,

nums:

List[int])

->

int3.3.4實(shí)戰(zhàn)—多數(shù)元素（LeetCode169）47/58第2章采用哈希映射求解，這里采用迭代法求解。解48/58依題意nums中一定存在多數(shù)元素。通過觀察可以歸納出這樣的結(jié)論：刪除nums中任意兩個(gè)不同的元素，則刪除后多數(shù)元素依然存在且不變。設(shè)候選多數(shù)元素為c=nums[0]，計(jì)數(shù)器cnt表示c出現(xiàn)的次數(shù)（初始為1），i從1開始遍歷nums，若兩個(gè)元素（nums[i]，c）相同，cnt增1，否則cnt減少1，相當(dāng)于刪除這兩個(gè)元素（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:

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

cnt+=1

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

else:11

cnt-=1

#不同遞減cnt，相當(dāng)于刪除這兩個(gè)元素12

if

cnt==0:

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

i+=114

c=nums[i];cnt+=115

i+=116

return

c50/58上述程序提交結(jié)果為通過，運(yùn)行時(shí)間為40ms，消耗空間為16.9MB。如果改為存在多數(shù)元素時(shí)返回多數(shù)元素，否則返回-151/582013年全國考研題41.（13分）已知一個(gè)整數(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個(gè)元素保存在一個(gè)一維數(shù)組中，請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出-1。要求：

（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C或C