计算思维导论课件 第3章资料.ppt

第三章 算法基础,3-2/60,1974年图灵奖获得者Donald Ervin Knuth: 计算机科学就是算法的研究 The Art of Computer Programming,3.1 算法的概念,3-3/60,一、算法的起源,3.1 算法的概念,公元前300年：古希腊著名数学家欧几里得提出求最大公约数的一种算法,即辗转相除法又称欧几里得算法公元263年：三国魏人刘徽注释《九章算术》中不仅对原书的方法、公式和定理进行一般的解释和推导，而且在其论述中多有创造如他运用割圆术得出圆周率的近似值3927/1250＝3.1416公元825年：波斯数学家al-Khwarizmi撰写了著名的Persian Textbook中概括了进行四则算术运算的法则Algorithm(算法)一词就来源于这位数学家的名字3-4/60,二、算法的定义,[算法3.1]欧几里得算法 输入：正整数m、n 输出：m、n的最大公约数 ① r＝m mod n ② 若r＝0，输出最大公约数n ③ 若r≠0，令m＝n，n＝r，转①继续,3.1 算法的概念,算法：是解决某一特定问题的一组有穷规则的集合 算法：对特定问题求解步骤的一种描述，是由若干条指令组成的有穷集合。

3-5/60,三、算法的特征,确定性：算法中每一个步骤都是清晰的、无歧义 有穷性：算法必须在有限步内终止 输 入：有零个或多个输入，作为初始状态 输 出：有一个或多个输出，作为计算结果 可行性：算法中的操作可通过有限次基本运算来实现,3.1 算法的概念,判断一个算法的好坏主要依据如下标准： 正确性：在合理输入下能在有限时间内得出正确结果 可读性：算法主要是为了人的阅读与交流，其次执行 健壮性：算法应具备检查错误和对错误进行处理能力 效 率：算法执行时所需计算机资源的多少,3-6/60,算法的描述目的 记录算法思想 方便他人理解算法,3.2 算法的描述,算法的描述方法 自然语言 流程图 伪代码 程序设计语言,3-7/60,一、自然语言,3.2 算法的描述,自然语言是人们日常进行交流的语言，如汉语、英语等 优点：通俗易懂，即使没有学过算法也能看懂算法执行 缺点：不够严谨，容易出现歧义和错误,[例题]利用自然语言描述欧几里得算法 ① 输入m、n ② 判断n是否为0，如果不为0，转步骤③，否则转④ ③ m对n取余，其结果赋值给r，n赋给m，r赋给n，转② ④ 输出m，算法结束,3-8/60,二、流程图,常用来描述算法的图形工具有：流程图或程序框图、N-S图和PAD图。

优点：直观形象，简洁明了 缺点：画起来费事，不易修改3.2 算法的描述,常用的流程图符号：,3-9/60,,[例题]利用流程图描述欧几里得算法3.2 算法的描述,3-10/60,三、伪代码,3.2 算法的描述,伪代码是由带标号的指令构成，但是它不是C、C++、Java等通常使用的程序设计语言，而是算法步骤的描述 伪代码介于自然语言和程序设计语言之间伪代码的具体表示： 赋值语言：← 分支语句：if…then…[else] 循环语句：while, for, repeat until 转向语句：goto 输出语句：return 调用： 注释：//…,3-11/60,[例题]利用伪代码描述欧几里得算法3.2 算法的描述,输入：正整数m、n 输出：m、n的最大公约数 1 repeat 2 r ← m mod n 3 m ← n 4 n ← r 5 until r=0 6 return m,3-12/60,四、程序设计语言,程序设计语言是一个能完整、准确和规则地表达人们的意图，并用以指挥或控制计算机工作的符号系统，如C、C++、Java等程序设计语言可以描述算法3.2 算法的描述,优点：描述的算法能在计算机上直接执行 缺点：抽象性差、不易理解且有严格的语法限制等。

3-13/60,输入：正整数m、n 输出：m、n的最大公约数 int gcd(int m, int n) { int r; do { r = m % n; m = n; n = r; } while(r); return m; },3.2 算法的描述,[例题]利用C语言描述欧几里得算法3-14/60,算法是解决问题的方案，由于实际问题千奇百怪，因而制定出的解决方案也将千差万别3.3 算法的设计,算法设计的一般步骤： ①理解待求解问题 解决问题是设计算法的最终目标除了需要分析问题的求解目标、输入数据和限制条件外，还要判断清楚待求解问题的种类，是否有现成的算法可以直接应用 ②确定算法运行的环境 了解算法的运行环境，才能设计出可行且高效的算法比如在小型的嵌入式环境中只能运行需要较小内存的算法，而对于并行分布式的运行环境，则要设计高效的并行算法3-15/60,③设计算法 设计算法是将算法具体化，即设计出算法的详细规格说明也就是，首先确定算法所需要的数据结构，然后结合具体问题的特性来选择算法的设计策略，最后根据算法设计技术的原理描述算法的具体流程(流程图、伪代码和程序设计语言等) ④分析算法 对所设计出的算法进行复杂性分析，考察其在时间和空间方面的计算开销。

若算法在某些环节的计算开销较大，可有针对性地改进该环节，若整个算法的计算开销太大，则需要返回第③步重新考虑采用新的算法设计技术来求解该问题 ⑤编程实现 采用某种程序设计语言将设计好的算法实现出来3.3 算法的设计,3-16/60,算法分类：,①数值算法 求解线性方程组、数值积分等，有特定的计算步骤 数值计算方法课程 ②非数值算法 求解判定问题、最优化问题等，需要掌握算法设计技术 算法设计与分析课程 ③软计算方法 遗传算法、粒子群算法、蚁群算法、人工神经网络等 计算智能课程,3.3 算法的设计,3-17/60,一、穷举法(又称蛮力算法) 穷举法指在问题的解空间范围内逐一测试，找出问题的解它是一种简单而有效的算法设计策略同时也是一种很容易应用的方法3.3 算法的设计,穷举法的应用 国王的婚姻中国王使用的算法 旅行商问题中逐条路线计算 密码学中的暴力破解法 图论中四色定理的证明 百钱买百鸡问题,3-18/60,[案例一]暴力破解法是一种用穷举法实现的密码破译方法3.3 算法的设计,,,最原始、最基本的攻击方式，对密码进行逐一测试直到找到真正的密码 原则上可以破译所有密码，但费时费力。

密码暴力破解软件：89Winrar 密码暴力破解软件,3-19/60,[案例二]四色定理(又称四色问题或四色猜想)3.3 算法的设计,四色问题描述：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色 数学语言表示：将平面任意地细分为不相重叠的区域，每一个区域总可以用1、2、3、4这四个数字之一来标记，而不会使相邻的有公共边界的两个区域得到相同的数字证明四色定理(穷举法)： ①利用数学理论推出证明所有例子可以归约到证明有限个特例上； ②利用计算机程序产生了所有特例(大约1700个例子)，通过穷举发现所有特例都是四着色的3-20/60,[案例三]百钱买百鸡问题,百钱买百鸡：鸡翁一，值钱五 鸡母一，值钱三 鸡雏三，值钱一 问翁、母、雏各几何？,3.3 算法的设计,意思是：公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数3-21/60,设鸡翁、鸡母、鸡雏的个数分别为x、y、z，根据题意可得如下方程组： 5x＋3y＋z/3＝100 x＋y＋z＝100 1≤x＜20, 1≤y＜33, 3≤z＜100, z mod 3＝0,测试集合：1≤x＜20, 1≤y＜33，z=3,6,9,.,99 测试条件：5x＋3y＋z/3＝100 x＋y＋z＝100,3.3 算法的设计,,3-22/60,巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是一种重要的算法设计策略： ①穷举法几乎可以通用于任何领域的问题求解，可能是唯一一种解决所有问题的一般性方法； ②即使效率低下，仍可用穷举法求解一些小规模的问题实例； ③如果解决的问题实例不多，而穷举法可用一种可接受的速度对问题求解，那么花时间去设计一个更高效地算法是得不偿失的。

3.3 算法的设计,[思考题]举例说明生活中的穷举法应用3-23/60,二、回溯法 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标在搜索过程中，能进则进，不能进则退回来，换一条路再试，通过此种方式提高搜索效率，减少不必要的测试3.3 算法的设计,回溯法的应用 迷宫问题 搜索引擎中的网络爬虫 八皇后问题,3-24/60,[案例一]老鼠走迷宫,3.3 算法的设计,老鼠从迷宫入口出发，任选一条路线向前走，在到达一个岔路口时，任选一个路线走下去…，如此继续，直到前面没有路可走时，老鼠退回到上一个岔路口，重新在没有走过的路线中任选一条路线往前走按这种方式走下去，直到走出迷宫3-25/60,[案例二]搜索引擎中的网络爬虫3.3 算法的设计,搜索引擎是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统百度和谷歌等是搜索引擎的代表 搜索引擎的组成：下载、索引和查询3-26/60,网络爬虫：自动下载互联网所有网页 网络爬虫原理：图的遍历，从图中某一顶点出发访遍图中所有顶点，且使每个顶点仅被访问一次 回溯算法：图的深度优先遍历（广度优先遍历）。

3.3 算法的设计,深度优先遍历顺序：V1,V2,V4,V8,V5,V3,V6,V7,3-27/60,[案例三]八皇后问题在8×8格国际象棋的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上问有多少种摆法？,3.3 算法的设计,3-28/60,回溯法解八皇后问题思路：逐行摆放皇后初始第1行皇后放第1列；摆放第i行皇后时，从第1列开始，逐列判定是否与前i-1行皇后攻击，直到找到一个不攻击的位置，继续第i+1行的摆放；若第i行无摆放位置，则拿掉该行皇后，回溯至第i-1行，第i-1行皇后从当前位置的下一列开始判定，继续搜索当第1行皇后的摆放位置超出棋盘时，全部求解过程结束92种),3.3 算法的设计,,,,,,,,,,,,,,,,,,,,,,,,,,,,,3-29/60,回溯法有通用解法之称，当一个问题没有显而易见的解法时，可尝试使用回溯法求解，这实际是与穷举法一致的，因其本质仍是穷举需要注意，回溯和穷举虽然能解很多问题，但其算法效率可能很低3.3 算法的设计,回溯法的基本思想是能进则进，不能进则退为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或确定该问题无解。

回溯法是求解实际问题的一个重要算法，很多无法使用贪心算法和动态规划算法进行求解的问题，都可以使用回溯算法进行求解，并且可以保证得到问题的最优解3-30/60,三、递归算法 递归：直接或间接地调用自身的算法 递归思想就是用与自身问题相似但规模较小的问题来描述自己3.3 算法的设计,递归算法的应用 盗梦空间(美国影片) 欧几里得算法 德罗斯特效应(Droste Effect) 斐波纳契数列(Fibonacci数列),3-31/60,[案例一]德罗斯特效应递归的一种视觉形式，它指一张图片的某个部分与整张图片相同，如此产生无限循环3.3 算法的设计,3-32/60,[案例二]1202年，意大利数学家斐波纳契出版了他的算盘全书他在书中提出了一个关于兔子繁殖问题：如果一对兔子每月能生一对小兔(一雄一雌)，而每对小兔在它们出生后的第三个月里，又能开始生一对小兔，假定在不发生死亡的情况下，由一对出生的小兔开始，50月后会有多少对兔子？,分析：第一个月只有一对兔子，第二个月仍只有一对兔子，。