大学计算机基础教程（徐昆良第3版）高教 课件 第9章 算法与程序设计基础.pptx

第9章 算法与程序设计基础;学习目标：;9.1 算 法;一个算法的例子，欧几里得算法即辗转相除法来求解两个正整数的最大公约数。具体算法如下： 输入：正整数a、b 输出：最大公约数 第1步：a除以b，余数记为r； 第2步：若r=0，输出最大公约数b，算法结束； 第3步：若r≠0，令a=b，b=r，重复第1步继续。 按照以上算法，重复第1-3步，使a，b的值不断缩小，最终一定能使r=0，算法终止，得到最大公约数。;9.1.2 算法的特性 有穷性。一个算法应包含有限的操作步骤，而不能是无限的。例9-1算法中对于任意的正整数a、b，第3步，令a=b，b=r，使a，b的值不断缩小，最终一定能使r=0，算法终止。 确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。例9-1算法中要求输入的是正整数，这就保证了运算的每一步都是清晰、无歧义的。 输入。有零个或多个输入、所谓输入是指在执行算法是需要从外界取得必要的信息。例9-1算法中输入是正整数a、b。 输出。有一个或多个输出。算法的目的是为了求解，没有输出的算法是没有意义的。例9-1算法中输出是最大公约数。 有效性。算法中所描述的运算和操作必须是可以通过有限次基本运算来实现的。例9-1算法中每一步都是基本运算，任何人都可以用纸笔在有限时间内完成。 ;9.1.3 算法的表示 常用的算法描述方法有自然语言、流程图、伪代码、程序语言、N-S图等。 1.自然语言 自然语言，就是用人们日常生活中所熟悉的语言，辅助操作操作序号描述算法的一种方法，例9-1是用自然语言描述的算法。 这种描述方法通俗易懂，但自然语言的模糊性与二义性会导致程序员在理解上出现偏差。因此，在计算机领域需要寻找更精确地算法描述手段，最常见的是流程图和伪代码。 2.流程图 流程图是最常见的用图形表示算法的工具，具有直观、简单、便宜阅读等特点，一直以来被广泛应用。 流程图使用框图表示各种操作，使用流程线表示算法步骤在时间上的执行顺序。常见的流程图所用的符号如图所示。 ; ;3.伪代码 伪代码是一种人们交流算法过程中使用的非程序设计语言，但又与程序设计语言相似的表述方法。通常可??采用自然语言、数学公式和符号混用来描述算法步骤，同时采用计算机高级语言控制结构来描述算法的执行顺序。 ;4.程序语言 程序语言是指用计算机高级语言，如Python、C++、JAVA等描述算法，用程序语言描述的算法也称为程序，是可以在计算机上运行并获得结果的算法描述。本书之后所有例子算法表示均使用Python语言描述。 ;1.穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。穷举法是一种比较耗时的算法，但正是计算机的使用，使穷举法有了用武之地。 百钱百鸡问题是穷举法的一个典型案例。百鸡问题是一个数学问题，出自中国古代约5—6世纪成书的《张丘建算经》，题目：公鸡5文钱一只，母鸡3文钱一只，小鸡3只一文钱， 用100文钱买一百只鸡,其中公鸡，母鸡，小鸡都必须要有，问公鸡，母鸡，小鸡要买多少只刚好凑足100文钱？;2.递归 递归是一种简化复杂问题求解过程的手段。递归首先逐步化简问题为同性质的规模缩小了的子问题，然后对这个子问题用函数（或过程）来描述，再递归调用该函数（或过程）以获得问题的最终解。递归总是直接或间接地调用自身完成同样性质的子问题求解。 递归算法的典型案例是裴波那契（Fibonacci）数列。1202年，意大利著名数学家莱昂纳多·裴波那契提出了一个有趣的数学问题，一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？ ;3.迭代法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。迭代计算过程是一种不断用变量的旧值递推新值的过程。 欧几里得算法是经典的迭代算法;4.分治法 分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 分治法的典型案例是二分搜索。二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。;二分搜索算法用Python语言描述为： # 返回 x 在 arr 中的索引，如果不存在返回 -1 def BinySearc