计算机导论-第五章程序设计

第五章程序设计本章内容5.1算法的定义与表示5.2简单的排序算法5.3程序设计语言简介5.4汇编语言5.1算法的定义和表示软件开发步入工程化阶段大型软件开发一般要经历“规划”、“需求分析”、“设计”、“编码”、“测试”和“运行维护”等阶段5.1.1算法的定义正确的“需求分析”对程序设计是至关重要的“编码”是对需求的实现。在“编码”过程中，算法很重要，良好的算法决定了程序的质量和性能软件的开发不仅需要处理大量的关系复杂的数据，这些数据通常都具有一定的结构性。因此，软件设计的实质就是设计合适的数据结构和基于这个数据结构的算法。于是N.沃恩提出了著名公式：

程序=数据结构+算法程序设计＝程序＋程序设计方法学模块化将复杂的算法(或程序)分解成若干个相对独立、功能单一的模块，利用这些模块组合成全局算法(或)程序。自顶向下结构设计方法从总体出发，居高临下，逐层分解和逐步细化。结构化程序设计方法：逐步求精结构设计方法

实质上也是一种自顶向下的设计方法。首先抛开细节设计出抽象算法，然后把抽象数据和操作逐步具体化，直到可以由计算机具体实现为止。算法的定义：是指解题方案的准确而完整的描述，也可以说它是解决某一特定问题的一组有穷规则的集合。（计算科学）可以用计算机来解决一类问题的程序和步骤算法特征：

有穷性：合理算法应在执行有限步后结束如：N!=1*2*3*…*(N-1)*N而式子：sum=1+2+3+…+N+…

不能称为算法，因为它执行有限步后仍不能结束

确定性：算法的每一步执行，其顺序和内容都必须有确切的规定，不能模棱两可

可执行性：即算法的所有操作都是能通过计算机程序代码实现，即可操作性

0个或多个输入；

1个或多个输出【例1】求解一元二次方程的算法方程a*x*x+b*x+c=0，其中a、b和c是不等于0的实数。具体参考步骤如下：p=b*b–4*a*cp≥0?计算实根计算复根输出YN结构化算法的属性：1.仅有一个入口2.仅有一个出口3.无死块4.无死循环块5.1.2算法的类型与结构算法类型数值算法非数值算法基本结构顺序结构分支结构循环结构结构化算法只能由三种控制结构所构成流程图算法的描述算法自然语言顺序结构选择结构循环结构顺序结构选择结构循环结构输语句伪代码循环语句赋值语句条件语句入出

算法的描述算法的描述还有计算机语言改进N-S四种图框类型输入、输出框处理框判断框起止框●N-S结构化流程图（1973年由美国学者I．Nassi和B．Shneiderman提出，N和S是这两位学者英文姓名的第一个字母）程序基本控制结构AB顺序分支?ABTFT?AF当循环循环FT?A直到型例2

给出求1+2+3+4+5的一个算法．算法1

按照逐一相加的程序进行．第一步

计算1+2，得到3；第二步

将第一步中的运算结果3与3相加，得到6；第三步

将第二步中的运算结果6与4相加，得到10；第四步

将第三步中的运算结果10与5相加，得到15．

自然语言示例算法2可以运用公式1+2+…+n=n(n+1)/2直接计算。第一步取n=5；第二步计算n(n+1)/2；第三步输出运算结果。循环结构例3求1×2×3×4×5。算法2S1T←1；S2I←2；S3T←T×I；S4I←I+1．S5如果I不大于5，重新执行

S3、S4、S5；否则算法结束．I>5NYT←1输出TI←2T←T×II←I+1开始结束例4求两个整数a和b的最大公约数——欧几里得辗转相除法。

问题背景与分析分析求出列数：a，b，r1，r2，…，rn–1，rn，0．这列数从第三项开始，每项都是前两项相除所得的余数，余数为0的前一项rn即是a和b的最大公约数．这种方法称为“欧几里得辗转相除法”．求68和32的最大公约数——欧几里得辗转相除法。68＝2×32＋432＝8×4＋0求66和23的最大公约数——欧几里得辗转相除法。66＝23×2＋2023＝20×1＋320＝3×6＋23＝2×1＋12＝1×2＋0输出ba←bYN输入a,br←Mod(a,b)b←rMod(a,b)≠0

流程图例5用二分法求方程x3

-

x

-1=0在区间[1,1.5]内的一个近似解（误差不超过0.001）。

问题背景与分析第一步确定有解区间[a,b]第二步取[a,b]的中点第三步计算函数在中点处的函数值第四步判断中点处函数值是否为0第五步判断新的有解区间的长度是否小于

给定的误差N输出x0x0←(a+b)f(x0)=0输入a,b,cb←x0f(a)f(x0)<0|a–b|<ca←x0f(a)←a3-a-1f(x0)←x03–x0–1YNYYN

流程图5.2简单的排序算法⑴冒泡排序法:⑵选择排序算法:⑶插入排序算法:5.3程序设计语言简介计算机程序设计语言的发展，经历了从机器语言、汇编语言到高级语言的历程。5.3.1机器语言电子计算机所使用的是由“0”和“1”组成的二进制数，二进制是计算机的语言的基础。也就是说，写出一串串由“0”和“1”组成的指令序列交由计算机执行，这种语言，就是机器语言。优点：由于使用的是针对特定型号计算机的语言，故而运算效率是所有语言中最高的；缺点：在一台计算机上执行的程序，要想在另一台计算机上执行，必须另编程序，造成了重复工作。5.3.2汇编语言用一些简洁的英文字母、符号串来替代一个特定的指令的二进制串，比如，用“ADD”代表加法，“MOV”代表数据传递等等。缺点：汇编语言同样十分依赖于机器硬件，移植性不好；优点：效率仍十分高，针对计算机特定硬件而编制的汇编语言程序，能准确发挥计算机硬件的功能和特长，程序精炼而质量高，所以至今仍是一种常用而强有力的软件开发工具。5.3.3高级语言这种语言接近于数学语言或人的自然语言，同时又不依赖于计算机硬件，编出的程序能在所有机器上通用。影响较大、使用较普遍的有FORTRAN、ALGOL、COBOL、BASIC、LISP、SNOBOL、PL/1、Pascal、C、PROLOG、Ada、C++、VC、VB、Delphi、JAVA

等。高级语言的发展也经历了从早期语言到结构化程序设计语言，从面向过程到非过程化程序语言的过程。相应地，软件的开发也由最初的个体手工作坊式的封闭式生产，发展为产业化、流水线式的工业化生产。FORTRAN语言FORTRAN是英文FORMULATRANSLATION的缩写，其含义是"公式翻译"。它是一种分块并列结构的面向过程的高级语言。

FORTRAN语言开始是为解决数学问题和科学计算而提出的，多年来的应用表明：由于FORTRAN本身具有标准化程度高，便于程序互换，较易优化，计算速度快；因此这种高级语言目前己广泛流行。国外几乎所有的计算机厂商都能向用户提供FORTRAN的编译程序和应用程序的版本。从使用的角度来看，目前FOBTBAN也不再是专用于科学计算(数值计算)中进行程序编制的语言了。越来越多的商业系统、企业单位也采用FORTRAN语言来编制商业和企业的管理程序。ALGOLALGOL:国际代数语言

ALGOL是计算机发展史上首批产生的高级语言，当时还是晶体管计算机流行的时代，由于ALGOL语句和普通语言表达式接近，更适于数值计算，所以ALGOL多用于科学计算机。

ALGOL这个名称是算法语言的简称，这种语言不是计算机制造公司为某种特定机器设计的，而是纯粹面向描述计算过程的，也就是所谓面向算法描述的。ALGOL是第一个清晰定义的语言，其语法是用严格公式化的方法说明的。ALGOL语言并没有被广泛的使用，但它是许多现代程序语言的概念基础。COBOL英文缩写:COBOL(CommonbusinessOrientedLanguage)解释:一种适合于商业及数据处理的类似英语的程序设计语言。这种语言可使商业数据处理过程精确表达。

COBOL（面向商业的通用语言，又称为企业管理语言、数据处理语言等，CommonBusinessOrientedLangauge）是最早的高级编程语言之一，是世界上第一个商用语言。BASICBASIC（Beginners‘All-purposeSymbolicInstructionCode，又译培基），意思就是“初学者的全方位符式指令代码”，是一种设计给初学者使用的程序设计语言。BASIC是一种直译式的编程语言，在完成编写后不须经由编译及连结等手续即可执行，但如果需要单独执行时仍然需要将其建立成执行档。

PascalPascal是一种计算机通用的高级程序设计语言。基于DOS的语言之一.Pascal语言可以被方便地用于描述各种算法与数据结构。是第一个结构化的编程语言CC语言是一种计算机程序设计语言。它既有高级语言的特点，又具有汇编语言的特点。它可以作为系统设计语言，编写工作系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。因此，它的应用范围广泛。

C语言对操作系统和系统使用程序以及需要对硬件进行操作的场合，用C语言明显优于其它解释型高级语言，一些大型应用软件也是用C语言编写的。

C语言具有绘图能力强，可移植性，并具备很强的数据处理能力，因此适于编写系统软件，三维，二维图形和动画。它是数值计算的高级语言。PROLOGProlog（ProgramminginLogic的缩写）是一种逻辑编程语言。它建立在逻辑学的理论基础之上。

最初被运用于自然语言等研究领域。现在它已广泛的应用在人工智能的研究中，它可以用来建造专家系统、自然语言理解、智能知识库等。同时它对一些通常的应用程序的编写也很有帮助。使用它能够比其他的语言更快速地开发程序，因为它的编程方法更象是使用逻辑的语言来描述程序。

AdaAda是一种表现能力很强的通用程序设计语言，它是美国国防部为克服软件开发危机，耗费巨资，历时近20年研制成功的。它被誉为第四代计算机语言的成功代表。Ada语言是美国国防部指定的唯一的一种可用于军用系统开发的语言，我国军方也将Ada作为军内开发标准（GJB1383《程序设计语言Ada》）。

C++C++语言是一种优秀的面向对象程序设计语言，它在C语言的基础上发展而来，但它比C语言更容易为人们学习和掌握。

Delphi由Borland公司推出的Delphi是全新的可视化编程环境，为我们提供了一种方便、快捷的Windows应用程序开发工具。它使用了MicrosoftWindows图形用户界面的许多先进特性和设计思想;采用了弹性可重复利用的完整的面向对象程序语言(Object-OrientedLanguage)、当今世界上最快的编辑器、最为领先的数据库技术。对于广大的程序开发人员来讲，使用Delphi开发应用软件，无疑会大大地提高编程效率，Java跨平台、动态的Web、Internet计算;Java语言是一个支持网络计算的面向对象程序设计语言.J2ME主要应用于嵌入式系统开发，如手机和PDA的编程(小型电子设备的系统)；J2EE主要用于分布式的网络程序的开发，如电子商务网站和ERP系统；J2SE开发桌面应用软件（单机软件）。工业编程语言：

A+|Ada|汇编语言|B|Brainfuck|C|C++|C++/CLI|Cg|COBOL|Eiffel|Erlang|FORTRAN|IronPython|Java|JRuby|Jython|LISP|Lua|Nuva|Oberon|Objective-C|Ocaml|Pascal|Perl|Powerbuilder|Python|QBASIC|R|REXX|Ruby|Self|Smalltalk|SQL|Tcl/Tk|VisualBasic|PHP|Lua|C#|F#|J#|VisualBasic.NET脚本编程语言：

ActionScript|JavaScript|JScript|Nuva|PostScript|VBScript|lua

学术编程语言：

APL/J|Haskell|Logo|ML|Prolog|Scheme|SAC其他编程语言：

ALGOL|BASIC|Clipper|Forth|Modula-2/Modula-3|MUMPS|PL/I|Simula

高级语言的下一个发展目标是面向应用，也就是说：只需要告诉程序你要干什么，程序就能自动生成算法，自动进行处理，这就是非过程化的程序语言。5.4汇编语言汇编语言(AssemblyLanguage)是面向机器的程序设计语言.汇编语言是一种功能很强的程序设计语言,也是利用计算机所有硬件特性并能直接控制硬件的语言。汇编语言”作为一门语言，对应于高级语言的编译器，需要一个“汇编器”来把汇编语言原文件汇编成机器可执行的代码。高级的汇编器如MASM,TASM等等为我们写汇编程序提供了很多类似于高级语言的特征，比如结构化、抽象等。在这样的