语言第02章ppt课件

第 2章 程序的灵魂 -算法2.0 引言2.1 算法的概念2.2 简单算法举例2.3 算法的特性2.4 怎样表示一个算法2.5 结构化程序设计方法Return1程序应包含 2方面的内容 :v对数据的描述 :程序中指定数据的类型和数据的组织形式 -数据结构v对操作的描述 :操作的步骤 ,即算法数据是操作的对象 ,操作的目的是对数据加工处理以得到期望的结果 .以厨师需菜谱打比方 .沃思 提出了一个公式 :数据结构 + 算法 = 程序除了上面 2个主要方面还有其他因素 ,程序可表示为 :程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环境4方面中 :算法是灵魂 ,数据结构是加工对象 ,语言是工具 ,编程要采用合适的方法 .本书不单单讲算法或是语言规则 ,而是结合这 4方面 ,如何编写 C程序Return2.0 引言22.1 算法的概念 算法 :解决一个问题而采取的方法和步骤v做任何事情都有一定的步骤 .如开会 ,购物 ,考大学 ,按一定顺序进行，缺一不可，日常生活中人们意识不到每件事都需事先设计出 “行动步骤 ” 。v并不是只有 “计算 ”的问题才有算法 .例如 :太极拳的拳谱 ,乐谱v不仅要保证算法正确 ,还要考虑的是算法的质量 .例如求解 本书只考虑计算机算法 .v数值算法 : 目的是求数值解 . 如求方程的根 ,求积分等v非数值算法 : 包括的面非常广泛 .最常见的用在事物管理领域Return32.2 简单算法举例 案例 2.1求 5! 。v方法 1：步骤 1：先求 12，得结果 2步骤 2：将步骤 1的结果乘以 3，得结果 6步骤 3： 6再乘以 4，得 24步骤 4： 24再乘以 5，得最后的结果 120。分析：算法正确，但太烦琐。若要求 1000 !，要写多少步骤呢？且不方便的是每次都直接使用上一步骤的结果v方法 2： 设变量 p为被乘数 (乘积 )， i为乘数 ，改写如下S1：使 p=1S2：使 i=2S3： p ipS4： i+1 iS5：若 i不大于 5，则回到 S3； 否则算法结束。最后的 p就是 5！v分析：若求 1 3 5 7 9 11，只做很少的改动即可。 S2： i=3 S4： i+2 i S5： i11， 回到 S3， 否则结束。说明方法 2简练且通用。若条件改成 i0 ; i+ ) 。 实际上， “有穷性 ”是指在一个 “合理的范围内”。若让计算机执行一个历时几千年才结束的算法，虽然是有穷的，但超过了合理的限度。 “合理限度 ”无严格标准，根据常识和需要而定 确定性v 算法中的每一步骤的含义都应当是确定唯一的，不应当产生 “歧义性 ”。如 “手举过头顶 ” “n被一个整数除，得余数 r。 ” 有零个或多个输入v 输入是指在执行算法时需要从外界取得必要的信息。例如，算法：判断一个数是否是素数，求 2个整数的最大公约数，求 n个数的方差等。当然也可以没有输入。 有一个或多个输出v 算法的目的就是求解，解就是输出。不一定是计算机打印输出。没有输出的算法没有意义 有效性v 算法的每一步骤应当有效的执行，得到确定的结果。如一个除数为 0表达式是不能有效执行的。算法如同 “黑箱子 ”，从外部特性了解算法的作用，就可使用算法。但自己要学会设计算法 Return 102.4 怎样表示算法 2.4.1 用自然语言表示算法 2.4.2 用传统流程图表示算法 2.4.3 三种基本结构和改进的流程图 2.4.4 用 N-S流程图表示算法 2.4.5 用伪代码表示算法 2.4.6 用计算机语言表示算法Return112.4.1 用自然语言表示算法 2.2节 算法举例中讲的算法就是用自然语言表示的。自然语言就是日常使用的语言，如汉语，英语等。v通俗易懂，但文字冗长，易出现 “歧义 ”“张先生对李先生说他的孩子考上了大学 ”，他指的谁？v描述包含分支和循环的算法，不是很方便适用描述简单的问题Return122.4.2 用流程图表示算法 用 图形表示算法，直观形象，易理解。美国国家标准化协会 ANSI（american national standard institute） 规定了一些常用的流程图符号：起止框 输入输出框 判断框 处理框连接点流程线注释框x0打印 x 打印 -x图 2.4 判断框有一入两出，根据给定的条件判断执行的操作图 2.5 连接点：把不同地方的流程线连接起来。画不下才分开来，可避免流程线交叉或过长，使流程图清晰。注释框：不是必要的部分，作些必要的说明以帮助阅读和理解13案例 2.6开始1t2ititi+1ii5打印 t结束YN图 2.7案例 2.1 求 5！的算法的流程图流程图一般包括以下几个部分 : 表示相应操作的框; 带箭头 的流程线 (反映各框的执行次序 ); 框内外的文字说明 .14案例 2.71igi80打印 ni， gii+1ii50结束YNNY图 2.9 案例 2.2的流程图表示 :输入 50个学生的学号和成绩且将 80分以上的打印出来开始1ii+1ii50输入 ni， giYNni,gi为第i个学生的学号和成绩15案例 2.8 判断闰年算法的流程图表示y+1yy2500结束YN开始2000yy不能被 4整除y不能被 100整除y不能被 400整除打印 y“是闰年 ”打印 y“不是闰年 ”打印 y“是闰年 ” 打印 y“不是闰年 ”YNYNY N16案例 2.9 求 (案例 2.4)的算法的流程图表示 开始1sum2deno1sign(-1)signsigndeno+1denodeno100结束YNsign(1/deno)termsum+termsum图 2.11 17案例 2.10 判断素数的算法(案例 2.5)的流程图表示i+1ir = 0 ?结束Y开始输入 n打印 n“不是素数 ”N2in/i的余数 r打印 n“是素数 ”i ?YN图 2.12传统流程图的优点 :直观形象 ,逻辑关系清楚缺点是 :篇幅较多 ,费时又不方便 .N-S结构化流程图已代替传统的流程图Return返回图 2.34 182.4.3 三种基本结构和改进的流程图 传统流程图的弊端v对流程线没有严格的限制 ,复杂的算法就会使流程图变得毫无规律 ,难以阅读和修改 ,算法的可靠性和可维护性不能得到保证 (见书中 P24 图 2.13)v为提高算法的质量 ,必须限制流程的随意转向 .可算法不可能由一个个框按顺序执行 .所以人们设想规定了几种基本结构 ,由各个基本结构顺序排列组成算法 . 三种基本结构v顺序结构 (最简单 )v选择结构 (又称选取或分支结构 )v循环结构 (重复结构 )当型 (While)直到型 (Until)19ABab图 2.14 顺序A BabpY N图 2.15 选择 (A或 B可一空 )Aabp1 YNAabp2Y N图 2.17 循环(While和 Until型 )共同特点 : 只有一入口 (a点 ) 只有一出口 (b点 ) 每一部分都有机会被执行 结构内不存在死循环具有以上特点的都可作为基本结构 ,但最基本就是以上 3种 ,其他的可以看作为由 3种最基本结构派生出来的 .Return程序演示 1程序演示 2202.4.4 用 N-S流程图表示算法 1973年美国人 Nassi和 Shneiderman提出了新的流程图形式，即 N-S结构化流程图。适合结构化程序设计，省略掉了带箭头的流程线，算法写在一个矩形框内，还可以包含框。 用到以下流程图符号： 其他的可用这几种结构组合。如图 2.24中的 A可以是选择结构， B可以是循环结构AB图 2.24 顺序结构A BP 不成立成立图 2.25 选择结构A当 p1成立图 2.26 当型循环结构A直到 p2成立图 2.27 直到型循环结构A当 p1成立211t2ititi+1i直到 i5打印 t图 2.29 案例 2.11 求 5！1ii+1i直到 i50图 2.31 例 2.12 50名学生成绩输入 ni,gi1igi80是 否输出ni,gii+1i直到 i5022例 2.13 判定闰年的算法的 N-S表示y/400的余数否是 为 0打印 y“是闰年 ”打印 y“非闰年 ”y/100的余数不为 0 否是y/4的余数为 0打印 y“是闰年 ”打印y“非闰年 ”否是y+1y直到 y 25002000y图 2.321sum2deno1sign(-1)signsign1/denosigntermsum+termsumdeno+1deno直到 deno100打印 sum例 2.14 求 算法的 N-S表示图 2.3323图 2.34变换使符合基本结构的特点，以解决 2个出口点的问题。加了个标志变量 wi+1ir = 0 ? Y开始输入 nN0w 2in/i的余数 ri 和 w=0NY1w结束打印 n“不是素数 ”打印 n“是素数 ”w=0Y N24i+1in/i的余数 r输入 n0w 2ir = 0是 否1w直到 i 和 w=0w=0是 否输出 n“是素数 ”输出 n“不是素数 ”图 2.35N-S的 优点 ： 比文字描述直观、形象、易理解 比传统流程图紧凑易画，废除了流程线，由各个基本结构按顺序组成总之 ，结构化的算法由一些基本结构按顺序组成的；基本结构又可以包含其他的基本结构；流程的跳转只存在基本结构范围内，之间不存在；非结构化的算法可以用等价的结构化算法代替；若算法不能分解成若干个基本结构，必然不是结构化的算法Return252.4.5 用伪代码表示算法 设计算法时要反复修改，画、修改流程图麻烦。为方便常用称为伪代码的工具。 伪代码 是用介于自然语言和计算机语言之间的文字和符号来描述算法的。每一行（或几行）表示一个操作。不用图形符号，书写方便，格式紧凑，易懂，向计算机语言算法过渡方便 计算机语言中的语句关键字用英文表示，其他可用汉字表示，以便于书写和阅读为原则。无固定的语法规则，只要把意思表达清楚，写成清晰易读的形式。 优点： 书写格式自由，易表达设计者的思想，容易修改。缺点：不如流程图直观，可能会出现逻辑上的错误。适合软件专业人员，初学者一般采用 N-S。 下