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

第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/58

2.穷举法框架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/58

1230012××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初始序列2-5-7j012345a[0..5]={-2，11，-4，13，-5，-2}解法1：设整数序列为a[0..n-1]，枚举所有连续子序列a[i..j]。11/58

1 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