Python程序设计实践 课件 ch03 典型算法介绍

第三章典型算法介绍浙江省普通本科高校“十四五”重点教材Python程序设计实践教程01枚举算法PARTONE1.算法定义枚举算法（ExhaustAlgorithm）又叫穷举法，也称为暴力破解法，是指针对要解决的问题，列举出所有可能的情况，逐个判断哪些符合问题所要求的约束条件，从而得到问题的解。2.算法特点这种算法充分利用计算机语言的循环结构，其优点是思路简单，程序编写和调试都很方便。如果问题规模不是很大，要在规定的时间与空间内求出解，那么枚举算法是最直接、简单的选择。这种算法的缺点是运算量比较大、解题效率不高。如果枚举范围太大（超过2000000次），会花费大量时间。3.算法思路这种算法的基本思想是根据问题的条件确定大致范围，并在该范围内进行穷举并验证，直到问题得到解决。这种算法一般用于决策最优化问题，适合那些很难找到大、小规模之间的关系，也不易进行分解的问题。第一步确定解题范围，枚举出所有可能的解。第三步使可能解的范围降至最小，以便提高解题效率。第二步判断是否符合正解的条件。4.算法案例【例】“百鸡百钱”问题中国古代数学家张丘建在《算经》中提出了著名的“百鸡百钱”问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？（已知公鸡每只5元，母鸡每只3元，小鸡1元3只。要求用100元正好买100只鸡，问公鸡、母鸡、小鸡各买多少只？）题目分析：设买x只公鸡、y只母鸡、z只小鸡，则问题转化为三元一次方程组，即x+y+z=100（百鸡），5x+3y+z/3=100（百钱），1个方程无法解出3个变量，只能将各种可能的取值代入，求出能使两个方程成立的解。鸡和钱的总数都是100，因此可以确定x、y、z的取值范围。x的取值范围为1～20（100/5=20），y的取值范围为1～33（100/3≈33），z的取值范围为1～99，求解流程图如图3-1所示。02递归算法PARTTWO1.算法定义递归算法（RecursionAlgorithm）把问题转化为同类问题的子问题，然后通过递归调用过程（或函数）表示问题的解。一个程序过程（或函数）直接或间接调用自己本身，这种过程（或函数）称为递归过程（或函数）。

递归调用分为直接递归和间接递归。直接递归是指在过程中调用方法本身，间接递归是指间接地调用一个过程。一般来说，递归算法需要有边界条件、递归前进段、递归返回段。不满足边界条件时，递归前进；满足边界条件时，递归返回。2.算法特点递归过程一般通过函数或子过程来实现，在函数或子过程的内部直接或间接地调用自身，常用于一些有明显递推性质的问题。递归算法的优点

代码简洁、清晰、可读性好。递归算法的缺点

递归形式比非递归形式的运行速度慢。如果递归层次太深，会导致堆栈溢出。虽然算法代码通常显得很简洁，但递归算法的运行效率较低。所以，如果有别的算法可行，一般不提倡用递归算法设计程序。3.算法思路递归

把一个问题归结为一个或多个规模更小的子问题，然后用同样的方法求解规模更小的子问题，要求子问题与原问题是同一类型，以保证可用同样的方法求解。如此下去，直到子问题的规模小到可以直接求解。递归算法有以下三个基本要求。①每次循环都必须使问题规模变小。②递归操作中相邻的两步是紧密关联的，在返回到上一层的操作中，前一次的输出信息是后一次的输入信息。③当子问题的规模足够小时，能直接求出该子问题的解，也就是说必须具备结束递归的初始条件。4.算法案例【例】阶乘问题阶乘（Factorial）是指1到n之间的所有自然数相乘的结果。在进行问题求解前，首先分析下面的分段函数。f(n)=1，n=1f(n)=nf(n-1)，n>1编写程序时，以fact()函数的调用过程为例，递归调用分为递推和回归两个阶段，如图3-2所示。递归调用4.算法案例【例】汉诺塔（Hanoi）问题汉诺塔问题是一个古典数学问题，只能用递归算法来解决。有一个汉诺塔，塔内有A、B、C三个座。开始时A上有64个盘子，盘子的大小不同，大的在下面，小的在上面，如图3-3所示。现有一个和尚想将这64个盘子从A移动到C上，但他每次只能移动一个盘子。在移动过程中，必须保持A、B、C上的盘子是大盘在下、小盘在上的状态。在移动过程中可以利用B，请分析移动过程。汉诺塔4.算法案例首先考虑A上最下面的盘子，如果能将它上面的63个盘子移动到C上，则完成任务，具体步骤如下。①将A最上面的63个盘子移动到B上。②将A上剩下的一个盘子移动到C上。③将B上的63个盘子移动到C上。如果能完成上述三步，则完成任务，这种方法就是递归的思考方法。为了将A最上面的63个盘子移动到B上，还需要做以下工作。①将A最上面的62个盘子移动到C上。②将A上剩下的一个盘子移动到B上。③将C上的62个盘子移动到B上。03分治算法PARTTHREE1.算法定义分治算法

将一个规模为n的问题分解为k个规模较小的子问题（这些子问题相互独立且与原问题的性质相同），再把子问题分成更小的子问题，直到子问题可以直接进行求解，原问题的解即为子问题解的合并。任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易求解，所需的计算时间也越少。“分而治之”技巧是很多高效算法的基础，如排序算法（快速排序、归并排序等）、傅里叶变换（快速傅里叶变换）等。由分治算法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。2.算法特点当问题的规模缩小到一定程度时，就可以容易地解决。如果问题可以分解为若干个规模较小的相同问题，则该问题具有最优子结构性质。利用子问题的解可以合并出问题的最终解。所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。010203043.算法思路（1）分解将要解决的问题划分成若干规模较小的同类问题。（2）求解当子问题划分得足够小时，用较简单的方法解决。（3）合并按原问题的要求，将子问题的解逐层合并，构成原问题的解。4.算法案例【例】在有序数据数列中查找给定的数设n个有序数（从小到大排序）存放在数组a[0]～a[n-1]中，要查找的数为x。用变量bot、top、mid分别表示所查找的数据范围的底部（序列的下界）、顶部（序列的上界）、中间（mid=(bot+top)/2），算法如下。（1）如果x=a[mid]，则已找到给定的数，退出循环，否则进行下面的判断。（2）如果x<a[mid]，则x必定在bot～mid-1范围内，即top=mid-1。（3）如果x>a[mid]，则x必定在mid+1～top范围内，即bot=mid+1。（4）确定了新的查找范围后，重复进行以上比较，直到找到给定的数或top≤bot。04递推算法PARTFOUR1.算法定义递推算法一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果。顺推法从已知条件出发，逐步推算出要解决的问题。逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始条件，即顺推法的逆过程。3.算法思路递推算法的本质按规律逐次推出（计算）下一步的结果，所以更多用于计算。递推算法是计算序列的一种常用算法，其思想是把一个复杂的、庞大的计算过程转化为简单过程的多次重复，利用了计算机速度快和“不知疲倦”的特点。第一步确定问题的数据信息之间存在着特定的递推关系，并用数学公式描述出来。第三步尽量使用简单变量，使计算的过程值暂用的空间量少，以便提高解题效率。第二步确定由已知的基础数据可以递推出后面的数据。4.算法案例【例】斐波那契数列（FibonacciSequence）问题斐波那契数列是：1，1，2，3，5，8，13，21，34，55，89，144…，求第n项的值。设它的函数为F(n)，已知F(1)=1、F(2)=1，那么F(n)=F(n-1)+F(n-2)(n≥3)，则通过顺推可以知道，F(3)=F(1)+F(2)=2、F(4)=F(2)+F(3)=3……只要配合循环控制序列项编号，就很容易得到想要的项值。05贪心算法PARTFIVE1.算法定义贪心算法将问题的求解过程看作一系列选择，它所作的每一个选择都是当前状态下某种意义上的最优解（即贪心选择），并期望通过每次所作的贪心选择（局部最优解）导致最终结果是问题的一个最优解或近似最优解。2.算法特点有一个以最优方式解决的问题。为了构造问题的解决方案，有一个候选的对象的集合。随着算法的进行，将积累起其他两个集合，一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。有一个函数来检查一个候选对象的集合是否提供了问题的解答，该函数不考虑此时的解决方法是否最优。还有一个函数检查是否一个候选对象的集合是可行的，即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。选择函数可以指出哪个剩余的候选对象最有希望构成问题的解。01020304053.算法思路贪心算法的主要思路如下。①建立数学模型来描述问题。②把求解的问题分成若干个子问题。③对每一子问题求解，得到子问题的局部最优解。④把子问题的局部最优解合成原来问题的一个解。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题选择出最优量度标准后，用贪心算法求解特别有效。4.算法案例【例】背包问题（KnapsackProblem）假设有n个物品和一个背包，物品i的重量是Wi，价值为Pi，背包的载荷能力为M。对于任一物品，该物品只能装入一次，并且不能只装入物品的一部分（要么整体装入背包，要么不装入）。请问：如何选择物品，才能使装入背包中的物品的总价值最大？将该问题转化成数学语言。给定M>0、Wi>0、Pi>0（1≤i≤n），要求找出一个n元向量（X1，X2，…，Xn），使得∑WiXi≤M，而且∑PiXi最大。4.算法案例【例】旅游路径的选择贪心算法也很适合用于旅游路径的选择，如图所示，假如要从节点5走到节点3，最短的路径是什么呢？以贪心算法来说，当然是先走到节点1，接着走到节点2，最后走到节点3，这样的距离是28。可是从图中我们发现直接从节点5走到节点3才是最短的距离，也就是说，在这种情况下无法用贪心算法找到最佳的解决方案。旅游路径的选择06回溯算法PARTSIX1.算法定义回溯算法（Back-TrackingAlgorithm）一种“选优”的搜索方法，按照“选优”的条件向前搜索，以达到目标；如果搜索到某一步时，发现原先的选择并不“优”或达不到目标，就退一步重新选择，这种走不通就退回再走的技术就是回溯算法。2.算法特点回溯算法

沿着一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯算法在迷宫搜索中很常见，如果某条路走不通，就返回前一个路口，继续探寻下一条路。回溯算法其实就是一种枚举算法。不过回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案）的节点，从而减少状态空间树的节点。3.算法思路通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索向前试探，若试探成功，就得到解；若试探失败，就逐步往回退，换别的路线再向前试探。回溯算法实际上是广度与深度结合的搜索方法，深度搜索过程中碰到条件不满足的情况，则退回上一层，进行全面的搜索。4.算法案例【例】老鼠走迷宫一只老鼠在一个n×n迷宫的入口处，它想吃迷宫出口处放着的奶酪，这只老鼠能否吃到奶酪？如果可以吃到，请给出一条从入口到奶酪的路径。老鼠在迷宫的入口处，迷宫中有许多墙，使大部分路径都被挡住而无法前进。老鼠可以采用尝试错误的方法找到出口。不过，这只老鼠必须能在走错路时重来一次并把走过的路记下来，避免下次走同样的路，直到找到出口。老鼠行进时，必须遵守以下三个原则。①一次只能走一格。②遇到墙无法往前走时，退回一步找找看是否有其他路可以走。③走过的路不会再走第二次。4.算法案例在编写走迷宫程序之前，我们先来了解如何在计算机中表现一个仿真迷宫。这时可以使用二维数组，并符合以下规则。maze[i][j]=1表示[i][j]处有墙，无法通行。maze[i][j]=0表示[i][j]处无墙，可通行。一个10×10的迷宫如图所示，灰色部分是墙，白色部分是可以走的路。迷宫的入口在上面，出口在右侧。4.算法案例这个迷宫其实是由10×10=100个格子组成的，灰色格子代表墙，白色格子代表路，如图(a)所示。“灰色格子代表墙，白色格子代表路”是用语言形式描述的，需要转换成数学形式，用1和0分别定义灰色格子和白色格子，如图(b)所示。4.算法案例从数学的角度分析老鼠走迷宫的过程。假设老鼠从左上角的maz