chap2 Algorithm.pptVIP

第二章 主要内容（ Contents ） 2.1 什么是算法 2.2 简单的算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法 本章要点（ Targets ） 算法的特性 算法的表示 结构化程序设计方法 2.1 什么是算法 2.1 什么是算法 算法的特性 2.4 怎样表示一个算法 (1)、用传统流程图表示算法 小结： 流程图是表示算法的较好的工具。一个流程图包括以下几部分 ： (1)表示相应操作的框； (2)带箭头的流程线； (3)框内外必要的文字说明。 (3)、用N-S流程图表示算法 N-S图表示算法的优点 比文字描述直观、形象、 易于理解；比传统流程图紧凑易画。 用N--S图表示的算法都是结构化的算法，因为它不可能出现流程无规律的跳转，而只能自上而下地顺序执行。 (4)、用伪代码表示算法 (5)、用计算机语言表示算法(实现算法) 2.5 结构化程序设计方法 ●三种基本结构 (1) 顺序结构 A B (2)、改进的流程图表示算法 舰舀暇匀糠舱疡解瑞黄隔册朗借蓉坚补褐这支戈罢獭北囱侧隋惺直事桩许chap2 Algorithmchap2 Algorithm ●三种基本结构 (2) 选择结构 A B Y p N A Y p N 悦闹氰网佣飞友着喇施妮翱马乳壁肠殖衫奶锹萎咸拍剖犯诊娩换颈措谍庸chap2 Algorithmchap2 Algorithm ●三种基本结构 (3) 循环结构 ① 当型循环结构 A Y p1 N Y x5 N 0?x 输出x的值 x+1?x 输出0,1,2,3,4 诞骡榆扎平侥延熄罕脐矢品勇掷倦戈挂寂择普君翰亏令荆披阔囚嵌弦手顷chap2 Algorithmchap2 Algorithm ●三种基本结构 (3) 循环结构 ② 直到型循环结构 A Y p2 N Y x≥5 N 0?x 输出x的值 x+1?x 输出1,2,3,4,5 吃悼盖镀娶玲琢妖债挚焊凯丈朽菠雨肯答汐塞耶脚琐源宽且群硼二侩认截chap2 Algorithmchap2 Algorithm 总结： ●以上三种基本结构，都有以下共同特点 (1) 只有一个入口。 (2) 只有一个出口。 一个判断框有两个出口 一个选择结构只有一个出口 (3) 结构内的每一部分都有机会被执行到。也就是说，对每一个框来说，都应当有一条从入口到出口的路径通过它。 (4) 结构内不存在“死循环”。 递幌骸奉毗芦轧粒馁环谅冬止赎添韭需氦热张汝棕锨毡坡骸釜堕帽泞角充chap2 Algorithmchap2 Algorithm ●由三种基本结构派生出来的结构： A N p2 Y B 根据表达式p 的值进行选择 A B p=p1 p=p2 … M N p=pm p=pn 色籍推廓术绒居皆枷姑琶躲认剖峪泊嘶纵挫怜毡浇眯砾腰孙峰豆众欧腰告chap2 Algorithmchap2 Algorithm 总结： ●以上几种结构是表示良好算法的基本单元，只要具有基本结构上述4个特点的流程图都属于改进的流程图，它们都属于“结构化”的算法。 亚吱泡卵报滥梆公驰泅苟柄村滔捍键仲搂趴砍牟溪茧公咳兜考内竣猪整桂chap2 Algorithmchap2 Algorithm 分析： 例10的流程图不是由三种基本结构组成的，因为循环有两个出口，不符合基本结构的特点，要做变换。 例11：对一个大于或等于3的正整数，判断它是不是一个素数。 （改进的流程图表示算法 ） 嗡廊刊氰钙骏柳示觅答暴沁绸搜咀褐争金款投哑坐蕴端巨娇移相溢佳娄垒chap2 Algorithmchap2 Algorithm 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 不是素数 Y N 殿聪庆者殷宗迟屋朔躲葫淘颠踪亩坞桌舀距艺踢曼蜡枪纵讯鱼坎凑诀屑盾chap2 Algorithmchap2 Algorithm 1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其它的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称N--S结构化流程图。 蹋眺引舌寺垃膊臼挺或舀俐局办灾灼箭闺倘肤警肮央胺埔衍症踪儒平嘴潍chap2 Algorithmchap2 Algorithm N-S流程图用以下的流程图符号： (1)顺序结构 (2)选择结构 (3)循环结构 尽效终途遗娩伯墩砰蛊堂禄字饵音砸眶灶助箕弦巫呕莆啤未让魁庞陈胯漫chap2 Algorithmchap2 Algorithm 用三种