第五章算法及程序设计.ppt

第5章 算法及程序设计 要点 算法＋数据结构＝程序设计 算术逻辑运算 非数值计算 面向过程和面向对象的程序设计。 5.1 算法的描述与实现 利用计算机解题的步骤是，实际的问题→抽象为数学问题→找到解决数学问题的方法→转化为计算机算法→用计算机程序设计语言编程→调试程序→运算得到结果。 5.1.1 计算机算法 1. 计算机算法的特点 1 对于任何一组确定的输入，都在有限的处理步骤后得到一组明确的输出。 2 计算机输出的结果是明确的。 3 计算机只能做有限步骤运算（处理）。 可以手工用π＝4 1-1/3+1/5-1/7+1/9- … 的公式，无限精确地计算圆周率，但没有一种计算机算法能实现无限精确地计算圆周率。 1. 算法表示方法 1 流程图表示法 利用基本流程图符号的组合，可以表示较复杂的设计思想。它主要由下面一些符号及流程指向线组成。 主要包括：开始、结束、输入、输出、过程、判断、循环等。 例如，输入一个数，如果它为0,输出“＝0”,否则输出“ 0” 2 问题分析图表PAD法 PAD Problem Analysis Diagram 是一种二维树形结构的软件设计表现方法。它强调“自顶向下，逐步求精”的设计思想。 基本符号 例：设计菜单程序 3 表达式 在高级程序设计语言中，表达式类似数学中的计算公式，但与数学公式有较大区别。 表达式是由变量名及运算符组成的式子。 1 特殊运算符号 程序设计语言中，只能以ASCII符号组成表达式，因此运算符号与数学中使用的符号有一些不相同。例如算数运算符号在C语言中：“*”表示乘法，“/”表示除法。C语言中还包括许多数学中没有的运算符号，例如“变量名”表示取变量的地址运算，“*变量名”表示间接访问变量运算。 2 变量名是符号化的内存地址,不是代数中的“未知数”的概念。 在使用变量运算之前，它一定已被赋值。 C语言表达式举例： Z 12* A+3.7 /B CP C 5.1.2 数学计算 1 利用表达式作计算 1 算术表达式 例：输入圆半径，计算圆面积 #include “stdio.h” /*标准 io头文件*/ main /*主函数 */ float r,s; /*定义变量类型*/ scanf “%f”,r ; /*输入半径值 */ s 3.14*r*r; /*计算面积 */ printf “s %f”,s ; /*输出 */ 2 关系表达式 关系表达式的值是逻辑值“真/伪”，“1 / 0”。 例如x y,a+b 9.8都是合法表达式。 当x 10,y 9时，c x y表示c被赋值为1（c语言中真用1表示）。 3 逻辑表达式 用逻辑运算符将关系表达式或逻辑量联系起来的式子为逻辑表达式。 例如：为逻辑与运算符号。 e a b c d ，如果a 1,b 2,c 3,d 3则e被赋值为1。 2. 算法设计 1 尽量节约内存、减少计算次数 设计算法时，要综合考虑：计算机的内存储器大小是有限的，因而数字的范围、精度是有限的；计算机的计算速度是有限的，因而等待程序执行的时间是有限的。因此在设计算法时要尽量节约内存、减少指令执行次数。 9*9比9^2运算快 2 尽量使用编译，不使用解释语言。 编译后回形成可执行文件 *.exe ，可以脱离编译器运行。例如：C语言 解释语言只能在解释器中执行,解释器本身还要占用内存。例如：BASIC语言 3 使用内存覆盖技术。 当内存不够的时候，把内存中最久未使用的数据调出到硬盘，借用硬盘空间存储内存数据。称为虚拟内存技术。 操作系统一般提供虚拟内存技术。 3. 算法误差 1 二进制小数转换误差 十进制转换为二进制方法：用2乘，小数部分积为0时，正向取进位值。 十进制0.1转换为二进制为0.001XXXXXXXXXX01100110011… … 计算浮点数可能产生积累误差。 3. 算法误差 2 截断误差 计算 由于误差r 3/ n＋1 ，当误差r＝0. 005时， 取n 5。 （3）有效数字误差 有效数字的最后一位与真值在此位相差正负1。 数学上规定，有效数字的最后一位与真值在此位相差正负1。 例如：3位有效数字1.23的真值在1.220与1.座机电话号码9… 之间。在第4位作四舍五入。 （4）精度转换误差 实际上高精度与低精度数运算结果应以低精度为准，但在计算机程序设计语言中，多数是把低精度自动转换为高精度。 5.1.3 常用算法 1. 枚举法 判断集合中，所有元素为真，则命题为真。 例如，若公鸡每只3元，母鸡每只5元，小鸡每只1元，求100元买100只鸡有多少种方案。 x+y+z 100 3*x+5*y+3*z 100 两个方程式不可能解出3