《算法设计与分析基础》（Python语言描述） 课件 第3章基本算法设计方法1

第3章必备技能—基本算法设计方法3.1穷举法3.2归纳法CONTENTS提纲3.3迭代法3.4递归法3.5递推式计算1/58穷举法又称枚举法或者列举法，是一种简单而直接地解决问题的方法。基本思想是先确定有哪些穷举对象和穷举对象的顺序，按穷举对象的顺序逐一列举每个穷举对象的所有情况，再根据问题提出的约束条件检验哪些是问题的解，哪些应予排除。3.1.1穷举法概述3.1穷举法1.什么是穷举法2/58常用的列举方法顺序列举。是指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变化顺序去列举。排列列举。有时答案的数据形式是一组数的排列，列举出所有答案所在范围内的排列，为排列列举。组合列举。当答案的数据形式为一些元素的组合时，往往需要用组合列举。组合是无序的。3/58穷举法的作用理论上讲穷举法可以解决可计算领域中的各种问题。在实际应用中，通常要解决的问题规模不大，用穷举法设计的算法其运算速度是可以接受的。举法算法一般逻辑清晰，编写的程序简洁明了。穷举法算法一般不需要特别证明算法的正确性。穷举法可作为某类问题时间性能的底限，用来衡量同样问题的更高效率的算法。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】鸡兔同笼问题。现有一笼子，里面有鸡和兔子若干只，数一数，共有a个头，b条腿。设计一个算法求鸡和兔子各有多少只？解x表示鸡的只数，y表示兔的只数，那么穷举对象就是x和y，假设穷举对象的顺序是先x后y（本问题中也可以先y后x）。x和y的取值范围都是0～a，约束条件

p(x，y)为x+y=aand2x+4y=b。6/58解空间树中共21个结点，显然结点个数越多时间性能越差！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优化：鸡的只数最多为min(a，b/2)，兔的只数最多为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个结点！尽管穷举法算法通常性能较差，但可以以它为基础进行优化继而得到高性能的算法，优化的关键是能够找出求解问题的优化点！×9/58给定一个含n（n≥1）个整数的序列，要求求出其中最大连续子序列的和。序列（-2，11，-4，13，-5，-2）的最大连续子序列和为20。序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大连续子序列和为16。规定一个序列最大连续子序列和至少是0，如果小于0，其结果为0。3.1.2最大连续子序列和10/58-20i9152183134115117201513-211-413-5-2初始序列-49421386-2-5-7j012345a[0..5]={-2，11，-4，13，-5，-2}解法1：设整数序列为a[0..n-1]，枚举所有连续子序列a[i..j]。11/581 defmaxSubSum1(a): #解法12 n,maxsum=len(a),03 foriinrange(0,n): #两重循环穷举所有的连续子序列4 forjinrange(i,n):5 cursum=0;6 forkinrange(i,j+1):cursum+=a[k]7 maxsum=max(maxsum,cursum) #比较求最大maxsum8 returnmaxsum12/58解法2：优化点利用前缀和用presum[i]表示子序列a[0..i-1]元素和即a中前i个元素和，显然有如下递推关系：

presum[0]=0presum[i]=presum(i-1)+a[i-1] 当i>0时假设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）循环可以求出所有连续子序列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：优化点避免起始下标i开始的子序列的重复计算。用Sum(a[i..j])表示子序列a[i..j]元素和，初始时置Sum(a[i..j])=0，显然有如下递推关系：

Sum(a[i..j])=Sum(a[i..j-1])+a[j] 当j≥i时连续求a[i..j]子序列和（j=i，i+1，…，n-1）时没有必要使用循环变量为k的第3重循环。-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：优化点

maxsum至少为0。a[0..5]={-2， 11， -4， 13， -5， -2}maxsum=0,cursum=0（cursum表示以a[i]结尾的最大和）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结果：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）个整数的数组

nums，设计一个算法找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

例如，nums={-2，1，-3，4，-1，2，1，-5，4}，答案为6，对应的连续子数组是{4，-1，2，1}。

要求设计如下方法：

def

maxSubArray(self,

nums:

List[int])

->

int:3.1.3实战—最大子序列和（LeetCode53）19/58本题的最大连续子序列和至少包含一个元素，也就是说最大连续子序列和可能为负数。例如，nums={-1，-2}，结果为-1，因此不能直接采用3.1.2节解法4，需要做修改：

将表示结果的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，内存消耗为29.8MB。21/583.2.1归纳法概述3.2归纳法1.什么是数学归纳法第一数学归纳法原理：若{P(1)，P(2)，P(3)，P(4)，…}是命题序列且满足以下两个性质，则所有命题均为真：①P(1)为真。②任何命题均可以从它的前一个命题推导得出。第二数学归纳法原理：若{P(1)，P(2)，P(3)，P(4)，…}是满足以下两个性质的命题序列，则对于其他自然数，该命题序列均为真：①P(1)为真。②任何命题均可以从它的前面所有命题推导得出。22/582.什么是归纳法23/5824/58归纳法

递推关系基本流程：按推导问题方向研究最初最原始的若干问题。按推导问题方向寻求问题间的转换规律即递推关系，使问题逐次转化成较低层级或简单的且能解决问题的或已解决的问题。顺推法和逆推法：顺推法是从已知条件出发逐步推算出要解决问题的结果。逆推法从已知问题的结果出发逐步推算出问题的开始条件。25/58数学归纳法不是归纳法，但它与归纳法有着一定程度的关联。在结论的发现过程中，往往先通过对大量个别事实的观察，通过不完全归纳法归纳形成一般性的结论，最终利用数学归纳法对结论的正确性予以证明。26/583.2.2直接插入排序有一个整数序列R[0..n-1]，采用直接插入排序实现R的递增有序排序。直接插入排序的过程是，i从1到n-1循环，将R[i]有序插入到R[0..i-1]中。27/58

采用不完全归纳法产生直接插入排序的递推关系。

例如R=（2，5，4，1，3），这里n=5，用[]表示有序区，各趟的排序结果如下：初始：

（[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

设f(R，i)用于实现R[0..i]（共i+1个元素）的递增排序，它是大问题，则f(R，i-1)实现R[0..i-1]（共i-1个元素）的排序，它是小问题。对应的递推关系：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)用于实现R[0..n-1]的递增排序。采用不完全归纳法得到的结论是否正确呢？

①证明归纳基础成立。当n=1时直接返回，由于此时R中只有一个元素，它是递增有序的，所以结论成立。

②证明归纳递推成立。假设n=k时成立，也就是说f(R，k-1)用于实现R[0..k-1]的递增排序。

当n=k+1时对应f(R，k)，先调用f(R，k-1)将R[0..k-1]排序，再将R[k]有序插入到R[0..k-1]中，这样R[0..k]变成递增有序序列了，所以f(R，k)实现R[0..k]的递增排序，结论成立。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] #将关键字大于a[i]的元素后移6 j-=17 ifnot(j>=0anda[j]>tmp):8 break #循环到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) #反序时调用Insert31/58问题描述：一个机器人位于一个m×n（1≤m，n≤100）网格的左上角（起始点标记为“Start”）。机器人每次只能向下或者向右移动一步。

设计一个算法求机器人达到网格的右下角（标记为“Finish”）总共有多少条不同的路径。

例如，m=3，n=3，对应的网格如下图所示，答案为6。StartFinish3.2.3实战—不同路径（LeetCode62★★）32/58解从左上角到右下角的任意路径中，一定是向下走m-1步向右走n-1步，不妨置x=m-1，y=n-1，路径长度为x+y。StartFinishmn归纳：不同路径条数等于x+y个选择中挑选x个“下”或者y个“右”的组合数，即

或者，为了方便假设x≤y，结果取33/58所有路径长度为4，=6条不同的路径如下：

①右右下下

②右下右下

③右下下右

④下右右下

⑤下右下右

⑥下下右右StartFinishmn例如：m=n=334/58上式中分子分母均为x个连乘，可以进一步转换为：由于除法的结果是实数，而不同的路径数一定是整数，所以最后需要将计算的结果四舍五入得到整数答案。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)上述程序提交时通过，执行时间为40ms，内存消耗14.9MB。x+y→y-1x→136/583.2.4猴子摘桃子问题自学（归纳法中的逆推法）37/583.3.1迭代法概述3.3迭代法迭代法也称辗转法，是一种不断用变量的旧值推出新值的过程。通过让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。38/58迭代法算法框架defIterative(): #迭代法框架

迭代变量赋初值 while(迭代条件成立:

根据递推关系式由旧值计算出新值

新值取代旧值，为下一次迭代做准备39/58迭代法算法包含循环，对循环的证明引入循环不变量的概念。循环不变量是指在每轮迭代开始前后要操作的数据必须保持的某种特性（比如在直接插入排序中，排序表前面部分必须是有序的）。循环不变量是进行循环的必备条件，因为它保证了循环进行的有效性，有助于理解算法的正确性。循环体循环不变量：每轮迭代前后保持不变，从而保证了算法的正确性40/58循环不变量必须证明它的三个性质：初始化：在循环的第一轮迭代开始之前，应该是正确的。保持：如果循环的第一次迭代开始之前正确，那么在下一次迭代开始之前它也应该保持正确。终止：当循环结束时，循环不变量给了我们一个有用的性质，它有助于表明算法是正确的。41/58【例3-3】采用循环不变量方法证明3.2.2节直接插入排序算法的正确性。证明：直接插入排序算法中循环不变量为R[0..i-1]是递增有序的。初始化：循环时i从1开始，循环之前R[0..0]只有一个元素，显然成立。保持：需要证明每一轮循环都能使循环不变量保持成立。对于R[i]排序的这一趟，之前R[0..i-1]是递增有序的：①如果R[i]≥R[i-1]即正序，则该趟结束，结束后循环不变量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]位置，这样结束后循环不变量R[0..i]显然也是递增有序的。终止：循环结束时i=n，在循环不变量中用i替换n，就有R[0..n-1]包含原来的全部元素，现在已经排好序了，即说循环不变量也是成立的。42/583.3.2简单选择排序有一个整数序列R[0..n-1]，采用简单选择排序实现R的递增有序排序。简单选择排序的过程是：i从0到n-2循环，R[0..i-1]是有序区，R[i..n-1]是无序区，并且前者的所有元素均小于等于后者的任意元素，在R[i..n-1]无序区通过简单比较找到最小元素R[minj]，通过交换将其放在R[i]位置。43/58采用不完全归纳法产生简单选择排序的递推关系。例如R=（2，5，4，1，3），这里n=5，用[]表示有序区，各趟的排序结果如下：初始：

（[]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设f(R，i)用于实现R[i..n-1]（共n-i个元素）的递增排序，它是大问题，则f(R，i-1)实现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的数组nums，设计一个算法求其中的多数元素。

多数元素是指在数组中出现次数大于

n/2

的元素。可以假设中给定的非空数组中总是存在多数元素。

例如数组为{3，2，3}，结果为3。

要求设计如下方法：

def

majorityElement(self,

nums:

List[int])

->

int3.3.4实战—多数元素（LeetCode169）47/58第2章采用哈希映射求解，这里采用迭代法求解。解48/58依题意nums中一定存在多数元素。通过观察可以归纳出这样的结论：删除nums中任意两个不同的元素，则删除后多数元素依然存在且不变。设候选多数元素为c=nums[0]，计数器cnt表示c出现的次数（初始为1），i从1开始遍历nums，若两个元素（nums[i]，c）相同，cnt增1，否则cnt减少1，相当于删除这两个元素（nums[i]删除一次，c也只删除一次）。如果cnt为0说明前面没有找到多数元素，从nums[i+1]开始重复查找即重置c=nums[i+1]，cnt=1。遍历结束后c就是nums中的多数元素。证明略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

#相同时累加次数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上述程序提交结果为通过，运行时间为40ms，消耗空间为16.9MB。如果改为存在多数元素时返回多数元素，否则返回-151/582013年全国考研题41.（13分）已知一个整数序列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中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C