c语言第02章算法.ppt

第二章 算 法,一、教学内容 1 算法的概念与简单实例 2 算法的特性 3 算法的描述 4 结构化程序设计方法介绍 二、教学重点与难点 1 算法的概念及算法的描述算法的流程图表示法； 2 编写实际问题的算法 三、教学方法与课时数 方法：讲授法 课时数：4节,四、 教学过程 (一) 算法的概念与简单实例 1 算法的概念 一个程序应包括两方面内容： 对数据的描述：即数据结构（数据类型，组织形式） 对操作的描述，即操作步骤。 计算机科学家WIRTH提出：程序=数据结构+算法 详细描述：程序=数据结构+算法+程序设计方法+语言工具和环境 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 计算机算法分为两大类别：数值算法和非数值算法 2 简单算法举例 例1：求1X2X3X4X5的积 算法：S1：令P=1 S2：令i=2 S3：使PXi，积仍放在变量P中，即PX i=P S4：使i的值加1，即i+1=I S5：如果i的值不大于5，返回重新执行步骤S3以及S4，S5，否则，算法结束，得到计算结果。,例2：有50个学生，要求将成绩在80分以上者打印出来，用n 表示学生的学号，n1代表第一个学生的学号，ni代表第i个学生学号，g代表学生成绩，gi代表第i个学生成绩， 算法：S1：1=i S2：如果gi 80，打印ni和gi ，否则不打印 S3：i+1=i S4：如果i50，返回S2，继续执行，否则算法结束。 例3,例4,例5见教材P16-17 （二） 算法的特性 一个算法有以下特点： 1 有穷性:仅有有限的操作步骤 2 确定性:算法的每一个步骤应当是确定的， 即无“二义性”。 3 有零个或多个输入 4 有一个可多外输出 5 有效性:算法中的每一个步骤都应当有效执行,（三）算法描述 常用的描述方法有：自然语言，流程图，伪代码，PAD图等 1、用自然语言表示算法 用人们日常使用的语言（汉语，英语，日语等）来描述一个问题的求解过程，对人而言易理解，但不易写成计算机执行的程序。 2、用流程图表示算法 流程图是用一些图框表示各种操作。用图形表示算法直观形象，易于理解。常用的图框有： 起止框： 输入输出框： 判断框： 处理框： 流程线： 连接点： 注释框：-,【例2.3】判定2000 2500年中的每一年是否闰年，将结果输出。 润年的条件： 能被4整除，但不能被100整除的年份； 能被100整除，又能被400整除的年份； 设y为被检测的年份，则算法可表示如下： S1: 2000y S2:若y不能被4整除，则输出y“不是闰年”，然后转到S6 S3:若y能被4整除，不能被100整除，则输出y“是闰年”，然后转到S6 S4:若y能被100整除，又能被400整除，输出y“是闰年” 否则输出y“不是闰年”，然后转到S6 S5:输出y“不是闰年”。 S6:y+1y S7:当y2500时, 返回S2继续执行，否则，结束。,三种基本结构和改进的流程图,三种基本结构的共同特点： 1.只有一个入口； 2.只有一个出口； 3. 结构内的每一部分都有机会被执行到； 4. 结构内不存在“死循环”。,顺序结构：,2.选择结构：,3.循环结构,用伪代码表示算法 伪代码使用介于自然语言和计算机语言之间的文字和符号来描述算法。,用计算机语言表示算法 我们的任务是用计算机解题，就是用计算机实现算法； 用计算机语言表示算法必须严格遵循所用语言的语法规则。,（四）结构化程序设计方法 1971年，Wirth基于其开发程序设计语言和编程的实践经验，首次提出了“结构化程序计”(structured programming)的概念。 这个概念的要点是:不要求一步就编制成可执行的程序，而是分若干步进行，逐步求精。 第一步编出的程序抽象度最高，第二步编出的程序抽象度有所降低最后一步编出的程序即为可执行的程序。用这种方法编程，似乎复杂，实际上优点很多，可使程序易读、易写、易调试、易维护、易保证其正确性及验证其正确性。结构化程序设计方法又称为“自顶向下”或“逐步求精”法，在程序设计领域引发了一场革命，成为程序开发的一个标准方法，尤其是在后来发展起来的软件工程中获得广泛应用。有人评价说沃思的结构化程序设计概念“完全改变了人们对程序设计的思维方式”，这是一点也不夸张的。,结构化程序设计的基本思想是：任何程序都可以用三种基本结构的组合来实现。这三种基本结构是：顺序结构、选择结构和循环结构。这三种结构都具有一个入口和一个出口。 结构化程序设计方法的四条原则是：1. 自顶向下；2. 逐步求精；3.模块化；4.限制使用goto语句。 “自顶向下”是说，程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标