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

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

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

直接解決 else:

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

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

直接解決 else:

merge() #合并

recursion2(m) #遞到最深處后，再不斷地歸來6/40【例3-4】假設(shè)二叉樹采用二叉鏈存儲(chǔ)，設(shè)計(jì)一個(gè)算法判斷兩棵二叉樹t1和t2是否相同，所謂相同是指它們的形態(tài)相同并且對(duì)應(yīng)結(jié)點(diǎn)值相同。1234t11234t2t1和t2相同1234t11234t2t1和t2不相同7/40解設(shè)f(t1，t2)表示二叉樹t1和t2是否相同，它們的左右子樹的判斷是兩個(gè)小問題。t1f(t1.left,t2.left)t2f(t1.right,t2.right)f(t1，t2)=true 當(dāng)t1和t2均為空f(t1，t2)=false 當(dāng)t1、t2中一空一非空f(t1，t2)=false 當(dāng)均不空但結(jié)點(diǎn)值不同f(t1，t2)=f(t1.left,t2.left)&&f(t1.right,t2.right) 其他8/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 當(dāng)t1和t2均為空f(t1，t2)=false 當(dāng)t1、t2中一空一非空f(t1，t2)=false 當(dāng)均不空但結(jié)點(diǎn)值不同f(t1，t2)=f(t1.left,t2.left)&&f(t1.right,t2.right)其他end9/403.4.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[i]位置。10/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]:

#當(dāng)相鄰元素反序時(shí)5 a[j],a[j-1]=a[j-1],a[j] #a[j]與a[j-1]進(jìn)行交換6 exchange=True

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

#返回是否存在交換89 defBubbleSort1(a): #迭代算法：冒泡排序10 foriinrange(0,len(a)-1): #進(jìn)行n-1趟排序11 ifnotBubble(a,i):return #本趟未發(fā)生交換時(shí)結(jié)束算法冒泡排序的迭代算法如下，改為單個(gè)算法。11/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）解12/40

設(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個(gè)元素）的排序，它是小問題。當(dāng)i=-1時(shí)，R[0..i]為空，看成是有序的。f(R，i)≡不做任何事情

當(dāng)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)遞推方向13/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)14/40

設(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è)元素）的排序，它是小問題。當(dāng)i=n-1時(shí)，R[n-1..n-1]僅包含最后一個(gè)元素，它一定是最大元素，排序結(jié)束。f(R，i)≡不做任何事情

當(dāng)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)遞推方向15/401 defBubbleSort31(a,i): #遞歸冒泡排序22 ifi==len(a)-1:return #滿足遞歸出口條件3 ifBubble(a,i):BubbleSort31(a,i+1)

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

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

當(dāng)i>1時(shí)19/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個(gè)整數(shù))的每個(gè)位置插入i11 tmp.append(s1) #s1添加到Pi中12 returntmp20/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)21/403.4.4實(shí)戰(zhàn)—字符串解碼（LeetCode394★★）問題描述：給定一個(gè)經(jīng)過編碼的有效字符串s，設(shè)計(jì)一個(gè)算法返回s解碼后的字符串。編碼規(guī)則是用“k[encoded_string]”表示方括號(hào)內(nèi)的

encoded_string

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

保證為正整數(shù)）

次。

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

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

String

decodeString(String

s)

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

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

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

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

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

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

（1）遞歸出口：對(duì)于不包含數(shù)字和括號(hào)的字符串s，直接連接到ans中。例如s="abc"，則ans="abc"。解24/40（2）遞歸體：依題意s是一個(gè)合法的字符串，分為如下幾種情況：s=“k[encoded_string]”，其中encoded_string是一個(gè)合法的字符串，先提取整數(shù)k，再調(diào)用f(encoded_string)求出小問題的結(jié)果，則ans為k個(gè)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"。25/401 class

Solution:2

def

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

#求解算法3

self.i=0

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

return

self.unfold(s)526/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

#后面是一個(gè)']'，跳過該']'18

while

k>0:

#連接tmp字符串k次19

ans+=tmp;k-=120

return

ans;

#s處理完畢返回ans27/40上述程序提交時(shí)通過，執(zhí)行用時(shí)為32ms，內(nèi)存消耗為15MB。28/403.5.1直接展開法3.5遞推式計(jì)算求解遞推式最自然的方法是將其反復(fù)展開。即直接從遞歸式出發(fā)，一層一層地往前遞推，直到最前面的初始條件為止，就得到了問題的解。29/40【例3-8】求解梵塔問題的遞歸算法如下，分析移動(dòng)n盤片的時(shí)間復(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);}}30/40解Hanoi(n，x，y，z)的執(zhí)行時(shí)間為T(n)T(n)=1 當(dāng)n=1T(n)=2T(n-1)+1 當(dāng)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(n-1,y,x,z);}}31/40【例3-9】分析以下遞推式的時(shí)間復(fù)雜度。T(0)=0T(n)=nT(n-1)+n! 當(dāng)n≥1T(n)=nT(n-1)+n!=n[(n-1)T(n-2)+(n-1)!]+n!=n(n-1)T(n-2)+2n!=n!(T(n-2)/(n-2)!+2)構(gòu)造一個(gè)輔助函數(shù)g(n)，令T(n)=n!g(n)（T(0)=g(0)=0），代入后有n!g(n)=n(n-1)!g(n-1)+n!，簡(jiǎn)化為g(n)=g(n-1)+1。展開后有因此，T(n)=n!g(n)=nn!=O(nn!)。解32/403.5.2遞歸樹方法用遞歸樹求解遞推式的基本過程是，展開遞推式，構(gòu)造對(duì)應(yīng)的遞歸樹，然后把每一層的時(shí)間進(jìn)行求和，從而得到算法執(zhí)行時(shí)間的估計(jì)。再用時(shí)間復(fù)雜度形式表示。33/40【例3-10】分析以下遞推式的時(shí)間復(fù)雜度。T(n)=1 當(dāng)n=1T(n)=2T(n/2)+n2

當(dāng)n>1解T(n)(a)初始n2T(n/2)T(n/2)(b)展開T(n)n2(n/2)2(c)展開T(n/2)T(n/4)T(n/4)(n/2)2T(n/4)T(n/4)34/40n2(n/2)2(n/2)2(n/4)2…………高度為log2n+1n2(n/4)2(n/4)2(n/4)2n2/2n2/41111n第1層的問題規(guī)模為n，第2的層的問題規(guī)模為n/2，依此類推，當(dāng)展開到第k+1層，其規(guī)模為n/2k=1，所以遞歸樹的高度為log2n+1。所有層的結(jié)點(diǎn)個(gè)數(shù)T(n)=n2+n2/2+…+n2/2k-1+…+n=O(n2)。35/403.5.3主方法T(1)=cT(n)=aT(n/b)+f(n) 當(dāng)n>1時(shí)求解如下形式遞推式的一般方法其中a≥1，b>1為常數(shù)，n為非負(fù)整數(shù)，T(n)表示算法的執(zhí)行時(shí)間。該算法將規(guī)模為n的原問題分解成a個(gè)子問題，每個(gè)子問題的大小為n/b，f(n)表示分解原問題和合并子問題解得到答案的時(shí)間。36/40主定理：T(n)的計(jì)算如下：若對(duì)于某個(gè)常數(shù)

>0，有f(n)=O()，稱為f(n)多項(xiàng)式地小于

，即f(n)與

的比值小于等于n-

，則T(n)=

()。若f(n)=