第05章-算法.pptVIP

第五章 算法 5.1 算法的概念 5.1.2 算法的正式定义 算法是抽象的。 课堂练习 简述进程、算法和程序进程之间的关系。 5.2 算法的表示 折纸术的原语 原语：计算机科学解决问题的途径是建立一组严格定义的构件块，利用他们来构建算法的表示，这种构件块称为原语。 原语组成：语法和语义 程序设计语言：原语的集合以及说明如何组合这些原语来表示比较复杂的算法的规则集合就构成了程序设计语言。 (1) 用自然语言描述算法 (2) 用流程图描述算法 (3) 使用伪代码描述算法 (4) 用程序设计语言描述算法 main() { int num,total; num=10; total=num*30; printf(“Total=%d”,total); } 5.3 算法的发现 程序开发：算法+程序 例：求解确认3个孩子年龄的计算过程 例：在甲、乙、丙和丁进行赛跑之前，分别对结果进行预测: 甲预测乙将会获胜 乙预测丁将是最后一名 丙预测甲是第三名 丁预测甲的预测将是正确的 这几个预测中只有一个是正确的，并且是最后的获胜者作出的预测，给出最后的名次排序。 入门的方法： 反方向解决问题 用相关解决方法 逐步求精：自顶向下 反方向解决问题 用相关解决方法 例如排序算法。 可以对很多排序问题用同一排序算法解决。 5.4 迭代结构 重复结构： N←1； While (N3) do (演奏该曲乐段； 演奏第N段尾曲； N=N+1；） While循环结构： While(条件) do（活动） Repeat循环结构： Repeat(活动)until(条件) While循环结构 While 循环的终止条件 While (PH值大于4) do （加一点硫酸） 终止条件：PH值不大于4 观察下列循环的终止 number ←1; While(number≠6) do (number ←number+2) 终止条件：number=6 Repeat循环结构 后测试循环 Repeat（从你口袋里面取出一个硬币） Until（你口袋里没有硬币） 前测试循环 While(你口袋里有硬币) do (从你口袋里面取出一个硬币) 5.4.3 插入排序算法 Procedure sort(List) N ←2; While(N的值不超过列表的长度) do （把列表的第N项作为主元项； 把主元项移动一个临时位置使该列表留出一个空位置； while（如果这个空位置上面存在一个名字并且那个名字比 主元大）do （把这个名字向下移到空位置上使该名字上面留出一个空位置） 把主元项插到这个列表的空位置上； N ←N+1 ） 例：49 38 65 97 76 13 27 5.5 递归结构 递归：通过指令集作为自身的一个子任务 重复调用来运行。 在表中查找John 二分有哪些信誉好的足球投注网站算法的伪代码 例：用二分法查找21 5 13 19 21 37 56 64 75 80 88 92 5.6 有效性和正确性 5.6.1 算法的有效性 有效性是算法设计中所关注的一个重要问题。 算法分析：算法所消耗的时间或者空间资源。 最优情况分析 最差情况分析 平均情况分析 算法正确性 一个被认为正确的程序和一个正确的程序之间是有区别的。 软件验证是一种重要承诺，发现有效的验证技术是计算机科学中一个活跃的研究领域。 例：一个拿着由7个金环组成的链子的旅行者必须在一个饭店里住7夜。每一夜的租金是金链中的一环。应该怎样对链子进行最少次数的切割，旅行者才能每天早上支付旅店一环而不用提前支付住宿费？ 用3次切割将链子分开 只用1次切割将链子分开 Why? 第一天早上：给饭店一个环； 第二天早上：给饭店一个两个环的金链，同时找回一个环； 第三天早上：给饭店一个环； 第四天早上：给饭店一个四个环的金链，同时找回先前给的三个环； 第五天早上：给饭店一个环； 第六天早上：给饭店一个两个环的金链，同时找回一个环； 第七天早上：给饭店一个环。 例： 阶乘函数 n! 1 n=0 n*F(n-1) n0 F(n)= 基本思想： 在已经排好序的表中先取中间位置与所有哪些信誉好的足球投注网站的项进行比较，如果相等，则查找成功。如果给定值比该项大，