《大学计算机基础（第三版）》-艾德才-电子教案 第8章 程序设计基础

《《大学计算机基础（第三版）》-艾德才-电子教案 第8章 程序设计基础》由会员分享，可在线阅读，更多相关《《大学计算机基础（第三版）》-艾德才-电子教案 第8章 程序设计基础（55页珍藏版）》请在金锄头文库上搜索。

1、第八章,程序设计基础,本章内容, 程序设计的基本概念 算法 软件开发基础 常用的程序设计语言,8.1 程序设计的基本概念,1. 程序和程序设计,2.程序的一般概念,一个计算机程序主要描述两部分内容: 数据结构描述问题的每个对象之间的关系 算法对问题的处理规则 经典公式: 程序=数据结构+算法, 程序设计：就是将解决某个问题的过程用程序设计语言描述出来，计算机按这个描述去逐步实现。 程序设计语言：编写程序的语言。,8.1 程序设计的基本概念,语言 人类交流思想的工具,程序设计语言 人和计算机之间进行交流的语言,8.1 程序设计的基本概念,按照程序设计语言发展的过程，大概分为, 机器语言（第一代语

2、言） 汇编语言（第二代语言） 高级语言（第三代语言） 面向问题的语言（第四代语言） 智能性语言（第五代语言）,8.1 程序设计的基本概念,机器语言 机器语言中的每一条语句实际上是一条二进制形式的指令代码 指令格式如下：,操作码 要完成的操作类型或性质 操作数 操作的内容或所在的地址,8.1 程序设计的基本概念,例如: 计算 A=7+8 的机器语言程序：,10110000 00000111 ：把7 放入累加器AX中 00000100 00001000 ：将8与累加器AX中的值相加，结果仍放 入AX中 11110100 ：结束停机,8.1 程序设计的基本概念,汇 编 语 言 汇编语言是使用一种叫做

3、助记符来代替机器语言中的二进制数0和1，比如用“ADD”表示加法，“MOV”用来表示传送数据，等等。读写程序容易多了，对程序进行纠错和维护都变得方便了。 例如，计算 A=7+8 的汇编语言程序：,MOV AX,7 ：把7 放入累加器AX中 ADD AX,8 ：将8与累加器AX中的值相加，结果仍 放入AX中 HLT ：结束停机,8.1 程序设计的基本概念,高 级 语 言 接近于数学语言或人的自然语言，同时又不依赖于计算机硬件。 例如，将计算A=7+8的过程用高级语言Basic表示如下:,A=7+8 7+8相加的结果放入变量A中 PRINT A 输出A的值 END 程序结束,8.1 程序设计的基本

4、概念,语言处理程序（语言翻译程序） 因为计算机只能执行机器语言程序，所以用其他语言编写的程序不能被计算机直接执行，而必须经过一个翻译程序将它转换成相应的机器语言程序才能被计算机直接执行。完成这一转换功能的程序就是语言处理程序，语言处理程序是一种系统软件，有三种： 汇编程序（汇编器） 编译程序（编译器） 解释程序（解释器）,8.1 程序设计的基本概念, 汇编程序（汇编器） 汇编程序专门负责把用汇编语言编写的程序翻译成机器可直接执行的机器指令程序。,汇编方式执行过程,8.1 程序设计的基本概念,高级语言翻译程序 编译程序-对高级语言书写的程序进行整体上的识别与理解，将其翻译成一个功能等价的程序。,

5、编译方式执行过程,8.1 程序设计的基本概念,高级语言翻译程序 解释程序对源程序进行逐句分析，若没有错误，将该语句转换成机器语言指令，并立即执行，即翻译一句执行一句。,解释方式执行过程,一般来说，程序设计语言都应包含以下四种成分： 数据成分 用以描述程序中所涉及的数据 运算成分 用以描述程序中所包含的运算 控制成分 用以描述程序中的控制结构 传输成分 用以表达程序中数据的传输,程序设计语言的组成,程序语言提供的数据类型： 基本数据类型 一般程序设计语言中提供了数值类型（整数类型、实数类型）、字符类型、逻辑类型和指针类型等。 构造数据类型 构造数据类型是由基本数据类型按照某种方式组合而成。一般有

6、：数组类型、记录类型、枚举类型、文件等。,程序设计语言的组成,程序语言包含的运算 一般程序设计语言中都提供了能支持计算机进行算术运算和逻辑运算的运算符，一般有以下几类： 算术运算符加（+）、减（-）、乘（*）、除（/）、乘方（*）等 关系运算符大于（）、小于（=）、小于等于(=)、等于(=)、不等于(!=)等 逻辑运算符与(&)、或(|)、非(!) 字符运算符两个字符串联结、取子串等,程序设计语言的组成,程序语言提供的控制结构,程序设计语言的组成,选择结构,循环结构,输入和输出： 程序的输入/输出分为两大类： 以文件形式数据传送 人机交互 输入/输出在不同的程序设计语言中由不同的语句或函数来实

7、现。 在C+中关于输入/输出的语句有： cin变量名1变量名2； cout表达式1表达式2；,程序设计语言的组成,过程 将重复处理程序段或分解的子功能编写成一个逻辑上独立的过程，当程序需要该过程时，只需调用它。 使用过程可降低程序的复杂度，简化程序编写，便于调试。 一般程序设计语言中有两种过程： 函数过程 函数名有返回值 子过程 子过程名没有返回值 各种语言系统还提供了已定义好的大量标准函数，如数学函数、字符串函数、类型转换函数等，放在系统的函数库中，供用户直接调用。,程序设计语言的组成,先定义后调用,8.2 算 法,计算机语言只是一种工具。光学习语言的规则还不够，最重要的是学会针对各种类型的

8、问题，拟定出有效的解决方法和步骤即算法。有了正确而有效的算法，可以利用任何一种计算机高级语言编写程序，使计算机进行工作。因此，设计算法是程序设计的核心。 算法是程序设计学习的重点。,算 法 的 概 念,通俗地说，算法就是解决问题的方法和步骤。 程序就是用计算机语言表述的算法。 算法可以分为两大类： 数值计算算法 求数值解，其特点是少量的输入、输出，复杂的运算，如求高次方程的根、求函数的定积分等。 非数值计算算法 对数据的处理，其特点是大量的输入、输出，简单的运算，例如，对数据的排序、查找等算法,算 法 的 概 念,例如:求两个正整数M和N的最大公因数的欧几里德算法为: 第一步: 求M除以N的余

9、数R; 第二步: 若R=0,算法结束,即N为M和N的最大公因数 第三步: 否则,置MN,NR,返回step1,算 法 的 概 念,对应程序如下： #include void main() int m,n; cinmn; while(n!=0) r=m%n; m=n; n=r; cout“m和n的最大公因数为:”m; ,算 法 的 概 念,用计算机解决问题的算法应具有以下特征： 有穷性 能行性 确定性 可输入输出信息,算 法 的 表 示, 自然语言使用人们能读懂的简短语句对算法的步骤 进行描述。 流程图法用一些图框、线条以及文字说明来形象地、直观地描述算法。 N-S流程图法 去掉了传统流程图中带

10、箭头的流向线，全部算法以一个大的矩形框表示，框内还可以包含一些从属于它的小矩形框，适于结构化程序设计。 伪代码法 用介于自然语言和计算机语言之间的文字和符号来描述算法。 计算机语言 用计算机语言描述算法，只有用计算机语言编写的程序才能被计算机执行。,算法的表示及三种基本结构,3 循 环 结 构,1 顺 序 结 构,2 分 支 结 构,num115；,算法的表示及三种基本结构,(1) 顺序结构,【例】 求两数之和。,显示结果：35,num220；,sumnum1+num2;,演示算法执行过程,输出sum;,算法的表示及三种基本结构,(2) 分支结构,【例】 输入三个数，输出其中的最大数。,x7;

11、,y12;,z10;,if(xy) maxx; else max y;,if (zmax) maxz;,输出max;,显示结果：12,演示算法执行过程,算法的表示及三种基本结构,(3) 循环结构,【例】求4个整数的和。,显示结果：60,演示算法执行过程,12,3,14,26,2,16,42,1,18,60,0,count4; /整数个数 sum0; /累加和的初值 while (count0) x输入一个整数; sumsum+x; countcount-1; 输出sum;,算 法 的 概 念,对同一个问题，可以有不同的解题方法和步骤。例如，求1+2+3+100，可以先进行1+2，再加3，再加4

12、，一直加到100，也可采取100+(1+99)+(2+98)+(49+51)+50100+50+491005050。还可以有其它的方法。当然，方法有优劣之分。有的方法只需进行很少的步骤，而有些方法则需要较多的步骤。一般说，希望采用方法简单，运算步骤少的方法。因此，为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。,常用算法介绍,解决的问题的种类与复杂程度各不相同决定了算法的多样性，但从其思想方法上可以将其归为以下几种：直接法、枚举法、递推法、递归法、回溯法等等。本节将介绍以下三种：,常用算法介绍, 直接法,直接法就是根据问题给出的条件直接求解，前面的很多例子都是这种

13、算法的运用。这里不再举例。,常用算法介绍, 枚举法,枚举法也称穷举法，基本思想是，在有限范围内列举所有可能的结果，找出其中符合要求的解。 枚举法适合求解的问题是：问题可能的答案是有限个且答案是可知的，但又难以用解析法描述。这种算法通常需要用循环结构来完成。,请看下例：,【例】 给定一个正整数，判断其非负整数立方根是否存在，若存在，输出该立方根。,常用算法介绍,算法如下：,分析：设某正整数为27，则非负整数立方根的取值范围为127，因此可在这一范围内对所有整数进行检测，满足立方根为27的就是所求整数。,【例】求非负整数立方根算法：,常用算法介绍,27,1,显示结果：3,演示算法执行过程,比较,c

14、*c*c,2,比较,c*c*c,3,比较,c*c*c,num27； c1；/立方根初值 while (cnum) 输出 “无整数立方根”;,常用算法介绍,【例】 判断一个正整数是否素数，给出相应结果。,分析：假设正整数num, 如果num不是2，需要检测它是否含有除1和它本身之外的其他因子，如果有，就不是素数。检测方法是在2num-1范围内逐个验证。,算法如下：,常用算法介绍,【例】 判断一个数是否为素数算法,#include void main() int num; cinnum; for(int i=2;inum;i+) if(num%i=0) break; if(i=num) coutn

15、um “是素数”； else coutnum “不是素数”； ,常用算法介绍, 递推法,递推算法是通过问题的一个或多个已知解，用同样的方法逐个推算出其他解，如数列问题以及一些近似计算问题等。通常也要借助于循环。,请看下例：,常用算法介绍,【例】 求n!,分析：n!=123n，因此可以从1开 始，由1!乘以2得到2!，再乘以3得到3!，以此推出n!。,假定n4，算法如下：,常用算法介绍,【例】 求n!算法：,显示结果：24,演示算法执行过程,1,2,4,比较,2,3,比较,6,4,比较,24,比较,5,factorial1; /阶乘初值 i2; n 4; while (i=n) factorialfactorial*i ; ii+1; 输出 factorial;,8.3 软件开发基础,软件开发不同于编写小程序，程序并不代表软件，软件包括程序和文档两部分。 应该把软件开发的全过程视为一项工程来处理，用工程的思想方法支持软件的开发，即软件工程。从而用