第2章_算法--程序的灵魂精要.ppt

第二章 主要内容 2.1 什么是算法 2.2 简单的算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法 2.1 什么是算法 2.1 什么是算法 2.2 简单的算法举例 2.2 简单的算法举例 2.2 简单的算法举例 2.2 简单的算法举例 2.2 简单的算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.4 怎样表示一个算法 由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由三种基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。 扩展： 只要具有上述四个特点的都可以作为基本结构。可以自己定义基本结构，并由这些基本结构组成结构化程序。 N-S图表示算法的优点: 比文字描述直观、形象、易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N--S流程图中的上下顺序就是执行时的顺序。用N--S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转,而只能自上而下地顺序执行. 2.5 结构化程序设计方法 2.4.3 三种基本结构和改进的流程图 (3)循环结构 ①当型循环结构 A Y p1 N Y x5 N 0?x 输出x的值 x+1?x 输出1,2,3,4,5 2.4.3 三种基本结构和改进的流程图 (3)循环结构 ②直到型循环结构 输出1,2,3,4,5 A Y p2 N Y x≧5 N 0?x 输出x的值 x+1?x 三种基本结构的共同特点： 只有一个入口； 只有一个出口； 一个判断框有两个出口 一个选择结构只有一个出口 结构内的每一部分都有机会被执行到； 也就是说，对每一个框来说，都应当有一条从入口到出口的路径通过它 结构内不存在“死循环”。 2.4.3 三种基本结构和改进的流程图 此图符合基本结构的特点 由三种基本结构派生出来的结构： 根据表达式p 的值进行选择 A B p=p1 p=p2 … M N p=pm p=pn 2.4.4 用N-S流程图表示算法 I.NassiB.Shneiderman(1973,USA) N-S流程图用以下的流程图符号： A B A B Y N p A 当p1成立 A 直到p2成立 顺序结构 选择结构 循环结构 （当型） 循环结构（直到型） 例2.11 将例2.1的求5!算法用N-S图表示。 直到i5 1?t 输出t 2?i t*i?t i+1?i 例2.12 将例2.2的算法用N-S图表示.将50名学生中成绩高于80分者的学号和成绩输出。 直到i50 1?i 1?i i+1?i 输入ni、gi i+1?i 直到i50 gi≧80 否 是 输出ni,gi 例2.13 将例2.3判定闰年的算法用N-S图表示 直到year2500 2000?year year+1?year 否 是 year%4为0 否 是 输出 year 非闰年 year%100不为0 year%400为0 是 否 输出year 非闰年 输出year 闰年 输出 year 闰年 例2.14 将例2.4的算法用N-S图表示。 直到deno100 deno+1?deno 输出sum 1?sum 1?sign 2?deno (-1)*sign?sign sign*(1/deno)?term sum+term?sum 例2.15 将例2.5判别素数的算法用N-S流程图表示 例2.10的流程图不是由三种基本结构组成的 循环有两个出口，不符合基本结构的特点 无法直接用N-S流程图的三种基本结构的来表示 先作必要的变换:引入控制变量 N Y 开始 输入n 0?w 2?i n%i?r r=0 i+1?i i≦ 和w=0 Y N 1?w ① 输出n 是素数 结束 w=0 ① 输出n 不是素数 输入n r=0 是 否 0?w 2?i n%i?r 1?w i+1?i 直到i 或w ≠0 w=0 是 否 输出n是素数 输出n不是素数 一个结构化的算法是由一些基本结构顺序组成的 在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内 一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变 如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法 2.4.5 用伪代码表示算法 伪代码(pseudo code)是用介于自然语言和计算机语言之间的文字和符号来描述算法 用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用 例2.16 求5!。 begin (算法开始) 1 ? t 2 ? i while i≤5 { t*i ? t