《第05章-算法》由会员分享，可在线阅读，更多相关《第05章-算法（43页珍藏版）》请在金锄头文库上搜索。
1、第五章 算法,5.1 算法的概念 5.2 算法的表示 5.3 算法的发现 5.4 迭代结构 5.5 递归结构 5.6 有效性和正确性,5.1 算法的概念,5.1.1 概览,算法（非正式定义）：描述如何完成任务的步骤集,举例：剥豌豆的算法,剥豌豆的步骤： 从篮子里拿出一个豌豆。 剥开豌豆的豆荚 把剥落的豆放在碗里面。 扔掉空豆荚。,5.1.2 算法的正式定义,算法是定义一个可终止过程的一组有序的、无歧义的、可执行的步骤的集合,有序：算法的各个步骤必须有一个非常明确的、顺序执行的结构 无歧义：执行过程中被处理的信息必须足以唯一地、完整地确定每一步所需要的动作。 可执行：一个算法的执行必须能够最终结
2、束。,算法是抽象的。,5.1.3 算法的抽象本质,程序和进程：程序是一个算法的表示，而进程是执行程序的活动,课堂练习,简述进程、算法和程序进程之间的关系。,答：进程是执行算法的活动。程序是算法的表示。,5.2 算法的表示,5.2.1 原语,由一张正方形的纸折叠成一只鸟,折纸术的原语,原语：计算机科学解决问题的途径是建立一组严格定义的构件块，利用他们来构建算法的表示，这种构件块称为原语。 原语组成：语法和语义 程序设计语言：原语的集合以及说明如何组合这些原语来表示比较复杂的算法的规则集合就构成了程序设计语言。,(1) 用自然语言描述算法 (2) 用流程图描述算法 (3) 使用伪代码描述算法 (4
3、) 用程序设计语言描述算法,算法的描述方法有以下四种：,(1) 用自然语言描述算法,举例：剥豌豆的算法,剥豌豆的步骤： 从篮子里拿出一个豌豆。 剥开豌豆的豆荚 把剥落的豆放在碗里面。 扔掉空豆荚。,流程图 flow chart：用图形符号表示算法操作。,(2) 用流程图描述算法,(3) 使用伪代码描述算法,5.2.2 伪代码,伪代码：一种在算法开发过程中非正式地表达思想的符号系统。,常用的伪代码的结构： 赋值语句 name expression 选择语句 if condition then action 循环控制 while condition do activity 过程 procedure
4、 name (generic names),(4) 用程序设计语言描述算法,main() int num,total;num=10;total=num*30;printf(“Total=%d”,total); ,程序开发：算法+程序,5.3 算法的发现,5.3.1 求解算法的艺术,程序开发的阶段： 第1阶段 理解问题 第2阶段 寻找一个可能解决问题的算法过程的思路 第3阶段 阐明算法并且用程序将其表达出来 第4阶段 从准确度及其是否有潜力作为一个工具解决其他问题这两方面评估这个程序,例：求解确认3个孩子年龄的计算过程,甲承担确认乙的三个孩子的年龄的任务。乙告诉甲三个线索： 三个孩子的年龄乘积是
5、36； 三个孩子的年龄之和（注意没确切说是多少）； 最大的一个孩子弹钢琴。,例：在甲、乙、丙和丁进行赛跑之前，分别对结果进行预测: 甲预测乙将会获胜 乙预测丁将是最后一名 丙预测甲是第三名 丁预测甲的预测将是正确的 这几个预测中只有一个是正确的，并且是最后的获胜者作出的预测，给出最后的名次排序。,5.3.2 入门,入门的方法： 反方向解决问题 用相关解决方法 逐步求精：自顶向下,把折纸过程反方向化,反方向解决问题,用相关解决方法,例如排序算法。 可以对很多排序问题用同一排序算法解决。,逐步求精,自顶向下：从一般发展到特殊 逐步求精：逐层分解复杂任务，把任务细节推延到下层模块中实现。 自底向上：
6、从特殊发展到一般,成绩管理程序,5.4 迭代结构,重复结构： N1； While (NTestEntry 并且还有表项没有检查)do（选择下一表项作为TestEntry ）if（TargetValue=TestEntry ）then(宣告查找成功)else (宣告查找失败)）end if,5.4.1 顺序搜索法,While循环结构： While(条件) do（活动）Repeat循环结构： Repeat(活动)until(条件),5.4.2 循环控制,While循环结构,While 循环的终止条件,While (PH值大于4) do（加一点硫酸） 终止条件：PH值不大于4,观察下列循环的终止,n
7、umber 1;While(number6) do(number number+2) 终止条件：number=6,Repeat循环结构,后测试循环 Repeat（从你口袋里面取出一个硬币） Until（你口袋里没有硬币）前测试循环 While(你口袋里有硬币) do(从你口袋里面取出一个硬币),Procedure sort(List) N 2; While(N的值不超过列表的长度) do（把列表的第N项作为主元项；把主元项移动一个临时位置使该列表留出一个空位置；while（如果这个空位置上面存在一个名字并且那个名字比 主元大）do （把这个名字向下移到空位置上使该名字上面留出一个空位置）把主元
8、项插到这个列表的空位置上； N N+1 ）,5.4.3 插入排序算法,例：49 38 65 97 76 13 27,49 38 65 97 76 13 27,(38 49) 65 97 76 13 27,(38 49 65) 97 76 13 27,(38 49 65 97) 76 13 27,(38 49 65 76 97) 13 27,(13 38 49 65 76 97) 27,( ),(13 38 49 65 76 97) 27,97,76,65,49,38,27,递归：通过指令集作为自身的一个子任务重复调用来运行。,5.5 递归结构,基本思想： 在已经排好序的表中先取中间位置与所搜索
9、的项进行比较，如果相等，则查找成功。如果给定值比该项大，则查找表的后半部分；否则查找结点在表的前半部分，然后再把选定的部分表的中间的项与给定项进行比较。如此反复进行，直到查找成功或者查找失败为止。,5.5.1 二分搜索算法,在表中查找John,二分搜索算法的伪代码,例：用二分法查找21 5 13 19 21 37 56 64 75 80 88 92,5.6 有效性和正确性,5.6.1 算法的有效性 有效性是算法设计中所关注的一个重要问题。 算法分析：算法所消耗的时间或者空间资源。 最优情况分析 最差情况分析 平均情况分析,插入排序算法的最差情况分析图,执行算法所需要的时间,增加列表长度时时间的
10、增长,长度均匀增长,列表的长度,二分搜索算法的最差情况分析图,执行算法所需要的时间,增加列表长度时时间的增长,长度均匀增长,列表的长度,5.6.2 软件验证,算法正确性 一个被认为正确的程序和一个正确的程序之间是有区别的。 软件验证是一种重要承诺，发现有效的验证技术是计算机科学中一个活跃的研究领域。 例：一个拿着由7个金环组成的链子的旅行者必须在一个饭店里住7夜。每一夜的租金是金链中的一环。应该怎样对链子进行最少次数的切割，旅行者才能每天早上支付旅店一环而不用提前支付住宿费？,用3次切割将链子分开,只用1次切割将链子分开,Why?,第一天早上：给饭店一个环； 第二天早上：给饭店一个两个环的金链，同时找回一个环； 第三天早上：给饭店一个环； 第四天早上：给饭店一个四个环的金链，同时找回先前给的三个环； 第五天早上：给饭店一个环； 第六天早上：给饭店一个两个环的金链，同时找回一个环； 第七天早上：给饭店一个环。,
