大学计算机基础-计算思维视角 课件 ch06计算平台一一算法与程序设计

算法与程序设计新工科建设之路·计算机类专业精品教材计算平台第六章算法的概念0101算法的概念1.什么是算法算法(Algorithm)一词源于算术(Algorism)，即算术方法，是指一种由已知推求未知的运算过程。后来，人们把进行某一工作的方法和步骤称为算法。随着计算机的出现，算法被广泛地应用于计算机的问题求解中，被认为是程序设计的精髓。在计算机科学中，算法是指问题求解的方法及求解过程的描述，是一个经过精心设计，用以解决一类特定问题的计算序列。01算法的概念2.算法的特性确定性算法中每一个步骤都必须是确切定义的，不能产生二义性，对于相同的输入必须得出相同的执行结果。01可行性算法必须是由一系列具体步骤组成的，并且每一步都能被计算机理解和执行。02有穷性一个算法应包含有限个操作步骤。在执行有限个操作步骤之后，算法能正常结束，而且每一步都能在合理的时间范围内完成。0301算法的概念2.算法的特性有零个或多个输入一个算法可以有零个或多个输入，这取决于算法要实现的功能。这里的输入可能是键盘输入，也可能是从文件中读取的输入。04有一个或多个输出算法的执行结果必须以某种形式反馈给用户，没有输出的算法毫无意义。这里的输出可以是屏幕输出或打印，也可以是将结果保存到文件或数据库中。0501算法的概念3.算法的分类算法的种类很多，分类标准也很多。根据处理的数据是数值数据还是非数值数据，算法可以分为数值计算方法和非数值计算方法。数值计算是指以获得数值结果为目标的计算，主要用于科学计算，其特点是少量的输输出和复杂的运算，如解线性方程组的直接法、解线性方程组的迭代法等算法。入非数值计算的计算对象是信息，包含文字、图形、记录等，目的是对数据进行管理，其特点是大量的输入、输出和大量的逻辑运算，如对数据的排序、查找等算法。在解决非数值计算问题时，可以借鉴一些基础的思维方式，如分治、递归等。02算法的表示1.算法的自然语言描述自然语言就是人们日常使用的语言，可以使用汉语、英语或其他语言等。用自然语言表示算法通俗易懂，但文字冗长，表示的含义往往不太严格，要根据上下文才能判断其正确含义，容易出现歧义性。此外，用自然语言来描述包含分支和循环的算法很不方便，因此除那些简单的问题外，一般不用自然语言描述算法。02算法的表示2.算法的流程图描述流程图(FlowChart)描述是指使用一些几何图形、线条和文字来表示各种操作和处理步骤。用流程图来描述问题的解题步骤，可使算法十分明确，具体直观，易于理解。美国国家标准化协会(AmericanNationalStandardInstitute，ANSI)规定了一些常用的流程图符号。02算法的表示3.算法的伪代码描述由于算法的设计需要反复修改，每次修改均需要重新绘制流程图，而绘图过程较费时,因而为了方便设计算法，常采用伪代码表示。伪代码产生于20世纪70年代，用介于自然语言与计算机语言之间的文字和符号来描述算法。伪代码不使用图形，格式紧凑，易于理解。02算法的表示4.算法的计算机语言描述不管是流程图还是伪代码，最后要让计算机识别并能自动执行，都需要转换成计算机语言编写的程序。用计算机语言描述算法必须严格遵循所选择的编程语言的语法规则。[例6.1]假设期末总评成绩的计算方法平时成绩x0.2+考试成绩X0.8现已知某学生某门课程的平时成绩和考试成绩，计算出该生的总评成绩，并给出该课程是否通过(大于或等于60分为通过)。算法的流程图、伪代码和C语言3种描述方法。03常用的基本算法1.枚举法枚举法也称穷举法、列举法、试凑法、蛮力法等。枚举法的求解思路很简单，就是对所有可能的解逐一尝试，从而找出问题的真正解。枚举法的基本思想是首先依据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能情况逐一验证，直到全部情况验证完。若某个情况经过验证符合题目的全部条件，则为本题的一个答案;若全部情况经过验证后都不符合题目的条件，则本题无解。枚举法是一种比较耗时的算法。由于计算机的运算速度快，擅长重复操作，因此很容易用计算机完成大量的枚举。03常用的基本算法1.枚举法[例6.2]百钱买百鸡问题的枚举法求解过程。03常用的基本算法2.迭代法选代法也称递推法、辗转法等，它是利用问题本身所具有的某种递推关系求解问题的一种方法。迭代法的基本思想是从初值出发，归纳出新值与旧值间存在的关系，这个关系就是迭代递推公式，利用此公式不断地用旧的变量值递推计算新的变量值，从而把一个复杂的计算过程转化为简单过程的多次重复。03常用的基本算法2.迭代法[例6.3]用欧几里得算法求两个任意整数的最大公约数。03常用的基本算法2.迭代法[例6.4]计算任意一个整数的相反数，如整数1389，其相反数是9831。对于任意整数，因不知确定的位数，所以求其相反数的算法可以用如下所示的迭代过程。03常用的基本算法3.递归法若一个算法直接地或间接地调用自己本身，则称这个算法是递归算法。递归法的基本思想是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来进行求解。因为问题规模变小，所以递归策略可以简单描述，且易于理解;解题过程需要多次重复计算，因此递归本质上是一种循环的算法结构。03常用的基本算法3.递归法[例6.5]计算n的阶乘(n!)。03常用的基本算法4.最值算法所谓最值，就是指最大值和最小值。当求最值时，需要有一个变量来记录最大或最小这个变量称为最值变量。求最值的基本思想是首先给最值变量一个初值，然后每个元素依次和最值变量比较遇到比最值变量更大(或更小)的元素时就用其值更新最值变量的值。最值变量的初值可以用元素集合中的第一个数，也可以用一个元素取值范围中的最小数(求最大值时)或最大数(求最小值时)，总之，当求最大值时，最值变量的初值数据一定要保证比所用元素集合中的最小值还要小;当求最小值时，最值变量的初值数据一定要保证比所用元素集合中的最大值还要大。03常用的基本算法4.最值算法[例6.6]找出10个整数中的最大数使用元素集合中的第一个数作为最值变量的初值，描述算法的程序流程图如图6-5所示。设有符号整数占内存空间2个字节，其所表示的数值大小为-32768~32767，当求最大数时，最值变量的初值可用-32768表示，描述算法的程序流程图如图6-6所示。03常用的基本算法5.排序算法所谓排序，就是按某种特定的顺序排列数据，把无序的数据序列调整为有序的数据序列。排序在数据处理领域中应用十分广泛，排序也是计算机程序中经常要用到的基本算法排序的方法有很多，每种排序方法都有其各自的特点和适用场景，本书仅介绍选择排序和冒泡排序。03常用的基本算法5.排序算法选择排序选择排序是一种简单直观的排序算法。它的基本方法是每次先从待排序的无序数中找出最小(或最大)的一个元素，存储在无序数的第一个位置;再从剩余的待排序的无序数中继续找出最小(或最大)的一个元素，存储在无序数的第一个位置或者说是已排序数的末尾位置。以此类推，直到待排序的数据元素的个数为零。0103常用的基本算法5.排序算法[例6.7]用选择排序方法对n个给定的整数降序排序设有49、38、65、76、13、27这6个数存储在数组a中，选择排序过程如图6-7所其中，已有序的数据用一对中括号括起来。降序排序是每次在待排序的数据中找最大数。03常用的基本算法5.排序算法每一轮排序过程相应的伪代码如下，在每一轮排序算法中，不同的部分用粗体进行了区分。03常用的基本算法5.排序算法[例6.8]用冒泡排序方法对n个给定的整数升序排序。设有49、38、657627、13这6个数存储在数组a中冒泡排序过程如图6-8所示其中，每经过一轮比较后，在待排数据中都会有一个大数沉到它的最终位置处，曲线下方的数据是每一轮结束后已经排好序的部分。例如，第1轮，最大数76底，小数13上升一个位置;第2轮，次大数65底，小数13继续上升一个位置，如此循环往复。03常用的基本算法5.排序算法前两轮排序过程相应的伪代码如下，在每一轮排序算法中，不同的部分用粗体进行了区分。当有n个数据时，排序过程最多需要经历n-1轮。用循环控制排序的轮数，最终完整的伪代码如下。03常用的基本算法6.查找算法查找也称检索，是指在大量的数据中寻找某个特定的数据元素。查找算法是常用的基本运算，利用计算机快速运算的特点，可以方便地实现查找。查找的方法很多，对于不同的数据结构，对应有不同的查找策略。本书仅介绍顺序查找和二分法查找。03常用的基本算法6.查找算法顺序查找。顺序查找又称线性查找，它的基本方法是在待查找的数据元素中从一端开始按顺序逐一比较，如果找到与给定值key相同的元素，则查找成功，如果所有元素均比较结束仍没有找到与给定值key相同的元素，则查找失败。顺序查找对数据没有特殊要求，可用于有序列表，也可用于无序列表;可用于线性结构存储的数据，也可用于链式结构存储的数据。最好的情况是比较第1个数时即找到，最坏的情况是比较到第n个数(最后一个数)时才知道结果，因此顺序查找的平均查找次数是(n+1)/2，当n值比较大时，查找效率较低。0103常用的基本算法6.查找算法[例6.9]用顺序查找方法在n个元素中查找值为key的元素。顺序查找过程如图6-9所示。03常用的基本算法6.查找算法二分法查找二分法查找又称折半查找，是在数据量较大时采用的一种高效查找法。当采用二分法查找时，要求数据结构必须是线性存储结构，且数据事先必须有序。猜数游戏使用的就是二分法查找，如果已知猜数范围是1~100的整数，人们一般都会先猜50，若猜大了，下次就会在1~50之间猜25，以此类推，每次猜完后就可以过滤掉一半数据，使得下次要猜的数据量大大减少。二分法查找的基本思想是将待查找数据的中间元素与给定值key相比较，若相等，则查找成功;若不等，则依据数据的排序情况，或者取中间值左边部分，或者取中间值右边部分，作为下一次查找的待查找数据。重复此过程，直到查找成功，或者直到待查找数据不再存在，此时查找不成功。0203常用的基本算法6.查找算法[例6.10]用二分法查找在n个元素中查找值为key的元素。04算法的复杂性分析算法的复杂性分析(AlgorithmComplexityAnalysis)主要针对运行该算法所需要的计算机资源的多少，需要的时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。算法所需要的资源越多，该算法的复杂性越高;反之，算法所需要的资源越少，该算法的复杂性越低。一个特定问题的算法在大部分情况下都不是唯一的，也就是说，同一个问题可以有多种解决问题的算法。算法没有对错之分，但有优劣之分。就好像我们做事情，常常会思考怎样才能高效地解决问题。对于特定的问题、特定的约束条件，设计出复杂性最低的算法是设计算法时追求的重要目标之一，而在存在的多种算法中选取其中复杂性最低的算法也是选用算法遵循的重要标准。用计算机求解问题的难易程度又称为计算复杂性，其实就是度量它的时间复杂性和空间复杂性。04算法的复杂性分析1.时间复杂性时间复杂性(时间复杂度)是指算法实现过程所消耗的时间。假设每条语句执行一次所需要的时间为单位时间，那么一个算法的执行时间就和算法中需要执行语句的次数成正比，就是所有语句的执行次数之和，用O(m))表示。其中O表示代码执行时间随数据规模增长的变化趋势，也称渐进时间复杂度，简称时间复杂度。04算法的复杂性分析1.时间复杂性[例6.11]有如下C语言程序。其中，第3、4、5行各执行一次，第6、8行分别执行n次，第9、11行分别执行n2次，所以可以得出时间复杂度为0(2n2+2n+3)，当n的值非常大时，公式中的低阶常数和系数三部分并不左右增长趋势，因此可以忽略不计，上述算法的时间复杂度即O(n2)。04算法的复杂性分析2.空间复杂性在一般情况下，一个算法所占用的存储空间包括算法自身、算法的输入、算法的输出及实现算法的程序在运行时所占用空间的总和。由于算法的输入和输出所占用的空间基本上是一个确定的值，它们不会随着算法的不同而不同，而算法自身所占用的空间与实现算法的语言和使用的语句密切相关，因此一个算法的空间复杂性(空间复杂度)的度量主要考虑的是算法在运行过程中所需要的存储空间的大小。实际上，时间、空间是一对矛盾体，有的时候不得不为了节省时间而消耗空间，有的时候又不得不为了节省空间而消耗时间。04算法的复杂性分析2.空间复杂性[例6.12]交换两个整数，可以有如下两种算法。其中算法1比算法2的空间复杂度大，但是算法1的通用性强，适合于各种类型的数据交换，而算法2只适合于整型数据。04算法的复杂性分析3.设计算法时应考虑的原则正确性算法的正确性是指算法至少应该能正确反映问题的需求，能够得到问的正确答案。01可读性设计算法的目的，一方面是让计算机执行，另一方面是便于自己和他人阅读，让人理解和交流。可读性是评判算法好坏很重要的标志。0204算法的复杂性分析3.设计算法时应考虑的原则健壮性当输入的数据非法时，算法应当能恰当地做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且算法处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。03高效率与低存储量算法的效率指的是算法的执行时间，算法的存储量指的是算法执行过程中所需的最大存储空间。在算法正确、易读、健壮的情况下，还需要利用数学工具，讨论其时间复杂度和空间复杂度，探讨具体算法对问题的适应性。04算法中的数据结构02算法中的数据结构著名的计算机科学家NiklausWirth曾提出:

程序=算法+数据结构这个公式说明，程序是由算法和数据结构两大要素构成的。其中，数据结构是指欲处理的数据类型和数据的组织形式。例如，学号、姓名、出生日期等数据都具有相应的数据类型，大量数据在计算机中存储时采用何种组织形式可以带来更高的运行效率或存储效率，是数据结构研究的内容。算法中的数据结构数据结构为算法服务算法要作用在特定的数据结构之上。例如，常用的二分法查找需要用数组这种线性存储结构来存储数据，而链表这种链式存储结构是无法使用二分法查找的；在大量的有序数据中插入一个新数据后，若欲使数据依然保持有序状态，那么采用数组这种线性存储结构就需要涉及数据的后移，之后才能插入新数据，而采用链表这种链式存储结构则无须移动数据，直接插入即可。程序设计步骤0301程序/02程序设计01程序人们事先编制的一组指令的有序集合。计算机系统能完成各种工作的核心就是程序。02程序设计程序设计是指从人们分析实际问题开始到计算机给出正确结果的完整过程。03程序设计方法程序设计方法在很大程度上会影响程序设计的成败及程序的质量。目前，常用的是结构化程序设计和面向对象程序设计。无论哪种程序设计方法，程序的可靠性、易读性、高效性、可维护性等都是衡量程序质量的重要标准。03程序设计方法1.结构化程序设计结构化程序设计(StructuredProgramming，SP)思想最早由荷兰科学家EWDijikstra在1965年提出，是计算机软件发展的一个重要里程碑。自顶向下、逐步求精在进行程序设计时，先考虑整体，后考虑细节;先考虑全局目标，后考虑局部目标:先从最上层总目标开始设计，逐步使问题具体化，逐步细化。01模块化把要解决的总目标分解为若干个子目标，进一步分解为具体的小目标,把每一个小目标称为一个模块(函数):各个模块都基于顺序、选择、循环3种基本控制结构，且具有单入口和单出口;限制使用goto语句在程序中任意跳转。0203程序设计方法1.结构化程序设计结构化程序的结构简单清晰，可读性好，模块化强，程序执行效率高。但存在如下一些问题。程序的重用性差重用性是指同一事物不经修改或稍加修改就可多次重复使用的性质。01程序难以适应大型软件的设计在结构化程序设计中，算法是一个独立的整体，数据结构也是一个独立的整体，二者分开设计，以算法为主，即数据和处理数据分离。因此在大型软件系统开发中，程序容易出错，难以维护。0203程序设计方法2.面向对象程序设计面向对象程序设计(ObjectOrientedProgramming，00P)是20世纪80年代初提出的一种计算机编程架构，它汲取了结构化程序设计中好的思想，并引入了新的概念，尽可能模拟人类的思维方式，采用对象、类、方法、实例等相关概念进行程序设计。面向对象程序设计认为现实世界是由一个个对象组成的，构成客观事物的基本单元是对象。当解决某个问题时，先要确定这个问题由哪些对象组成。例如，一个学校是一个对象，一个班级是一个对象，一个学生是一个对象，而一个班级又是由若干个学生对象组成的，一个学校又是由若干个班级对象和若干个其他对象组成的。作为对象，一般应具备两个因素:一个是从事活动的主体，如班级中的若干个学生;另一个是活动的内容，如上课、开会等。从计算机的角度看，一个对象一般包括两个因素:一个是数据，相当于班级中的学生属性;另一个是需要进行的操作(函数)，相当于班级中学生进行的各种活动。对象就是一个包含数据及与这些数据有关的操作集合。03程序设计方法2.面向对象程序设计抽象抽象是指对具体问题进行概括，提取出一类对象的公共性质并加以描述的过程。抽象的过程是对问题进行分析和认知的过程，这是人类认识世界的基本手段之-抽象的作用是表示同一类事物的本质，如不同品牌的电视、不同形状的桌子等，它们分别属于同一类事物，所以可以对它们进行归纳，找出共同的属性和行为。01例如，对人类进行抽象。通过对人类进行归纳、抽象，抽取其中的共性，可得如下结论。人类的共同属性:姓名、性别、年龄、身高、体重等。人类的共同行为:吃饭、走路、睡觉等生物性行为:工作、学习等社会性行为。属性可用变量来表达。行为可用函数来表达。03程序设计方法2.面向对象程序设计封装将抽象得到的数据和行为相结合，形成一个有机的整体，即将数据和操作数据的函数进行有机的结合，形成“类”。封装是面向对象程序设计的一个重要特点。封装包含两个含义:一是将有关的数据和函数封装在一个对象中，形成一个基本单位，各个对象之间相互独立，互不干扰:二是将对象中某些部分对外隐蔽，即隐蔽其内部细节，只留下少量接口，以便与外界联系，接收外界的消息。这种对外界隐蔽的做法称为信息隐蔽。信息隐蔽有利于数据安全，防止无关的人了解和修改数据。02封装改变了传统方法中数据和处理数据分离的缺陷。03程序设计方法2.面向对象程序设计继承继承是面向对象程序设计的又一个重要特点。只有继承，才可以在别人认识的基础之上有所发现，有所突破，摆脱重复分析、重复开发的困境。例如，如果某汽车制造厂想生产一款新型汽车，一般不会全部从头开始设计，而是选择已有的某一型号汽车为基础，增加新的功能后形成一款新的汽车，从而提高生产效率，降低成本。这种新产品的研制方式称为继承。0303程序设计方法2.面向对象程序设计多态广义地说，多态是指一种行为表现出了多种形态。例如，你“吃饭”，我也“吃饭”，但吃的东西不一样，所以吃饭的动作不同。所谓多态性，是指由继承而产生的不同的派生类，其对象对同一消息会做出不同的响应。多态性也是面向对象程序设计的一个重要特点，能增加程序的灵活性。04①整个软件由各种各样的对象构成。③根据对象的属性和运动规律的相似性可以将对象分类。②每个对象都有各自的内部状态和运动规律。④复杂对象由相对简单的对象构成。03程序设计方法2.面向对象程序设计多态04⑤不同对象的组合及其间的相瓦作用和联系构成系统。⑥对象间的相互作用通过消息传递，对象根据所接收到的消息做出自身的响应。由此可以看出，面向对象程序设计将问题抽象成许多类，将数据与对数据的操作封装在一起，各个类之间可能存在着继承关系，对象是类的实例，程序由对象组成，程序可以被描述为:程序=对象+对象+···+对象，对象=数据结构+算法。面向对象程序设计可以较好地克服面向过程程序设计存在的问题，使用得好，可以开发出健壮的、易于扩展和维护的应用程序。基于计算机的问题求解0401基于计算机软件的问题求解方法在实际工作中，当我们遇到问题时，首先会怎么做呢?大多数人的做法一般都是有意或无意地寻找一些现成的工具。一些计算机的通用软件就是我们的工具。例如，当我们需要利用计算机处理图像时，可以使用图像处理软件Photoshop;当我们需要处理文档时，可以使用字处理软件Word;当我们需要求解拟合问题、等高线、权限等诸多数学问题时，可以使用商业数学软件MATLAB:当我们发现计算机可能感染病毒时，可以使用对应的杀毒软件，等等。通用问题与求解问题的相应软件如表6-1所示。02基于计算机程序的问题求解方法软件这么强大，那么所有计算机可解的问题都有可用的软件吗?显然不是。无论计算机软件多么