计算机概论 毛汉书 1 第5章 算法及程序设计

《计算机概论 毛汉书 1 第5章 算法及程序设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章算法及程序设计要点算法＋数据结构＝程序设计算术逻辑运算非数值计算面向过程和面向对象的程序设计。5.1算法的描述与实现利用计算机解题的步骤是，实际的问题→抽象为数学问题→找到解决数学问题的方法→转化为计算机算法→用计算机程序设计语言编程→调试程序→运算得到结果。5.1.1计算机算法1.计算机算法的特点(1)对于任何一组确定的输入，都在有限的处理步骤后得到一组明确的输出。(2)计算机输出的结果是明确的。(3)计算机只能做有限步骤运算（处理）。可以手工用π＝4(1-1/3+1/5-1/7+1/9-…)的公式，

2、无限精确地计算圆周率，但没有一种计算机算法能实现无限精确地计算圆周率。1.算法表示方法(1)流程图表示法利用基本流程图符号的组合，可以表示较复杂的设计思想。它主要由下面一些符号及流程指向线组成。主要包括：开始、结束、输入、输出、过程、判断、循环等。例如，输入一个数，如果它为0,输出“＝0”,否则输出“<>0”(2)问题分析图表PAD法PAD(ProblemAnalysisDiagram)是一种二维树形结构的软件设计表现方法。它强调“自顶向下，逐步求精”的设计思想。基本符号例：设计菜单程序(3)表达式在高级程序

3、设计语言中，表达式类似数学中的计算公式，但与数学公式有较大区别。表达式是由变量名及运算符组成的式子。1)特殊运算符号程序设计语言中，只能以ASCII符号组成表达式，因此运算符号与数学中使用的符号有一些不相同。例如算数运算符号在C语言中：“*”表示乘法，“/”表示除法。C语言中还包括许多数学中没有的运算符号，例如“&变量名”表示取变量的地址运算，“*变量名”表示间接访问变量运算。2)变量名是符号化的内存地址,不是代数中的“未知数”的概念。在使用变量运算之前，它一定已被赋值。C语言表达式举例：Z=12*(A+3.

4、7)/BCP=&C5.1.2数值计算1利用表达式作计算(1)算术表达式例：输入圆半径，计算圆面积#include“stdio.h”/*标准io头文件*/main()/*主函数*/{floatr,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语言中

5、真用1表示）。(3)逻辑表达式用逻辑运算符将关系表达式或逻辑量联系起来的式子为逻辑表达式。例如：&&为逻辑与运算符号。e=(a<=b)&&(c<=d)，如果a=1,b=2,c=3,d=3则e被赋值为1。2.算法设计(1)尽量节约内存、减少计算次数设计算法时，要综合考虑：计算机的内存储器大小是有限的，因而数字的范围、精度是有限的；计算机的计算速度是有限的，因而等待程序执行的时间是有限的。因此在设计算法时要尽量节约内存、减少指令执行次数。9*9比9^2运算快(2)尽量使用编译，不使用解释语言。(3)使用内存覆盖技

6、术。3.算法误差(1)二进制小数转换误差十进制0.1转换为二进制为0.001100110011001100110011……计算浮点数可能产生积累误差。(2)截断误差计算由于误差>3/(n＋1)，当误差＝0.005时，N=5。（3）有效数字误差有效数字的最后一位与真值在此位相差正负1。例如：3位有效数字1.23的真值在1.220x与1.229999999…之间。在第4位作四舍五入。（4）精度转换误差实际上高精度与低精度数运算结果应以低精度为准，但在计算机程序设计语言中，多数是把低精度自动转换为高精度。5.1.3

7、常用算法1.枚举法判断集合中，所有元素为真，则命题为真。例如，若公鸡每只3元，母鸡每只5元，小鸡每只1元，求100元买100只鸡有多少种方案。x+y+z=1003*x+5*y+z/3=100两个方程式不可能解出3个未知数，但可以用x、y、z的各种组合来试验。当试验次数超过10的10次方时，实用性不大。2.递归算法定义算法的过程中使用了被定义的算法本身。(1)直接递归重复一组或一个操作，例如累加，累减，累乘，累除等。a=a+1，把a加1后的值赋给a。(2)间接递归程序用到它自身的前一步或前几步。例1计算阶乘。2

8、!=1*23!=1*2*3=2!*3(N+1)!=N!*(N+1)例2有若干球，若每次拿走剩下的一半还于1个，当第10次要拿球时，仅剩下1个球，问原来有多少球？3迭代算法每一次计算都在前一次计算的基础上进行，解决已知有解，但难用表达式表示的问题。（1）对分法（2）逐次逼近法4回朔法枚举和试探的结合。将要解决的问题过程分为若干结点，每个结点有若干可供选择的后续结点。若不满足条件，返回到上一层结点，恢复