离散数学及其应用第2章-整数与算法基础(下)课件.pptx

1、2022-8-5计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-8-5计算机应用技术研究所计算机应用技术研究所2第第2 2章章 整数与算法设计基础整数与算法设计基础（下）（下）2022-8-52022-8-5整数的基本知识整数的基本知识1 1 同余算术及其应用同余算术及其应用2 2算法设计策略与应用算法设计策略与应用4 4 算法设计的基本知识算法设计的基本知识3 3&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所4算法算法

2、设计的基本知识设计的基本知识&算法设计的算法设计的基本知识基本知识J 算法的基本概念算法的基本概念4 算法效率的度量算法效率的度量4 算法设计应用举例算法设计应用举例2022-8-5计算机应用技术研究所计算机应用技术研究所6&算法的概念算法的概念计算机是处理数据并将数据转化为有用信息的电子设备。任何计算机都由程序指令控制，程序指令规定计算机的用途，并告诉计算机需要完成的工作。因此，要使计算机工作就需要编写计算机程序，告诉计算机如何按照步骤执行程序，以实现最终目标。2022-8-5计算机应用技术研究所计算机应用技术研究所7&算法的概念算法的概念从广义上讲，算法是指通过运算的方式按照某种机械的步骤

3、逐步实现对问题的求解，从这个角度看，现实生活中的很多工作流程都可以看成是算法，例如烧菜的菜谱、理发的流程等，都可以叫算法。从狭义上讲，算法是一个由已知推求未知的过程，对于符合一定规范的输入，它能够在有限的时间内获得所需的输出。2022-8-5计算机应用技术研究所计算机应用技术研究所8&算法的基本性质算法的基本性质1.1.有穷性有穷性：算法中每条指令的执行次数和时间均有限。执行次数或执行时间无穷的算法，对实际生产生活几乎没有意义，而且还会造成资源浪费。2.2.确定性确定性：对算法的描述必须无歧义，以保证算法执行结果是确定的，且符合要求和期望。如果算法对于同样的输入，在相同环境下产生不确定的结果，

4、则是不能接受的。3.3.输入输入：一个算法有0个或多个输入，以确定运算对象的初始情况。所谓0个输入是指算法本身给定了初始条件。4.4.输出输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。5.5.可行性可行性：算法中有待实现的运算都是基本运算，算法原则上要能够精确地运行，且人们用笔和纸做有限次运算后就可以完成。2022-8-5计算机应用技术研究所计算机应用技术研究所9&算法的基本要素算法的基本要素算法的实现形式有多种，但是这些实现形式都具有相同的基本运算和操作。算术运算：加减乘除等运算；关系运算：大于、小于、等于、不等于等运算；逻辑运算：或、与、非等运算

5、；数据操作：输入、输出、赋值等运算。算法的控制结构确定了算法的基本框架，决定着各个操作的执行顺序。算法控制结构有三种，即顺序结构、选择结构和循环结构。在计算机领域，算法的操作对象是数据。具体实际问题及其数学模型的结构特点决定了数据之间总是存在着一些特定的逻辑关系或逻辑结构。这些存储结构和逻辑结构统称为数据结构。2022-8-5计算机应用技术研究所计算机应用技术研究所10&总总 结结简单地说，算法就是解决问题的程序或步骤。可以一步步进行，每一步都能得到唯一的结果。算法一般是刻板的，枯燥的，有时需要进行大量重复的计算，显示了其“机械化”(也叫傻瓜化”)的特点。实际上，处理任何问题都需要算法;象棋有

6、象棋的棋谱，电视有电视的说明书，邮寄物品有其相应的手续.算法与具体问题的解法既有联系，又有区别，它们之间是一般和特殊，抽象与具体的关系1234&算法设计的基本知识算法设计的基本知识4 算法的基本概念算法的基本概念J 算法效率的度量算法效率的度量4 算法设计应用举例算法设计应用举例2022-8-5计算机应用技术研究所计算机应用技术研究所12&算法效率的度量算法效率的度量度量算法的效率：度量算法的效率：时间复杂度；时间复杂度；空间复杂度。空间复杂度。2022-8-5计算机应用技术研究所计算机应用技术研究所13&时间复杂度时间复杂度时间复杂度时间复杂度：一般情况，算法中基本操作重复执行的次数是问题规

7、模n的一个函数f(n)，算法的时间度量记做T(n)=O(f(n)，表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度渐近时间复杂度，简称时间复杂度时间复杂度。2022-8-5计算机应用技术研究所计算机应用技术研究所14&时间复杂度时间复杂度 为了更好地分析算法的效率，需要一些合适的方法来描述或度量函数值随自变量增长而增长的速度，如果不能精确地算出函数增长的速度，那么至少也要针对函数增长的不同速度划分出若干性质不同的等级，这就是函数增长的阶函数增长的阶。2022-8-5计算机应用技术研究所计算机应用技术研究所15&时间复杂度时间复杂度另一方面，例如若复

8、杂度为多项式x x+x x，x的复杂度会被x的复杂所吸收，因此只需考虑最高阶最高阶。因此当输入规模足够大时，精确表示的运行时间函数中的常系数和低阶项会被输入规模所掩盖。此时，只需要考虑高阶高阶项项即可。2022-8-5计算机应用技术研究所计算机应用技术研究所16&时间复杂度时间复杂度 对于绝大多数算法来说，其复杂度的增长速度还可以使用基本或常用函数增长类型通过示例性的方法来描述或表示，如常数级、对数级、多项式级、指数级、阶乘级增长速度，等等。下面介绍一些常见的时间复杂度时间复杂度。2022-8-5计算机应用技术研究所计算机应用技术研究所17&时间复杂度时间复杂度2022-8-5计算机应用技术研

9、究所计算机应用技术研究所18&时间复杂度时间复杂度2022-8-5计算机应用技术研究所计算机应用技术研究所19&时间复杂度时间复杂度2022-8-5计算机应用技术研究所计算机应用技术研究所20&空间复杂度空间复杂度空间复杂度：空间复杂度：一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间辅助空间。&算法设计的基本知识算法设计的基本知识4 算法的基本概念算法的基本概念4 算法效率的度

10、量算法效率的度量J 算法设计应用举例算法设计应用举例2022-8-5计算机应用技术研究所计算机应用技术研究所22&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所23&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所24&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所25&例例 题题【例题】（找假币问题）有12枚外观相同的硬币，要么全是真币，要么仅有一枚是假币。我们并不知道假币比真币重还是轻，你可以使用一个没有砝码的两盘天平秤，确定是否所有的硬币都是真币。如果有假币，找出那个假币并判断假币和真币相比孰轻孰重。设计一个算法，能够在使用最少称

11、重次数的情况下解决设计一个算法，能够在使用最少称重次数的情况下解决这个问题。这个问题。2022-8-5计算机应用技术研究所计算机应用技术研究所262022-8-5计算机应用技术研究所计算机应用技术研究所27&例例 题题【例题】（受限汉诺塔问题）如图（受限汉诺塔问题）如图2-22-2所示。设计一个所示。设计一个算法来求解该问题，使得所有的移动次数最小。算法来求解该问题，使得所有的移动次数最小。2022-8-5计算机应用技术研究所计算机应用技术研究所28&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所29&例例 题题【解】续2）将源柱子上最下面的盘子移动到中间柱子上，如下图所示

12、。2022-8-5计算机应用技术研究所计算机应用技术研究所30&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所31&例例 题题【解】续4）将中间柱子上的盘子移动到目的柱子上，如下图所示。2022-8-5计算机应用技术研究所计算机应用技术研究所32&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所33&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所342022-8-52022-8-5整数的基本知识整数的基本知识1 1 同余算术及其应用同余算术及其应用2 2算法设计的基本算法设计的基本知识知识3 3算法设计策略与应用算法设计策略与应用4 4

13、&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所36算法设计策略与应用算法设计策略与应用&算法设计策略与应用算法设计策略与应用J 蛮力与贪心策略蛮力与贪心策略4 递归与分治策略递归与分治策略4 回溯与动态规划策略回溯与动态规划策略2022-8-5计算机应用技术研究所计算机应用技术研究所38&算法设计算法设计思考一下，如何用算法解决以下数学问题？2022-8-5计算机应用技术研究所计算机应用技术研究所39&算法设计算法设计计算机问题求解算法虽然千差万别，但都遵循一些基本的设计策略。这些策略蕴含着很多非常深刻而又普适的求解智慧。通过不断学习、领会和掌握这些智慧，就

14、可逐步形成良好的算法思维，从而能够更加透彻地从本质上理解算法设计的精髓，为设计出高水平算法打下坚实的基础。2022-8-5计算机应用技术研究所计算机应用技术研究所40&蛮力策略蛮力策略l 就像宝剑不是撬棍一样，科学也很少使用蛮力l 认真做事往往是浪费时间蛮力真的没用吗？2022-8-5计算机应用技术研究所计算机应用技术研究所41&蛮力策略蛮力策略蛮力策略或蛮力法，亦称为穷举法或暴力法，就是用最原始、最暴力的方式解决问题，基本思路是以扫描的模式依次处理问题域所有元素，并将所有可能的结果枚举出来，进而实现对问题的求解。从算法思想的角度来看，蛮力法直接基于问题的描述和所涉及概念的定义来解决问题，即用

15、最直接的方式解决问题。2022-8-5计算机应用技术研究所计算机应用技术研究所42&蛮力策略蛮力策略2022-8-5计算机应用技术研究所计算机应用技术研究所43&算法思想算法思想p Step 1将模式对准文本的前m个字符p Step 2 从左到右匹配每一对相应的字符直到所有字符全部匹配;or有一对字符不匹配p Step 3 当模式未能匹配且文本尚未穷尽，将模式右移一位，返回Step 22022-8-5计算机应用技术研究所计算机应用技术研究所44&算法伪码描述算法伪码描述2022-8-5计算机应用技术研究所计算机应用技术研究所45&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究

16、所46&例例 题题【解】不失一般性，假定出发城市和终止城市都是A（因为一个合法的周游方案是一个城市圈，因此这样的假定不会对问题产生影响）。由于该问题的规模比较小，只有4个城市，我们使用蛮力法求解，如表2-5所示，穷举了所有出发城市和终止城市都是A的周游方案。2022-8-5计算机应用技术研究所计算机应用技术研究所47&总结总结n 蛮力法是一种简单直接地解决问题的方法，通常直接基于问题的描述和所涉及的概念定义。n 蛮力法的主要优点是它广泛的适用性和简单性;它的主要缺点是大多数蛮力算法的效率都不高。n 除了相关问题的一些规模非常小的实例，穷举查找法几乎是不实用的。2022-8-5计算机应用技术研究

17、所计算机应用技术研究所48&贪心策略贪心策略将问题的求解过程看作是一系列选择，每次选择一个输入，每次选择都是当前状态下的最好选择(局部最优解)。每作一次选择后，所求问题会简化为一个规模更小的子问题。从而通过每一步的最优解逐步达到整体的最优解。2022-8-5计算机应用技术研究所计算机应用技术研究所49&贪心算法贪心算法2022-8-5计算机应用技术研究所计算机应用技术研究所50&算法伪码算法伪码2022-8-5计算机应用技术研究所计算机应用技术研究所51&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所52&例例 题题【解】可以使用用贪心算法解决这个问题。贪心策略如下：为了使

18、得会议室能够满足更多同学和老师的需求，我们总是选择在当前状态下，结束时间最早且在时间安排上无冲突的会议，如此选择会使得剩余时间最多，以便安排后续会议。按上述标准，不断重复地进行局部最优选择，直至所有会议都安排上或者时间安排满，由此得到问题的最优解。具体实现过程如图2-9所示。2022-8-5计算机应用技术研究所计算机应用技术研究所53&例例 题题根据算法思想：a.首先选取会议结束时间最早的会议，即会议1，其结束时间为4；b.当继续选择会议结束时间第二早的会议2时，由于该会议开始时间与会议1结束时间产生冲突，因此放弃会议2的安排；继续选择第三早的会议3，此时会议3情况和会议2情况类似，也不予安排

19、；c.当继续选择会议结束时间第四早的会议4时，由于会议4的开始时间与会议1结束时间并未冲突，故可安排会议4；d.以此类推，不再赘述，完整过程参见图2-9。2022-8-5计算机应用技术研究所计算机应用技术研究所54&总结总结对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的,但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此,选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。&算法算法设计策略与应用设计策略与应用4 蛮力与贪心策略蛮力与贪心策略J 递归与分治策略递归与分治策略4 回溯与动态规划策略回溯与

20、动态规划策略2022-8-5计算机应用技术研究所计算机应用技术研究所56&递归策略递归策略2022-8-5计算机应用技术研究所计算机应用技术研究所57&递归策略递归策略n 递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程;n 到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回;n 返回到最外层的调用语句时递归算法执行过程结束。2022-8-5计算机应用技术研究所计算机应用技术研究所58&递归算法的基本要求递归算法的基本要求2022-8-5计算机应用技术研究所计算机应用技术研究所59&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所60&分治策略分

21、治策略2022-8-5计算机应用技术研究所计算机应用技术研究所61&分治策略分治策略对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，求解这些子问题，然后将各子问题的解合并得到原问题的解。2022-8-5计算机应用技术研究所计算机应用技术研究所62&分治策略分治策略分治算法步骤：（1）将原问题分解为若干相同的子问题；（2）若子问题的规模容易解决则直接求解，否则继续分解；（3）将子问题的解合并得到原问题的解，当遇到如折半查找等某些不必求出所有子问题的解的情况时，则省略合并操作。2022-8-5计

22、算机应用技术研究所计算机应用技术研究所63&分治递归分治递归&分治递归分治递归2022-8-5计算机应用技术研究所计算机应用技术研究所65&分治递归分治递归递推关系算法的复杂度2022-8-5计算机应用技术研究所计算机应用技术研究所66&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所67&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所68&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所69&时间复杂度分析时间复杂度分析2022-8-5计算机应用技术研究所计算机应用技术研究所70&总结总结 由分治法所得到的子问题与原问题具有相同的类型。

23、如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。要使分治算法效率高，关键在于如何分割?一般地，出于一种平衡原则，总是把大问题分成K个规模尽可能相等的子问题。&算法设计策略与应用算法设计策略与应用4 蛮蛮力与贪心策略力与贪心策略4 递归与分治策略递归与分治策略J 回溯与动态规划策略回溯与动态规划策略2022-8-5计算机应用技术研究所计算机应用技术研究所72&回溯策略回溯策略2022-8-5计算机应用技术研究所计算机应用技术研究所73&回溯策略回溯策略【定义【定义2.232.23】回

24、溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。2022-8-5计算机应用技术研究所计算机应用技术研究所74&回溯的基本思想回溯的基本思想1、回溯法主要思想是每次只构造解的一个分量，然后按照鲜明的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束,我们就接受对下一个分量所作的第一个合法选择。如果无法对下一个分量进行合法的选择，就不对剩下的任何分量再做任何选择了。在这种情况下，该算法进行回溯，把部分构造解的最后一

25、个分量替换为它的下一个选择。2、解空间树:通过对所做的选择结构构造一棵解空间树，树根代表了在查找解之前的初始状态。树的第一层节点代表对解的第一个分量所做的选择，第二层节点代表了对解的第二个分量所做的选择，以此类推。如果一个部分构造解(子树)仍然有可能导致一个完整解,我们说这个部分解在树中的相应节点是有希望的。否则说是没希望的。叶子要么代表没希望的,要么代表算法找到完整解2022-8-5计算机应用技术研究所计算机应用技术研究所75&回溯算法的解空间回溯算法的解空间2022-8-5计算机应用技术研究所计算机应用技术研究所76&剪剪 枝枝回溯算法需要搜索整棵解空间树，当问题规模很大时，计算量比较大。

26、此时可用剪枝的方法对搜索策略进行优化。【定义定义2.242.24】剪枝就是通过某种判断避免一些不必要的遍历过程，剪去解空间树中的一些不必要的枝条，从而缩小搜索规模。2022-8-5计算机应用技术研究所计算机应用技术研究所77&剪枝策略剪枝策略A.用约束函数在扩展节点处剪去不满足约束条件的子树；B.用限界函数剪去不能得到最优解的子树。对于限界函数，一般是添加一个全局变量记录当前最优解，在到达节点时计算该节点预期值并与当前最优解比较，若不好，则回溯。剪纸函数的两种策略：2022-8-5计算机应用技术研究所计算机应用技术研究所78&回溯策略的步骤回溯策略的步骤(1)定义问题的解空间；(2)确定解空间

27、结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。2022-8-5计算机应用技术研究所计算机应用技术研究所79&回溯法算法流程回溯法算法流程2022-8-5计算机应用技术研究所计算机应用技术研究所80&N N皇后问题皇后问题2022-8-5计算机应用技术研究所计算机应用技术研究所81&问题分析问题分析&4 4皇后问题的解皇后问题的解使用回溯算法搜索其解空间的排列树时过程如下图所示，图中(a,b)表示皇后放置在第a行第b列。&N N皇后问题的解皇后问题的解&8 8皇后问题的解皇后问题的解该解的8元组表示：（4,6,8,2,7，1,3,5）&总总 结结&动态规划策略动态规

28、划策略当问题的数学模型是递推式时，按理应该使用递归算法求解。但是，递归算法有时存在大量重复计算，使得算法时间复杂度过高。实际上，不同子问题的个数往往只有多项式数量级，若将已经计算过的子问题中间数据和计算结果记录下来，需要某个子问题的解时就直接调用，则可避免大量的重复计算。动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。可以看出，动态规划采用的是以空间换取时间的策略&动态规划的有效性动态规划的有效性动态规划法的有效性依赖于求解问题的两个重要性质：1.1.最优子结构性质最优子结构性质 如果问题最优解所包含子问题的解也是最优的，则称该问题具有最优子

29、结构性质。最优子结构性质是动态规划求解问题的必要条件。2.2.子问题重叠性质子问题重叠性质 子问题重叠性质是指在用递归算法由自顶向下的方式对问题求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。当再次需要计算已经计算过的子问题时，无需再次计算，只需查表即可。&动态规划的求解步骤动态规划的求解步骤a)把所有最优化问题分成若干个阶段，找出最优解的性质，并刻画其结构特性。b)将问题发展到各个阶段时所处的不同状态表示出来，确定各个阶段状态之间的递推（或递归）关系，并确定初始（边界）条件。c)应用递推（或递归）关系求解最优值。d)根据计算最优值时得到的信息，构造最优解。&例例 题题【例】一些硬币随机散步在nm的方格板上，一枚硬币占据一个方格，在板上左上角的方格里有一个机器人，它将尽可能多地收集硬币并把这些硬币带到最右下角的方格里，机器人向右或向下移动一格算作一步。每当机器人移动到一个方格就会收集该方格里的硬币。设计一个算法计算机器人所能收集硬币的最大数目以及相应的收集路径。&例例 题题&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所92