[理学]第2章 算法---程序的灵魂 谭浩强版.ppt

数据结构与算法 算法 2.2 简单算法举例 步骤1： 先求1×2，得到结果2。 步骤2： 将步骤1得到的乘积2再乘以3，得到结果6。 步骤3： 将6再乘以4，得24。 步骤4： 将24再乘以5，得120。 2.2 简单算法举例 S1: 使t=1 S2: 使i=2 S3: 使t×i, 乘积仍然放在在变量t中，可表示为t×i→t S4: 使i的值+1，即i+1→i S5: 如果i≤5, 返回重新执行步骤S3以及其后的S4和S5；否则，算法结束。 常用算法 算法的设计目标 算法的设计目标 ●健状性：当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。 ●效率与低存储量的需求：主要指算法执行时的最长时间与所需的最大存储空间。 补充内容：算法的评价 1.时间复杂度 2.4.1 用自然语言表示算法 (3) 循环结构： 图2.20 没有通路 结构化程序设计 自顶向下（将一个任务分为若干层次） 逐步细化（对各层逐步补充、完善） 模块化设计 将一个任务分为若干个相对独立、功能单一的小模块，而每个模块与外部联系只有单一的入口和出口。 结构化编码（选用结构化的语言） 图2.21 死循环 由三种基本结构派生出来的结构： A N p2 Y B 根据表达式p 的值进行选择 A B p=p1 p=p2 … M N p=pm p=pn 2.4.4 用N-S流程图表示算法 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?t 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用伪代码表示算法 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法 用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用 例2.16 求5!。 begin (算法开始) 1 ? t 2 ? i while i≤5 { t*i ? t i+1 ? i } print t end (算法结束) 例2.17 求 begin 1 ? sum 2 ? deno 1 ? sign while deno ≤ 100 { (-1)*sign ? sign sign*1/deno ? term sum+term ? sum deno+1 ? deno } print sum end 2.4.6用计算机语言表示算法 要完成一项工作，包括设计算法和实现算法两个部分。 设计算法的目的是为了实现算法。 不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。