c语言教欧学课件之第2章算法.ppt

2.1　算法的概念 2.2　简单算法举例 2.3　算法的特性 2.4　怎样表示一个算法 2.5　结构化程序设计方法 本章大纲 程序的灵魂——算法（1学时） 教学内容： 算法的概念 算法的特性； 算法的常用表示方法：流程图 基本要求： 理解算法的概念及特性； 了解怎样设计算法； 掌握算法的表示方法； 熟悉结构化程序设计方法。 重点：算法的常用表示方法 难点：算法的常用表示方法 2.1 算法的概念 2.2 简单算法举例 步骤1： 先求1×2，得到结果2。 步骤2： 将步骤1得到的乘积2再乘以3，得到结果6。 步骤3： 将6再乘以4，得24。 步骤4： 将24再乘以5，得120。 设两个变量，一个变量p代表被乘数，一个变量i代表乘数，乘积放在被乘数变量p中。将算法改写如下： S1： 使p=1 S2： 使i=2 S3： 使p×i，乘积仍放在变量p中，可表示为p×i=p S4： 使i的值加1，即i+1 = i S5： 如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。 2.3 算法的特性 1.有穷性 3.有零个或多个输入 图2.2 补充内容：算法的评价 1.时间复杂度 2.4 怎样表示一个算法 自然语言 传统流程图 结构化流程图 N-S流程图 伪代码 PAD图 计算机语言 2.4.1 用自然语言表示算法 2.4.2 用流程图表示算法 用一些图框表示各种操作，直观形象，易于理解。规定了一些常用的流程图符号(见图2.3)。 图 2.3 例2.6 将例2.1求5!的算法用流程图表示。 2.4.3 三种基本结构和改进的流程图 1. 传统流程图的弊端 (1) 顺序结构，如图2.14所示，虚线框内是一个顺序结构。 (2) 选择结构（选取结构，分支结构）如图2.15所示。 图2.16 (3) 循环结构： 图2.18当型循环 (1) 只有一个入口。 (2) 只有一个出口。 (3) 结构内的每一部分都有机会被执行到。 (4) 结构内不存在“死循环” 图2.20 没有通路 2.4.4 用N-S流程图表示算法 (2) 选择结构 图2.26当型循环 2.4.5 用伪代码表示算法 IF x 为正 print x ELSE print –x 2.4.6 用计算机语言表示算法 例2.20 将例2.16表示的算法（求5!）用C语言表示。 补充内容：PAD图 2.5 结构化程序设计方法 第二次作业： 习题（36页） 用流程图表示以下问题的算法 (1)有两个瓶子A和B，分别盛放醋和酱油，要求将它们互换(即A瓶原来盛醋，现改盛酱油，B瓶则相反)。 (4) 求1+2+3+…+100。 不再是表示算法,而是用计算机语言来实现算法 计算机是无法识别流程图和伪代码的。 main( ) { int i，t; t=1; i=2; while(i=5) { t=t*i; i=i+1; } printf(%d，t); } 1.PAD （Problem Analysis Diagram）即问题分析图 2.1973年由日本日立公司发明，得到一定程度的推广 3.它用二维数形结构的图表示程序的控制流，将这种图转换为程序代码比较容易。 优点 ： 1.程序结构十分清晰 2.易读、易懂、易记。程序自上而下，从左到右顺序执行 3.很容易将PAD图转换成高级程序语言源程序，由软件工具自动完成提高可靠性和生产率。 4.既可用于表示程序逻辑，也可用于描述数据结构 了解 PAD图的基本符号 自顶向下； 逐步细化； 模块化设计； 结构化编码 1.模块化思想：“分而治之” 2.模块划分的原则：聚合度高，耦合性低 3.子模块用函数实现，一般不超过50行。 凡邦之有疾病者、疕疡者造焉，则使医 分而治之。 模仿是一种最好的学习方法 * 嘉应学院杨久红制作于2010年末 * 知识改变命运 学习成就未来 第2章 程序的灵魂—算法 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。 算法成熟，已汇编成册 种类繁多，要求各异，难规范化 非数值运算算法 数值运算算法 如果想求1×2×…×1000， 难道要写999个步骤吗？ 例2.1 求1×2×3×4×5。 理解 循环算法解决 这类问题最拿手了！ 如果求1×3×5×7×9×11 怎么办呢？自己想想啦！ 1.包含有限的操作步骤 2.指“在合理的范围之内” 3. “合理限度” ，由人们的常识和需要而定 算法中的每一个步骤都应当是确定的 2.确定性 理解 所谓输