第8章算法与程序设计语言讲述.pptx

算法与程序设计语言 一 算法与程序 什么是程序？ 按一定的顺序安排的工作即操作序列 描述完成某项功能所涉及的对象和动作规则 计算机学科中,程序描述了计算机处理数据、解决问题的过程 2 程序和算法的关系是怎样的？ 引例: 从存放教职工档案的“d:\zgxx.txt”文件中，显示出教龄满30年的女教工的姓名和所在部门 3 程序=数据结构+算法 程序包括两方面的内容： （1）对数据的描述: 指定欲处理的数据类型和数据的组织形式，也就是数据结构。 例如教职工的姓名, 部门, 教龄等都具有相应的数据类型 文件d:\zgxx.txt指定了数据的组织形式。 （2）对操作的描述: 指定操作步骤， 例如“fopen”打开文件、“fscanf”读入数据、“If”判断是否满足条件等。 这些操作的先后顺序以及它们所作用的数据，要遵守一定的规则，即求解问题的的算法。 二 算法的概念 1 什么是算法? 计算机来解决的某一类问题的方法或步骤 算法是程序的核心 例:小球称重 9个编号小球中有一个的质量偏小，其余的质量标准。用一天平,无需砝码，检出质量偏小的小球。 4 解法一：9个小球分成5堆，（1,2）,（3,4）,（5,6）,（7,8）,（9） 解法二：可将9个小球分成3堆进行称量, (1,2,3),(4,5,6),(7,8,9),若1,2相等,则称量第三堆中,否则对偏轻的一堆继续称量。 5 哪种方法称量次数最少? 解法三：先将小球分成（1，2，3，4）与（5，6，7，8）两堆，若两堆的质量的相等则偏小的小球是第9个，否则将偏轻的小球分成两堆进行称量。 例:圆周率的计算 (1)割圆法 6 S正12边形=12 × △S=3 圆周率= S正12边形/R/R=3 算法步骤： ①量出圆的半径R ②做圆的内接正n边形 ③求小三角形的面积△S ④求圆的内接正n边形面积S= △S ×n ⑤求圆周率=S/R/R ⑥结束 公元3世纪，刘徽利用“割圆术”，也就是利用圆内接正六边形算起，依次将边数加倍，一直算到内接正3072边形的面积，从而得到圆周率的近似值为=3.1416，祖冲之把圆周率精确到小数点后15位 7 (2)利用求圆周率公式 同一个问题，可用不同的算法来求解 算法不同，求解的效率不同 选择效率高、容易理解和编程实现的算法 2 算法的两个要素 算法是由操作与控制结构两个要素组成 （1）操作 ①算术运算：加、减、乘、除等。 ②关系运算：大于、大于等于、小于、小于等于、等于、不等于等。 ③逻辑运算：与、或、非等。 ④数据传送：输入、输出、赋值等。 8 (a)顺序结构 (b)选择结构 （2）控制结构 各操作之间的执行顺序 顺序结构、选择结构、循环结构，称为算法的三种基本结构 9 (c)当型循环结构 (d)直到型循环结构 10 从整体上看是顺序结构 11 当型循环 3 算法的特点 12 4 算法的分类 （1）数值计算算法 用于科学计算 特点是少量的输入、输出，复杂的运算。 例如：计算圆周率，积分 （2）非数值计算算法 对数据的管理 特点是大量的输入、输出，简单的算术运算 和大量的逻辑运算。 例如：排序 查找替换 随着计算机技术的发展和应用面的普及，非数值计算算法涉及面更广，研究的任务更重。 13 5 算法的表示 自然语言 传统流程图 N-S流程图 伪代码 计算机语言 14 利用求圆周率公式 计算圆周率 分析:对通项式：ti= ， i=1，2，… ，进行累加，直到某项ti绝对值小于精度即|t|10-8为止。 15 自然语言 ①置初态：累加器pi←0，计数器i←1，第1项t←1，正负符号变化s←1； ②重复执行下面的语句，直到某项绝对值小于精度，转③； ?求累加和：pi←pi+t； ?为下一项作准备：i←i+1、s←-1*s、t←s*1/(2*i-1)； ③输出：显示结果pi*4。 ④结束 优点: 通俗易懂 缺陷： （1）不太严格，易产生歧义性。 （2） 繁琐、冗长，并且很难清楚地表达算法的逻辑流程，不直观。 16 传统流程图 采用一些图框、线条以及文字说明来形象地、直观地描述算法处理过程。 17 false 计算圆周率的流程图 缺陷： 制作费时 优点:较好地体现程序设计的逻辑 18 N-S流程图 由美国学者 I.Nassi和 B.Shneideman 提出 去掉了传统流程图中带箭头的流向线,全部算法以一个大的矩形框表示，该框内还可以包含一些从属于它的小矩形框 适于结构化程序设计。 19 计算圆周率N-S图 N-S图的三种控制结构 20 BEGIN pi←0 //变量赋初值 s←1 i←1 t←1 While (|t|≥10-8)