第5章 算法及程序设计

第5章 算法及程序设计 n要点n算法数据结构程序设计n算术逻辑运算n非数值计算n面向过程和面向对象的程序设计。5.1 算法的描述与实现 n利用计算机解题的步骤是，实际的问题抽象为数学问题找到解决数学问题的方法转化为计算机算法用计算机程序设计语言编程调试程序运算得到结果。 5.1.1 计算机算法 n1. 计算机算法的特点计算机算法的特点n(1) 对于任何一组确定的输入，都在有限的处理步骤后得到一组明确的输出。n(2) 计算机输出的结果是明确的。n(3) 计算机只能做有限步骤运算（处理）。 n可以手工用4(1-1/3+1/5-1/7+1/9- )的公式，无限精确地计算圆周率，但没有一种计算机算法能实现无限精确地计算圆周率。 n1. 算法表示方法算法表示方法n(1)流程图表示法流程图表示法n利用基本流程图符号的组合，可以表示较复杂的设计思想。它主要由下面一些符号及流程指向线组成。n主要包括：开始、结束、输入、输出、过程、判断、循环等。例如，输入一个数，如果它为0,输出“0”,否则输出“0”(2) 问题分析图表PAD法nPAD(Problem Analysis Diagram )是一种二维树形结构的软件设计表现方法。它强调“自顶向下，逐步求精”的设计思想。基本符号例：设计菜单程序(3) 表达式 n 在高级程序设计语言中，表达式类似数学中的计算公式，但与数学公式有较大区别。n 表达式是由变量名及运算符组成的式子表达式是由变量名及运算符组成的式子。n 1) 特殊运算符号 程序设计语言中，只能以ASCII符号组成表达式，因此运算符号与数学中使用的符号有一些不相同。例如算数运算符号在C语言中：“*”表示乘法，“/”表示除法。C语言中还包括许多数学中没有的运算符号，例如“&变量名”表示取变量的地址运算，“*变量名”表示间接访问变量运算。n 2)变量名是符号化的内存地址,不是代数中的“未知数”的概念。n在使用变量运算之前，它一定已被赋值。n C语言表达式举例：nZ=12*(A+3.7)/BnCP=&C5.1.2 数值计算 n1 利用表达式作计算n(1)算术表达式 n例：输入圆半径，计算圆面积n#include “stdio.h” /*标准 io头文件*/nmain() /*主函数 */nfloat r,s; /*定义变量类型*/nscanf (“%f”,&r); /*输入半径值 */ns=3.14*r*r; /*计算面积 */nprintf(“s=%f”,s); /*输出 */ (2)关系表达式n关系表达式的值是逻辑值“真/伪”，“1 / 0”。n例如xy,a+b9.8都是合法表达式。n当x=10,y=9时，c=xy表示c被赋值为1（c语言中真用1表示）。(3) 逻辑表达式n用逻辑运算符将关系表达式或逻辑量联系起来的式子为逻辑表达式。n例如：&为逻辑与运算符号。ne=(a=b)&(c3/(n1)，当误差0.005时， N=5。 （3）有效数字误差n有效数字的最后一位与真值在此位相差正负1。n例如：3位有效数字1.23的真值在1.220 x 与1.229999999 之间。在第4位作四舍五入。n（4）精度转换误差n实际上高精度与低精度数运算结果应以低精度为准，但在计算机程序设计语言中，多数是把低精度自动转换为高精度。5.1.3 常用算法n1. 枚举法n判断集合中，所有元素为真，则命题为真。n例如，若公鸡每只3元，母鸡每只5元，小鸡每只1元，求100元买100只鸡有多少种方案。nx+y+z=100n3*x+5*y+z/3=100n两个方程式不可能解出3个未知数，但可以用x、y、z的各种组合来试验。n当试验次数超过10的10次方时，实用性不大。2. 递归算法n定义算法的过程中使用了被定义的算法本身。n(1) 直接递归 n重复一组或一个操作，例如累加，累减，累乘，累除等。na=a+1 ，把a加1后的值赋给a。 (2) 间接递归n程序用到它自身的前一步或前几步。n例1 计算阶乘。n2!=1*2n3!=1*2*3=2!*3n(N+1)!=N!*(N+1)n例2 有若干球，若每次拿走剩下的一半还于1个，当第10次要拿球时，仅剩下1个球，问原来有多少球？3 迭代算法n每一次计算都在前一次计算的基础上进行，解决已知有解，但难用表达式表示的问题。（1）对分法（2）逐次逼近法4 回朔法n枚举和试探的结合。将要解决的问题过程分为若干结点，每个结点有若干可供选择的后续结点。若不满足条件，返回到上一层结点，恢复刚才的参数，再试探其他分支。5 排序n将杂乱无章的数据按升序或降序排列。n常用冒泡法6 插值 n一些函数表无法用f(x)表示，在表中插入一些中间值，构成新的表，用p(x)，近似代替f(x)。要求p(xi)=f(xi)，xi为已知点。7 数据压缩与解压缩n 科学家在研究中发现，大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。n 计算机中用二进制表示的数据文件（包括数字或符号）中有许多是同一个或同一组数据的多次重复。重复的数据使得文件的总长度变长，不利于存储和传输。n 设计算法，尽量去除文件中的重复数据，形成等效的新文件是数据压缩数据压缩要解决的问题。 n反之，把已经压缩了的文件恢复成原来未压缩的文件是解压缩解压缩要解决的问题。n 为了提高压缩比例，压缩可分无损压缩和有损压缩两大类。无损压缩比例较小，一般在一倍以下，有损压缩比例可达几倍，十几倍，甚至几十倍！n 前者用于对文档、程序、重要数据的压缩，后者多用于对声音、图像、影像等文件的压缩。压缩技术大致可以按照以下的方法分类压缩技术大致可以按照以下的方法分类常用压缩/解压缩软件n在Windows 操作系统支持下的压缩/解压缩软件很多，以WinRAR和WinZIP最常用，压缩比例较高，可支持的压缩文件类型较多。5.2 程序设计方法 n 程序设计方法已有很大发展：n个人集体协作n利用程序设计语言软件开发平台n面向过程面向对象n手工生产软件工程5.2.1 面向过程的程序设计 n 这种程序设计方法是先把计算机要处理的事务分解成若干个独立的过程（ procedures ），自顶向下不断的把复杂的处理分解为子处理，一层一层地分解下去，直到仅剩下若干个容易处理的子处理为止。再用面向过程的开发语言（汇编、C语言等）编制源程序，然后经过编译形成计算机可执行程序，通过反复修改最后完成设计工作。n 这种方法的理论基础是数据结构和算法，流程图能较好反映整个设计和执行过程。1 结构化程序设计方法n主要特点是：把过程分为顺序、条件转移（循环）、分支、子过程等标准程序功能模块，每块都只能有唯一的入口和出口，模块之间通过入口、出口连接。由于块内的程序结构是封闭的，因此便于设计和检验程序的正确性。适合开发小型应用软件。n 2 支持面向过程设计的高级程序设计语言n常用的有：n（1）C语言（包括Microsoft C、Turbo C等多种版本） 它是于20世纪60年代在ALGOL语言基础上研制的。 其显著特点是代码及数据分隔,即程序的各个部分除了必要的信息交流外彼此独立。C语言提供给用户各种函数，这些函数可方便的调用，并具有多种循环、条件语句用来控制程序流向，从而使程序完全结构化。C语言还提供许多汇编一级的指令，可直接指挥硬件工作，因此也有人称它为中间级语言。 n（2） Pascal 语言 它是于20世纪70年代在ALGOL语言基础上研制的。PASCAL语言最初是为系统地教授程序设计而设计的，它具有丰富的数据类型，其控制结构体现了结构化程序设计原则。适合教学，科学计算与系统软件的研制。n（3） Basic语言n3 软件测试n （1）白箱法：设计多组输入数据，使得程序中的每一个分支都得到测试，要求测试中使用合理的输入数据能得到合理的输出结果；程序能对不合理的输入作出适当的反应。由于这种测试涉及程序的具体结构，有时实际操作有困难。n（2）黑箱法：设计多组输入数据，要求程序能在输入合理的数据后得到合理的输出结果；对不合理的输入作出适当的反应。5.2.2 面向对象的程序设计n1. 基本概念基本概念n(1) 对象n对象是包括自己的数据和一组对这些数据的操作的独立实体。对象对象=数据数据+作用于这些数据上的操作作用于这些数据上的操作。在面向对象的程序设计方法中，对象是基本单位。(2) 类n具有相同属性和操作对象的集合称为类。n编译系统为程序员预先设置了上万个类供选用。每个类可以派生（继承）出子类、孙类。实际上类是用来定义对象的抽象数据类型，它把整数、实数、符号等具体的数据类型和过程操作都已经隐藏起来了。 n(3) 封装n把对象的属性和操作结合成一个独立的系统单位，并尽可能隐蔽对象的内部细节。n(4) 继承n特殊类的对象拥有其一般类的全部属性与操作，称作特殊类对一般类的继承。 2 面向对象程序设计方法n要在应用程序的统筹规划和设计之后作以下步骤：n（1)创建对象或选用合适的对象；n（2)设置对象的属性；n（3)选择并设计适当的对象事件及操作；n（4)在过程代码中调用对象以实现对象之间的通信；n（5)将对象的方法程序和属性代码包装在一起。 n 面向过程程序设计方法与面向对象程序设计方法的区别：n 前者在程序设计时将数据和算法完全的分开，后者将数据和算法看作是不可分割的实体，称为对象；n 前者在程序设计过程中以算法为中心，围绕着实现系统功能的过程来构造系统，后者以数据为中心，所有的操作都围绕着数据而展开；n 前者是一句接一句地编写程序，后者主要是适当地创建对象、修改对象属性和编写对象的方法程序。 3 面向对象设计的高级程序设计语言n（1）VB （Visual Basic)，它是1991年微软公司推出的第一个可视化的编程软件，从VB 4.0版开始，VB也引入了面向对象的程序设计思想。VB功能强大，学习简单。而且，VB还引入了“控件的概念，使得大量已经编好的VB程序可以被直接使用，现在VB已经发布6.0版。 n（2）C+（包括Microsoft Visual C+,Borland C+，Turbo C+等）n这些程序设计工具软件的共同点是：n1)在Windows平台上运行；n2）可视化编程，一般用鼠标拖动工作窗口上的元件：表格(Form)视窗、元件盒(Component palette)等元件，设置、修改属性参数即可创建一个适合的对象。5.3.3 网络程序设计nWeb技术的广泛应用，一些适合网络环境的脚本（Script）语言应运而生。n脚本语言不是程序设计语言，它不能被编译后生成执行文件。利用文本编辑软件，根据脚本语言书写脚本文件是ASCII文件。n 浏览器根据脚本文件所规定的格式显示文字、声音、图形、影像。1 常用的脚本语言n （1） HTML语言语言 是超文本标记语言（Hyperlink Text Markup Language）的缩写。它是一种描述文档结构的语言，而不能描述实际的表现形式。HTML语言使用描述性的标记符（称为标签）来指明文档的不同内容。标签是区分文本各个组成部分的分界符，用来把HTML文档划分成不同的逻辑部分（或结构），如段落、标题和表格等。标签描述了文档的结构，它向浏览器提供该文档的格式化信息，以传送文档的外观特征。n n 用HTML语言写的页面是普通的文本文档（ASCII），不含任何与平台和程序相关的信息，它们可以被任何文本编辑器读取。n HTML文档包含两种信息：页面本身的文本和表示页面元素、结构、格式、和其它超文本链接的HTML标签。 nVBScript 它是一种HTML嵌入脚本化语言。微软公司把用于应用程序描述的Visual Basic语言压缩成一个更合理的子集，即VBScript，它具有易学易用等特点 n（2）JS (JavaScript)语言 是Netscape公司的一种基于对象（Object)和事件驱动（Event Driven）的脚本语言。n JS主要用于HTML页面，脚本嵌入在HTML源码中；Java是一种完整的、独立的编程语言，即可以在Web中应用，也可以用于与Web无关的情况。n JS编写的脚本不必在运行前编译，它可以直接写入Web页面中并由调用它的浏览器来解释执行。这样，一些基本交互作用就不用在服务器端完成，提高了客户端的响应时间。n n下面的JS脚本程序可显示时间。n!-now = new Date()hour = now.getHours()if (hour 12) document.write(现在是: + now.toLocaleString() else if (hour = 18) document.write(现在是: + now.toLocaleString() n（3）ASP (Active page server)语言 是在服务器端使用的脚本语言。服务器上必须安装脚本引擎。 脚本引擎是用于处理脚本的COM （组件对象模型）对象。ASP为脚本引擎提供主机环境并把 .asp 文件中的脚本交给脚本引擎处理。n ASP脚本中也可以插入其他脚本语言，凡是 .asp文件中使用的每种脚本语言，都要将他们相应的脚本引擎安装在Web 服务器上。 ASP中缺省语言是 VBScript ， 所以不用担心安装 VBScript 的脚本引擎，当 安装完 Active Server Pages 时，该引擎就已存在了。使用JScript 也不必有同样的担心。 但 是要使用一些不太常用的脚本语言时需要安装相应的脚本引擎 。 n（4）PHP语言语言 是一种服务器端、跨平台、HTML嵌入式的脚本语言。是一种常用于Web编程的语言。PHP酝酿于1994年，1995年发布其第一个公开版本，截止目前已发布的最新版本为PHP4.05。nPHP是一种免费软件，它能运行在包括Windows、Linux等在内的绝大多数操作系统环境中，常与免费Web服务软件Apache和免费数据库Mysql配合使用于Linux平台上，具有最高的性能价格比，号称“黄金组合”。2 常用的网页设计软件n标记或脚本语言虽然语法规则简单，但由于标记符号抽象，掌握起来仍有一定困难。利用一些网页设计工具软件，可做到可视化设计。n（1）Frontpage 是微软公司Office软件的一个组件，可直接所见即所得设计网页。自动生成全部脚本及相关文档。 （2）网页制作三剑客 Macromedia公司开发的网页制作工具Dreamweaver、Flash和Fireworks ，虽然工种不同，却是相辅相成。如若熟练掌握了它们，再加上你自己独特的设计思路，可以说没有做不出来的网页。 1)Dreamweaver 用于生成功能齐全的网站。2)Flash 用于制作动态及交互网站。它集声音、图像和动态效果于一身，生成一种后缀名为swf的文件，因压缩率极高故产生的文件很小，并支持边下载边浏览，所以特别适合制作多媒体交互网站。 n3) Fireworks 是一款功能强大的web图像创作工具，不需借助任何外挂软件就能制作矢量图形和位图，并独立完成所有设计过程，它的主要特点： 比较专业的矢量图形制作工具，支持矢量图形切换至位图编辑状态，可以在对象模式与图像模式之间相互转换，提供了更大的制作空间。 支持很多Photoshop的位图编辑方式，如渐变、阴影、外发光、纹理等等效果，还内建了很多已经做好比较成熟的风格和特效。它同样支持Photoshop的各种插件，使它的发挥空间更为广阔。n Fireworks与Dreamweaver 属于无缝集成，可以边做网页边修改图形，使得所有工作在一个平台上完成。 n3. 网格计算 n网格计算（Grid Computing）可以说是因特网发展的一个产物。它把分布式计算（Distributed Computing）思想发展到因特网上，把分布在因特网上的成千上万台计算机（包括微机）都当成结点，由结点组成网格，各个结点分担一定的计算任务，形成一个虚拟超级计算机。5.2.4 网页设计网页设计n1. 使用FrontPage 2000创建网页n(1)创建网站 n(2)利用向导建立个人站点 n(3)不使用向导建立网页 2. 发布网页发布网页n(1) 使用使用PWS服务器发布网页服务器发布网页n(2) 使用使用WIN 2000 Server3 软件工程及软件开发管理 n5.1.1 软件工程基本观念软件工程基本观念n1. 软件危机的主要表现软件危机的主要表现n对软件开发成本和进度的估计不准确。n软件质量不高、可靠性差，用户不满意。n缺乏适当的文档资料，不可维护、错误难以改正。n软件成本占系统总成本的比例逐年上升。n软件开发速度跟不上计算机硬件发展速度。 2. 产生软件危机的原因产生软件危机的原因n软件开发过程的进展情况较难衡量，软件开发的质量也较难评价。因此，管理和控制软件开发过程相当困难。 n在软件开发过程中，或多或少地采用了错误的方法和技术。n对用户需求没有完整准确的认识，就匆忙着手编写程序。3. 软件工程的目标与常用模型软件工程的目标与常用模型n软件工程的目标是提高软件的质量与生产效率，最终实现软件的工业化生产。n(1) 软件工程的主要环节(2)常见的软件工程模型 n1)线性模型 2)渐增式模型 4. 软件开发的基本策略软件开发的基本策略n复用 n分解化简 n折衷 5.3.2 软件计划及实施 n1. 软件计划包含内容软件计划包含内容n软件计划包含内容包括工作范围、资源、成本计算和进度安排。n(1) 范围n(2) 资源 n(3) 成本估算n(4) 进度安排 n2. 软件开发组织机构及成员n3. 软件开发工具和开发环境n4. 建立软件质量保证体系n5. 软件质量度量n6. 软件维护5.3.3 软件产权保护软件产权保护n为了保护软件生产者的合法权益，对商品软件应及时进行注册、认证。我国有专门的结构从事这方面服务工作，具体情况可参考“北京市软件企业认定和软件产品登记工作有关事项的通知”，北京软件行业协会网站主页，网址：http:/www.bsia-srrd.org。 小结n数据结构+算法=程序。算法是计算机算法，它与数学算法有一定区别。n计算机算法可用流程图、PAD图等方法描述，n具有完整功能程序的集合及其相应文档称为软件。采用软件工程的办法是目前专业软件生产的主要工作方式。n软件工程的目标是提高软件的质量与生产率，最终实现软件的工业化生产。参考文献n1 刘萍编.数值计算方法.北京：人民邮电出版社，2002.2n2 谭浩强著.C程序设计（第二版）. 北京：清华大学出版社，1999.12 n3 刘甲耀 严桂兰编著.PAD编程方法与C语言程序设计. 北京：电子工业出版社，1999.7n4 软件工程学习园地. http:/202.109.98.159/se/Title.htm结束n