大学计算机基础(第三版)-第8章-程序设计基础

第八章程序设计基础本章内容

程序设计的基本概念

算法

软件开发基础

常用的程序设计语言8.1程序设计的基本概念1.程序和程序设计2.程序的一般概念

一个计算机程序主要描述两部分内容:

数据结构—描述问题的每个对象之间的关系

算法—对问题的处理规则

经典公式:程序=数据结构+算法

程序设计：就是将解决某个问题的过程用程序设计语言描述出来，计算机按这个描述去逐步实现。

程序设计语言：编写程序的语言。8.1

程序设计的基本概念语言

人类交流思想的工具程序设计语言

人和计算机之间进行交流的语言

8.1程序设计的基本概念按照程序设计语言发展的过程，大概分为

机器语言（第一代语言）

汇编语言（第二代语言）

高级语言（第三代语言）

面向问题的语言（第四代语言）

智能性语言（第五代语言）低级语言8.1程序设计的基本概念

机器语言机器语言中的每一条语句实际上是一条二进制形式的指令代码指令格式如下：操作码

操作数

操作码

要完成的操作类型或性质操作数

操作的内容或所在的地址

8.1程序设计的基本概念例如:计算A=7+8的机器语言程序：

1011000000000111：把7放入累加器AX中0000010000001000：将8与累加器AX中的值相加，结果仍放入AX中

11110100：结束停机8.1

程序设计的基本概念

汇编语言汇编语言是使用一种叫做助记符来代替机器语言中的二进制数0和1，比如用“ADD”表示加法，“MOV”用来表示传送数据，等等。读写程序容易多了，对程序进行纠错和维护都变得方便了。例如，计算A=7+8的汇编语言程序：

MOVAX,7：把7放入累加器AX中ADDAX,8：将8与累加器AX中的值相加，结果仍放入AX中

HLT：结束停机8.1

程序设计的基本概念高级语言接近于数学语言或人的自然语言，同时又不依赖于计算机硬件。例如，将计算A=7+8的过程用高级语言Basic表示如下:A=7+8‘7+8相加的结果放入变量A中PRINTA‘输出A的值END‘程序结束8.1程序设计的基本概念语言处理程序（语言翻译程序）

因为计算机只能执行机器语言程序，所以用其他语言编写的程序不能被计算机直接执行，而必须经过一个翻译程序将它转换成相应的机器语言程序才能被计算机直接执行。完成这一转换功能的程序就是语言处理程序，语言处理程序是一种系统软件，有三种：

汇编程序（汇编器）

编译程序（编译器）

解释程序（解释器）8.1程序设计的基本概念

汇编程序（汇编器）汇编程序专门负责把用汇编语言编写的程序翻译成机器可直接执行的机器指令程序。机器语言程序汇编程序汇编语言源程序汇编方式执行过程8.1程序设计的基本概念高级语言翻译程序

编译程序——-对高级语言书写的程序进行整体上的识别与理解，将其翻译成一个功能等价的程序。编译方式执行过程数据编

辑源程序(*.cpp)可执行程序

(*.exe)结果目标程序（*.obj）连

接运行编

译编辑程序编译程序连接程序8.1程序设计的基本概念高级语言翻译程序

解释程序——对源程序进行逐句分析，若没有错误，将该语句转换成机器语言指令，并立即执行，即翻译一句执行一句。计算结果解释程序高级语言源程序解释方式执行过程

一般来说，程序设计语言都应包含以下四种成分：

数据成分

用以描述程序中所涉及的数据

运算成分

用以描述程序中所包含的运算

控制成分

用以描述程序中的控制结构

传输成分

用以表达程序中数据的传输

程序设计语言的组成

程序语言提供的数据类型：

基本数据类型一般程序设计语言中提供了数值类型（整数类型、实数类型）、字符类型、逻辑类型和指针类型等。

构造数据类型构造数据类型是由基本数据类型按照某种方式组合而成。一般有：数组类型、记录类型、枚举类型、文件等。

程序设计语言的组成

程序语言包含的运算

一般程序设计语言中都提供了能支持计算机进行算术运算和逻辑运算的运算符，一般有以下几类：

算术运算符——加（+）、减（-）、乘（*）、除（/）、乘方（**）等

关系运算符——大于（>）、小于（<）、大于等于（>=）、小于等于(<=)、等于(==)、不等于(!=)等

逻辑运算符——与(&&)、或(||)、非(!)

字符运算符——两个字符串联结、取子串等

程序设计语言的组成

程序语言提供的控制结构

程序设计语言的组成

ABAB条件NYA条件YNA条件YN选择结构循环结构输入和输出：程序的输入/输出分为两大类：

以文件形式数据传送

人—机交互输入/输出在不同的程序设计语言中由不同的语句或函数来实现。在C++中关于输入/输出的语句有：cin>>变量名1>>变量名2…；cout<<表达式1<<表达式2…；

程序设计语言的组成过程将重复处理程序段或分解的子功能编写成一个逻辑上独立的过程，当程序需要该过程时，只需调用它。使用过程可降低程序的复杂度，简化程序编写，便于调试。一般程序设计语言中有两种过程：

函数过程

函数名有返回值

子过程

子过程名没有返回值各种语言系统还提供了已定义好的大量标准函数，如数学函数、字符串函数、类型转换函数等，放在系统的函数库中，供用户直接调用。

程序设计语言的组成先定义后调用8.2算法

计算机语言只是一种工具。光学习语言的规则还不够，最重要的是学会针对各种类型的问题，拟定出有效的解决方法和步骤即算法。有了正确而有效的算法，可以利用任何一种计算机高级语言编写程序，使计算机进行工作。因此，设计算法是程序设计的核心。

算法是程序设计学习的重点。算法的概念

通俗地说，算法就是解决问题的方法和步骤。程序就是用计算机语言表述的算法。算法可以分为两大类：

数值计算算法

求数值解，其特点是少量的输入、输出，复杂的运算，如求高次方程的根、求函数的定积分等。

非数值计算算法

对数据的处理，其特点是大量的输入、输出，简单的运算，例如，对数据的排序、查找等算法算法的概念

例如:求两个正整数M和N的最大公因数的欧几里德算法为:第一步:求M除以N的余数R;第二步:若R=0,算法结束,即N为M和N的最大公因数第三步:否则,置M←N,N←R,返回step1算法的概念对应程序如下：#include<iostream.h>voidmain(){intm,n;cin>>m>>n;while(n!=0){r=m%n;m=n;n=r;}cout<<“m和n的最大公因数为:”<<m;}算法的概念

用计算机解决问题的算法应具有以下特征：

有穷性

能行性

确定性

可输入输出信息算法的表示

自然语言——使用人们能读懂的简短语句对算法的步骤进行描述。

流程图法——用一些图框、线条以及文字说明来形象地、直观地描述算法。

N-S流程图法——去掉了传统流程图中带箭头的流向线，全部算法以一个大的矩形框表示，框内还可以包含一些从属于它的小矩形框，适于结构化程序设计。

伪代码法——用介于自然语言和计算机语言之间的文字和符号来描述算法。

计算机语言——用计算机语言描述算法，只有用计算机语言编写的程序才能被计算机执行。算法的表示及三种基本结构3循环结构1顺序结构2分支结构num1

15；算法的表示及三种基本结构(1)

顺序结构【例】

求两数之和。块1块2块3流程图

寄存器35＋显示结果：35num115num220sum35num2

20；sum

num1+num2;

演示算法执行过程输出sum;算法的表示及三种基本结构(2)

分支结构【例】

输入三个数，输出其中的最大数。

x

7;y

12;z

10;if(x>y)max

x;elsemax

y;if(z>max)max

z;输出max;x7y12z10CPUmax12比较比较显示结果：12流程图条件块1块2真假演示算法执行过程算法的表示及三种基本结构(3)

循环结构流程图条件块真假【例】求4个整数的和。

0sum4count12x显示结果：60演示算法执行过程123142621642118600count

4;//整数个数sum

0;//累加和的初值while(count>0){x

输入一个整数;sum

sum+x;count

count-1;}输出sum;算法的概念

对同一个问题，可以有不同的解题方法和步骤。例如，求1+2+3+…+100，可以先进行1+2，再加3，再加4，一直加到100，也可采取100+(1+99)+(2+98)+…+(49+51)+50＝100+50+49×100＝5050。还可以有其它的方法。当然，方法有优劣之分。有的方法只需进行很少的步骤，而有些方法则需要较多的步骤。一般说，希望采用方法简单，运算步骤少的方法。因此，为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。常用算法介绍1.直接法2.枚举法3.递推法

解决的问题的种类与复杂程度各不相同决定了算法的多样性，但从其思想方法上可以将其归为以下几种：直接法、枚举法、递推法、递归法、回溯法等等。本节将介绍以下三种：常用算法介绍

直接法

直接法就是根据问题给出的条件直接求解，前面的很多例子都是这种算法的运用。这里不再举例。常用算法介绍

枚举法枚举法也称穷举法，基本思想是，在有限范围内列举所有可能的结果，找出其中符合要求的解。枚举法适合求解的问题是：问题可能的答案是有限个且答案是可知的，但又难以用解析法描述。这种算法通常需要用循环结构来完成。请看下例：【例】

给定一个正整数，判断其非负整数立方根是否存在，若存在，输出该立方根。常用算法介绍算法如下：分析：设某正整数为27，则非负整数立方根的取值范围为1—27，因此可在这一范围内对所有整数进行检测，满足立方根为27的就是所求整数。【例】求非负整数立方根算法：常用算法介绍numc271显示结果：3演示算法执行过程比较c*c*c2比较c*c*c3比较c*c*cnum

27；c

1；//立方根初值while(c<=num){if(c*c*c==num){输出c;break;//终止循环}elsec

c+1;}if(c>num)输出“无整数立方根”;常用算法介绍【例】

判断一个正整数是否素数，给出相应结果。分析：假设正整数num,如果num不是2，需要检测它是否含有除1和它本身之外的其他因子，如果有，就不是素数。检测方法是在2

num-1范围内逐个验证。算法如下：常用算法介绍【例】

判断一个数是否为素数算法#include<iostream.h>voidmain(){intnum;cin>>num;for(inti=2;i<num;i++)if(num%i==0)break;if(i==num)cout<<num<<“是素数”；

elsecout<<num<<“不是素数”；}常用算法介绍

递推法递推算法是通过问题的一个或多个已知解，用同样的方法逐个推算出其他解，如数列问题以及一些近似计算问题等。通常也要借助于循环。请看下例：

常用算法介绍【例】

求n!

分析：n!=1

2

3

n，因此可以从1开始，由1!乘以2得到2!，再乘以3得到3!

，以此推出n!。假定n＝4，算法如下：ni2factorial常用算法介绍【例】

求n!算法：显示结果：24演示算法执行过程124比较23比较64比较24比较5factorial

1; //阶乘初值i

2;n4;while(i<=n){factorial

factorial*i;i

i+1;}输出factorial;

8.3软件开发基础软件开发不同于编写小程序，程序并不代表软件，软件包括程序和文档两部分。应该把软件开发的全过程视为一项工程来处理，用工程的思想方法支持软件的开发，即软件工程。从而用较小的投入开发出更稳定更有效率的高质量的软件。

8.3软件开发基础软件开发的6个步骤：软件需求分析问题定义编写程序代码软件的测试软件维护制作文档

程序设计方法

传统的结构化程序设计

SP(StructuredProgramming)

面向对象的程序设计

OOP(ObjectOrientedProgramming)

传统的结构化程序设计传统的程序设计方法可以归结为“程序=算法+数据结构”，将程序定义为处理数据的一系列过程。这种设计方法的着眼点是面向过程的，特点是数据与程序分离，即数据与数据处理分离。

结构化程序设计的基本思想是采用自顶向下、逐步细化的模块化程序设计原则。在代码编写时，采用顺序、选择、循环三种基本控制结构，避免使用GOTO语句。

传统的结构化程序设计模块

22.12.2模块11.21.11.31.3.11.3.21.3.3模块

33.13.23.1.13.1.2

程序

传统的结构化程序设计

结构化程序设计为处理复杂问题提供了有力手段，但到80年代末，这种设计方法逐渐暴露出以下缺陷：

难以适应大型软件的设计。

程序可重用性差。

面向对象程序设计

面向对象的程序设计方法是另一种程序设计方法

基本思想是：使用类把数据和处理数据的过程放在一起作为一个整体。基本方法是：抽象同类型对象的共性，形成类。类中数据通常只能被本类处理，对象间通过消息进行通信。特征：封装性、继承性、多态性。

面向对象程序设计

对象的概念是面向对象技术的核心所在。面向对象技术中的对象就是现实世界中某个具体的物理实体在计算机逻辑中的映射和体现。对象、实体与类

现实世界中的实体可以抽象出类别的概念。对应于计算机世界就有一个类（class）的概念，因为类是一个抽象的概念的对应体，所以计算机不给它分配内存，只给对象分配内存。左图表达了计算机世界与现实世界之间的对应关系。计算机世界现实世界客观世界映射对象类抽象抽象实例化主观世界对象类实体抽象类别

面向对象程序设计FORTRAN语言FORTRAN语言是世界上第一个出现的高级程序设计语言FORTRAN是FORmulaTRANslator（公式翻译器）的缩写，它主要用于科学计算，现在仍然广泛用于数学、科学和工程计算问题领域。

8.4常用的程序设计语言PASCAL语言P