计算机科学导论-基于计算思维的思想与方法（第4版） 课件【ch07】问题求解的算法基础

计算机科学导论基于计算思维的思想与方法问题求解的算法基础第七章新工科建设之路·计算机类系列教材01算法——问题求解的核心算法——问题求解的核心01一、算法的基本概念算法研究史上最著名的古老算法是用于求两个整数的最大公约数的欧几里得(Euclid)算法。这个算法最早出现在大约公元前350——300年由古希腊数学家欧几里得写成的《Elements》(《几何原本》)中，它被人们公认为是算法史上的第一个算法，欧几里得算法的原理是重复应用等式1.算法的起源算法——问题求解的核心01一、算法的基本概念算法是求解问题的方法和步骤，并具有完整的规则。把算法归纳为以下5个显著特征。(1)确定性；(2)有效性；(3)有穷性；(4)有零个或多个输入；(5)有一个或多个输出。2.算法的特征算法——问题求解的核心01二、算法的设计要求1.正确性(Correctness)正确性是指对一切合法的输入，都能在有限次的计算后产生正确的结果。算法的正确是评价一个算法优劣的重要指标，一旦完成对算法的描述，必须证明它是正确的。2.可读性(Readality)可读性是指算法可供人们阅读的容易程度。一个好的算法应便于阅读、理解、编码、修改等。从书写角度来说，结构上要直观、清晰、美观，并在必要的地方加上注释说明。算法——问题求解的核心01二、算法的设计要求3.健壮性(Robustness)健壮性是指一个算法对不合理输入数据的反应能力和处理能力。程序设计时要充分考虑异常情况。健壮性体现了思维的缜密性，如果没有对算法进行仔细认真的考察，特别是极端数据、特殊数据的处理，就很可能使算法失去准确性。4.算法的运行效率算法的运行效率是指在程序执行时，所需耗用的时间和所占用的内存空间。耗用的时间和占用的空间越少，则算法的运行效率越高。算法的运行效率是评价算法好坏的重要指标。算法——问题求解的核心01三、算法的复杂性1.时间复杂度(TimeComplexity)算法的时间复杂度是指度量时间的复杂性，即算法的时间效率的指标。换言之，时间复杂度是与求解问题的规模、算法输入数据相关的函数，该函数表示算法运行所花费的时间。为了简化问题，通常用算法运行某段代码的次数来代替准确的执行时间，记为T(n)。T即Time的首字母，T(n)中的n表示问题规模的大小，一般指待处理的数据量的大小。算法——问题求解的核心01三、算法的复杂性2.空间复杂度(SpaceComplexity)算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。空间复杂度也是与求解问题规模、算法输入数据相关的函数，记为S(n)。空间复杂度的分析方法与时间复杂度的分析是类似的，往往希望算法有常数数量级或多项式数量级的空间复杂度。算法——问题求解的核心01四、算法的描述方法1.用自然语言描述算法自然语言是人们日常所使用的语言，如汉语、英语、日语等。用自然语言描述算法是最原始方法，也是最直观、通俗易懂、为人们所熟悉的方法。算法——问题求解的核心01四、算法的描述方法2.用图形描述算法由于用自然语言描述算法的逻辑结构不是太好，对于稍复杂的算法问题很容易出错，因此常用图形描述算法。目前，用来描述算法的图形有3种：流程图(FlowChart)、N-S图和PAD图，

它们各有其优点，人们更多地习惯用流程图描述算法，并特别适合初学者。算法——问题求解的核心01四、算法的描述方法3.用伪代码描述算法伪代码是一种介于自然语言与高级语言之间描述方法，常用伪代码符号如表7-1所示。算法——问题求解的核心01四、算法的描述方法4.用程序设计语言描述算法无论是用自然语言或伪代码，还是用流程图所描述的算法，都不能被机器识别，最后必须将它们转换成程序设计语言。因此，用程序设计语言来描述算法是最直接有效的方法。存在以下不足：(1)要求设计者必须熟练掌握程序设计语言和编程技巧；(2)要求描述计算步骤的细节，从而忽视了算法的本质；

(3)程序设计语言基于串行，算法的逻辑流程难以遵循，逻辑较复杂时问题越显严重。02数值数据求解——算法策略数值数据求解——算法策略02穷举算法(ExhaustiveAttackAlgorithm)，也称为枚举算法(EnumerateAlgorithm)或称为强力算法(Brute-forceAlgorithm)，是针对要解决的问题，列举所有可能的情况，逐个判断哪些条件符合问题所要求的约束条件，从而得到问题的解。一、穷举算法数值数据求解——算法策略021.算法思想(1)确定范围：按照问题要求确定问题解的大致范围一一列举，遍历所有可能的组合值。(2)条件约束：判断题解是否符合正解条件，避免解题结果错误。(3)循环运算：使可能解的范围降至最小，以便提高解题效益。一、穷举算法数值数据求解——算法策略022.算法特点(1)算法优点：思路简单，问题的答案是一个有穷的集合，可以一一列举出来。(2)算法缺点：运算量比较大，解题效率不高。(3)算法应用：适用于决策类最优化问题。一、穷举算法数值数据求解——算法策略02回溯算法(Back-TrackingAlgorithm)是穷举法和试探法的结合，它将要解决的问题的所有解空间(SolutionSpace)分为若干节点，每个节点有若干可供选择的后续节点，然后按某种顺序逐一穷举和试验。若不满足条件，返回到上一层节点，恢复刚才的参数，再试探其他分支。二、回溯算法数值数据求解——算法策略02二、回溯算法1.算法思想回溯法是一种解决问题的方法，而不是一种特殊算法。回溯算法一般按照以下步骤求解：(1)定义：针对所给问题，定义问题的解空间，至少包含问题的一个最优解；(2)确定：根据定义，确定易于搜索的解空间结构，使得能用回溯方法搜索整个解空间；(3)搜索：以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。数值数据求解——算法策略02二、回溯算法2.算法特点回溯算法本质上是一种穷举法，但它是比穷举“聪明”的搜索技术，有“通用解题法”之称。当一个问题没有显而易见的解法时，可以尝试使用回溯法求解。不过，该算法耗时多，效率低。由于回溯算法是对解空间的深度优先探索，所以在一般情况下可用递归函数来实现回溯算法。数值数据求解——算法策略02三、递推算法递推算法(RecurrenceAlgorithm)是根据问题本身的已知条件，利用特定关系得出中间推论，直至得到结果的算法。递推算法本质上属于归纳法，即根据简单、特殊实例，总结一般性结论。递推算法分为顺推和反推(逆推)两种。顺推是指从已知条件出发，逐步推算出求解结果；反推是指从已知结果出发，用迭代表达式逐步推出问题的开始条件(初始值)，它是顺推的逆过程。数值数据求解——算法策略02三、递推算法1.算法思想递推方法是假设问题在某一步某个条件下成立，下一步可根据这一步所得到的关系进行推导，把一个复杂、庞大的计算过程转化为简单过程的多次重复运算。递推算法一般按以下步骤进行。(1)确定问题数据之间的特定关系，并将这种关系规律归纳成简捷的递推关系式

；(2)确定由已知的基础数据可以递推出后面的数据，而且尽量简化变量，以减少变量暂用空间。数值数据求解——算法策略02三、递推算法2.算法特点每相邻两项之间的变化有一定规律性，通过后项与前项之间的关系，从初始条件入手，一步步地按递推关系进行递推，直到求出最终结果。(1)算法优点：思路简单，无论是程序编写还是程序调试，都很方便，而且程序运行效率高。(2)算法缺点：运算的过程值较多，耗用空间大。适合大、小规模之间的关系。(3)算法应用：适用于已知本身条件，利用特定关系得出中间推论，直至得到最终结果。数值数据求解——算法策略02四、迭代算法迭代算法(IterativeAlgorithm)就是在数的序列中建立起后项与前项之间的关系，通过从一个初始值出发，不断用变量的旧值递推新值的过程。迭代算法包括求精确解和近似解的算法。1.迭代算法思想所谓迭代，就是为了逼近所需目标或结果而重复反馈，每次迭代的结果作为下次迭代的初始值。迭代与递推的区别源于问题的性质，在实际问题中可能遇到以下两种情况。(1)可以表示成数学上明确的递推公式。(2)无法直接写出显式递推公式：只能通过“迭代”，并且可分为精确迭代和近似迭代。数值数据求解——算法策略02四、迭代算法2.算法特点(1)算法优点：对一组指令进行重复执行，每次执行时都从变量的原值中推出它的一个新值。(2)算法缺点：如果方程无解，算法的近似根序列不会收敛，迭代过程失败；如果方程虽然有解但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。(3)算法应用：是递推算法的反推形式，适用于方程求根，方程组求解，矩阵求特征值等。数值数据求解——算法策略02五、递归算法递归算法(RecursiveAlgorithm)是指在定义算法的过程中，用自身的简单情况来定义自身，直接或间接地调用自身的一种算法。一个直接或间接地调用自身的过程称为递归过程(RecursiveProcedure)，一个使用函数自身给出定义的函数称为递归函数(RecursiveFunction)。1.算法思想递归是一种强有力的数学工具，它可使问题的描述和求解变得简洁和清晰，它有两种形式。(1)直接递归(2)间接递归数值数据求解——算法策略02五、递归算法2.算法特点本质上，递归和递推都是同一种解决问题的思路，都是把问题进行分解，但递推是由小到大的推导，而递归则是由大到小的推导。(1)算法优点：程序代码简洁、清晰，可读性好。(2)算法缺点：如果递归层次太深(太多)，会导致堆栈溢出，而且递归算法运行效率较低。(3)算法应用：适用于当问题本身或所涉及的数据结构是递归定义的情况，可与分治法结合。数值数据求解——算法策略02六、分治算法分治算法(DivideandConquerAlgorithm)是将一个难以直接解决的大问题，划分成一些规模较小子问题，以便各个击破。因此，分治算法是一种“分而治之”的算法思想策略。1.算法思想由分治算法产生的子问题往往是原问题的较小模式，最终使子问题缩小到容易直接求解，自然导致递归过程的产生，也为使用递归技术提供了方便。分治算法一般按照以下步骤求解：(1)分解(2)求解(3)合并数值数据求解——算法策略02六、分治算法2.算法特点“分而治之”策略是很多高效算法的思想基础，由分治法产生的子问题往往是原问题的较小或最小模式，这既导致了递归过程的产生，也为使用递归技术提供了方便，最终使子问题缩小到很容易直接求出其解。分治算法与递归算法像一对孪生兄弟经常同时应用在算法设计中，并由此产生许多高效算法，如汉诺塔问题、折半查找、快速排序等，都是分治策略运用的典型实例。数值数据求解——算法策略02七、贪心算法贪心算法(GreedyAlgorithm)是把一一个复杂问题分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解。贪心算法的典型应用是求解最优问题(OptimizationProblem)，即在满足一定约束条件下，使得目标函数的值达到最大或最小。数值数据求解——算法策略02七、贪心算法1.算法思想贪心算法的指导思想是将待求的问题分解成若干子问题进行分步求解，并且每一步总是做出当前最好的选择，即得到局部最优解，然后将各个子问题的局部最优解组合成原问题的一个解。由此可见，贪心算法体现了“快刀斩乱麻”的思想，以当前和局部利益最大化为导向的求解策略。2.算法特点贪心算法是最接近人类日常思维的一种问题求解方法，例如“背包问题”“田忌赛马”等都是典型实例。数值数据求解——算法策略02八、动态规划1.算法思想为了解决某一多阶段决策过程的优化问题，而依次做出n个决策D1，D2，.，Dn；如果这个决策序列是最优的，不论前面决策是怎样的，以后的最优决策取决于由前面决策所确定的当前状态。动态规划一般按照以下步骤求解。(1)划分(2)推导(3)记录数值数据求解——算法策略02八、动态规划2.算法特点(1)算法优点：能够得到全局最优解，可以得到一族最优解，由于动态规划方法反映了动态过程演变的联系和特征，在计算时可以利用实际知识和经验提高求解效率。(2)算法缺点：一是没有统一的标准模型；二是数值方法求解时需要额外的内存空间。(3)算法应用：动态规划方法是解决复杂问题的思维方法，在经济管理、生产调度、工程技术和最优控制值等方面得到广泛应用，用动态规划方法求解比用其它方法求解更为方便、有效。03非数值数据处理——数据结构非数值数据处理——数据结构03一、线性表结构线性表(LinearTable)是由有限个相同的数据元素所构成的序列，通常记为a1，a2，...an。除了第一个元素只有直接后继、最后一个元素只有直接前驱，其余数据元素都有一个直接前驱和一个直接后继。学生档案表是一个典型的线性表。1.线性表的定义非数值数据处理——数据结构03一、线性表结构将一个线性表存储到计算机中可以采用多种不同的方法来实现，通常采用的方法有顺序存储结构(也称为静态存储结构)和链式存储结构(也称为动态存储结构)。2.线性表的实现非数值数据处理——数据结构03一、线性表结构线性表是最简单、最常用的一种数据结构，通常用于对大量数据元素进行随机存取的情况，例如，程序设计中使用的数组和字符串，由学生学籍信息构成的档案表项，用计算机进行学籍管理时对数据表项实现添加、删除、修改、查找、存储等操作，都是线性表的典型应用。若对线性表的这些基本操作加以一定的限制，则形成特殊结构的线性表，即栈结构和队列结构。3.线性表的应用非数值数据处理——数据结构03二、栈结构1.栈结构的定义栈(Stack)或堆栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表，是一种“先进后出”的数据结构，首先存入栈中的元素在栈底(Bottom)，最后存入栈中的元素在栈项(Top)，，它是允许插入或删除的端口，没有元素的堆栈称为空栈。栈结构形如子弹夹，其数据动态如图7-12所示。非数值数据处理——数据结构03二、栈结构2.栈结构的实现栈结构的具体实现取决于栈的存储结构，存储结构不同，其相应的算法描述方法也不同。存储结构通常分为顺序存储和链接存储两种形式。3.栈结构的应用在程序设计中通常用于数据逆序处理的各种场合，如对数据进行首尾元素互换的排序操作、函数嵌套调用时返回地址的存放、编译过程中的语法分析等。在程序设计中，函数嵌套调用和递归调用的实现都包含栈的应用。非数值数据处理——数据结构03三、队列结构队列结构也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。这种逻辑结构被称为队列(Queue)，只允许插入的一端被称为队尾(Rear)，只允许删除的一端被称为队首(Front)。1.队列结构的定义非数值数据处理——数据结构03三、队列结构队列结构可以采用顺序存储结构来实现，也可以采用链表存储结构来实现。顺序存储结构：一般情况下，使用一维数组作为队列的顺序存储空间；再设两个指示器：一个指向队头元素位置的指示器front，另一个指向队尾元素位置的指示器rear。链表存储结构：在一个链表队列中需要设定两个指针(头指针和尾指针)，分别指向队列的头部和尾部。2.队列结构的实现非数值数据处理——数据结构03三、队列结构队列结构可用于应用系统中的事件规划，典型的实例是CPU资源的竞争问题，如在操作系统中用来解决主机与外部设备之间速度不匹配或多个用户引起的资源竞争问题。3.队列结构的应用非数值数据处理——数据结构03四、树结构1.树结构的定义树结构(TreeStructure)是一种非常重要的非线性数据结构，该结构因节点之间存在的分支、层次关系非常类似一颗倒立的树而得名。(Subtree)。树的定义是递归的，深刻地反映了树的固有特性，即一棵非空树是由若干子树构成的，而子树又可由若干更小的子树构成。非数值数据处理——数据结构03四、树结构2.二叉树和哈夫曼树二叉树是指每个节点的度至多为2的有序树，如图7-15所示。哈夫曼树又称为最优二叉树，是指对于一组带有确定权值的叶节点构造出具有最小带权路径长度(最精简、最高效描述)的二叉树。非数值数据处理——数据结构03四、树结构3.二叉树的实现二叉树的实现可以采用顺序存储结构，也可以采用链表存储结构，但主要采用链表存储结构。顺序存储结构：完全二叉树采用自上而下，每层自左向右的顺序存储；非完全二叉树也按完全二叉树的形式来存储，不过需要增加空节点。链表存储结构：用顺序存储结构存放一般的二叉树比较浪费存储空间，所以通常采用链表的方式存储。非数值数据处理——数据结构03四、树结构4.二叉树的遍历遍历(Traversal)是指沿着某条搜索路线依次对树中每个节点仅做一次访问。二叉树遍历的实质是将非线性结构的数据线性化的过程，并先遍历左子树，再遍历右子树。5.树结构的应用树结构在计算机领域中具有广泛应用。例如，在编译系统中，用树来表示源程序的语法结构；在人工智能系统中，用树来描述数据模型；在文件系统中，用树来描述目录结构；在数据库中，用树结构来组织信息和大型列表的搜索。04数据元素操作——查找和排序数据元素操作——查找和排序04一、查找算法1.顺序查找(SequentialSearch)顺序查找，又称为线性查找，是一种最简单的查找算法，既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。(1)顺序查找算法思想：顺序查找是从线性表的一段开始，顺序扫描该线性表。(2)顺序查找算法分析：对n个元素进行顺序查找，若查找成功，则所需比较关键字的次数最少为1，即R[n]