第6章 算法与程序设计.docx

1、第6章 算法与程序设计教案授课时间11 月 4 日 至 11 月 10日课时数3+1授课方式理论课 讨论课 习题课 实验课 上机课 技能课 其他授课单元第六章：算法与程序设计目的与要求1.理解算法的定义。2.掌握算法的基本特征。3.了解流程图、N-S图等算法表示方法。4.掌握结构化程序设计方法的三种基本结构。重点与难点重点：掌握算法的基本特征；掌握结构化程序设计方法。难点：掌握选择结构、循环结构的特点。主要内容1.算法定义、基本特征、表示方法。2.常用程序设计语言简介。3.常用程序设计方法简介；结构化程序设计方法中三种基本结构。教学方法手段（教具）使用多媒体投影与国家一级考试模拟系统辅助教学。

2、采用案例教学和任务驱动等教学法授课。参考资料计算机基础及应用 机械工业出版社 郑坚主编等级考试学习笔记-一级office人民邮电出版社 李琳主编思考题、作业作业：P164 一操作题：在VB中设计求5！的简单程序。讲稿第六章 算法与程序设计旧课复习：复习内容：1. PowerPoint幻灯片的基本制作方法2.PowerPoint 幻灯片的动画设计复习目的：加强学生熟练掌握PowerPoint基本操作复习时长：大约5分钟新课导入：导入方式：展示一个自制应用程序导入目的：让学生初步了解程序设计的应用理念导入时长：大约5分钟新课讲授：重点：掌握算法的基本特征；掌握结构化程序设计方法。难点：掌握选择结构

3、、循环结构的特点。方法：运用多媒体辅助教学，采用案例教学和任务驱动等教学法。6.1 计算机求解问题的方法（1）界定问题。（2）分析问题。（3）建模。（4）分析模型建立算法。6.2 算法及算法的描述6.2.1 算法的定义算法（Algorithm）是指完成某一特定任务所需要的具体方法和步骤，是有穷规则的集合。6.2.2 算法的基本特征算法是程序设计的“灵魂”，算法+数据结构=程序。算法独立于任何具体的程序设计语言，一个算法可以用多种程序设计语言来实现。算法具有以下基本特征。（1）输入：一个算法有0个或多个输入，用以表征算法开始之前运算对象的初始情况。（2）输出：一个算法必须有一个或多个输出，输出是

4、算法计算的结果，没有任何输出的程序是没有意义的。（3）确定性：算法对每一步骤的描述必须确切而无歧义，以保证算法的实际执行结果精确地符合要求或期望。（4）有穷性：算法必须在有穷步骤内完成任务，并且每一步骤都可以在有穷时间内完成。（5）可行性：算法中描述的操作都是可以通过已经实现的基本运算，执行有限次数来实现。6.2.3 算法的评价对于算法的评价有两个基本标准：时间复杂度和空间复杂度。所谓时间复杂度，即执行这个算法需要多少时间。所谓空间复杂度，即执行这个算法需要占用多少资源（可以理解为占用了多少计算机存储单元）。6.2.4 算法的描述计算机算法无非是将人脑抽象出的模型程序化，而求解问题的关键还是在

5、于人类本身的思维。算法的描述是基于一种形式地表达6.2.5 算法的表示常用的描述工具有：流程图、N-S图、PAD图、伪码等。1流程图流程图是算法表达最常用的一种方法。流程图是一种用程序框、流程线及文字说明来表示算法的图形。在程序框图中，一个或几个程序框的组合表示算法中的一个步骤，带有方向箭头的流程线将程序框连接起来，表示算法步骤的执行顺序。流程图中常用的元件起止框 表示一个算法的起始和结束，是任何流程图不可少的输入、输出框表示一个算法输入和输出的信息，可用在算法中任何需要输入、输出的位置 处理框 赋值、计算。算法中处理数据需要的算式、公式等分别写在不同的用以处理数据的处理框内。 判断框 判断某

6、一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时标明“否”或“N” 流程线 连接程序框，带有控制方向 连接点 连接程序框的两部分2伪代码伪代码（pseudo code）也叫虚拟代码，是一种由自然语言和没有限定的多种编程语言元素混合而成的。介于自然语言和计算机语言之间。6.3 程序设计语言及程序设计6.3.1 程序设计语言程序设计语言是指一组由关键字和语法规则构成的，并且可以被计算机所处理和执行的指令规则。其基本成分主要包括以下4种。（1）数据成分。用以描述程序中所涉及的数据，如常量、变量、各种数据类型等。（2）运算成分。用以描述程序中所包含的运算，包含运算符号和运算规则，有算术运算、

7、逻辑运算、关系运算等。（3）控制成分。用以描述程序中的控制构造，如顺序结构、选择结构和循环结构。（4）传输成分。用以描述程序中数据的传输。在程序设计语言的发展中，经历了如下几个阶段。1机器语言机器语言是直接用二进制代码指令表达的计算机语言。2汇编语言汇编语言比机器语言直观，它的每一条符号指令与相应的机器指令有对应关系，同时又增加了一些宏、符号地址等功能。机器语言和汇编语言同属于低级语言。3高级语言高级语言提供给程序员的指令更像人类自然语言，它为计算机应用的普及起到了重要作用。例如，高级语言中的关键字Print或Write代表的命令，能够代替数行的汇编语言操作码或者冗长的机器语言的0、1指令序列

8、。用高级程序设计语言编程直观、方便，但计算机最终执行的还是二进制表示的机器指令，这中间需要编译程序或解释程序来做翻译工作。高级程序设计语言不再与具体的计算机硬件相对应，同一高级程序设计语言，只要给出不同的编译程序或解释程序，就可以用在不同类型的计算机上。这就是高级程序设计语言的通用性。高级语言又分为过程性语言、面向对象语言和专用语言。（1）过程性语言过程性编程语言适合于那些结构化设计的算法。用过程性语言编写的程序有一个起点和一个终点，程序从起点到终点执行的流程是直线型的。BASIC、COBOL、FORTRAN、C、Pascal都属于过程性语言。（2）面向对象语言面向对象语言是建立在用对象编程方

9、法的基础上的。程序被看成是正在进行通信的若干对象的集合，程序设计就是定义对象、建立对象间的通信关系。面向对象的程序设计语言提供了类库，类库中定义了包括窗口类在内的各种各样的类供程序使用，从而使大型软件的开发变得容易。面向对象的程序设计语言有Visual Basic、C+、Java、Delphi等。 （3）专用语言专用语言是为特殊应用而设计的语言。通常有特殊的语法形式，面对特定的问题，输入结构及词汇表与该问题的范围密切相关。专用语言针对特殊用途设计，一般应用面窄，翻译过程简便、高效，但与通用语言相比，可移植性和可维护性差。4第四代编程语言4GL（Fourth-Generation Languag

10、e）使用广泛的第四代语言是数据库查询语言，它支持用户以复杂的方式操作数据库。流行的结构化查询语言（Structured Query Language，SQL）支持数据库的定义和操作，功能强大，简单易学。6.3.2 程序设计过程 程序设计过程。1编写源程序用合适的编辑软件进行相应语言源程序的书写。2编译/解释编译就是用相应的编译器对源程序进行编译，产生计算机能够识别的目标文件。3链接经过编译产生的目标文件与程序执行所需要的相关函数库。4发布使其可以脱离编程环境独立运行。6.4 程序设计方法在此我们将以Visual Basic（简称VB）开发工具作为示范用例及平台。VB 6.0又分三个不同版本：（

11、1）普及版（Learning）：适合初学者及教学使用。（2）专业版（Professional）：适合专业程序开发人员使用。（3）企业版（Enterprise）：适合企业用户开发大型客户服务器应用程序。图6-4 顺序结构6.4.1 结构化程序设计方法结构化程序设计的主要思想是采用自顶向下、逐步细化的程序设计方法，同时严格使用3种基本控制结构来构造程序。3种基本控制结构是指顺序结构、选择结构和循环结构。计算机科学家Bohm和Jacopini证明了任何简单或复杂的算法都可以由这3种基本结构组合而成。1顺序结构顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的。其流程如图6-4所示。2选择结构选

12、择结构也称为分支结构，根据所列条件的正确与否选择执行路径，如图6-5所示。VB中分支结构的使用形式：（1）单行结构条件语句IfThenElse 语句。语法格式：If Then Else 说明： 条件可以是关系表达式、布尔表达式或数值表达式。如果以数值表达式作条件，则非0值为真，0为假。 如果没有Else子句，则为必要参数，在 为True时执行。【例6-1】 输入三个数，按照从大到小的顺序排序，程序运行结果如图6-6所示。代码如下：Private Sub Command1_Click() Dim a As Double, b As Double, c As Double, p As Double

13、图6-6 三个数从大到小排序 a = Val(Trim(Text1.Text) b = Val(Trim(Text2.Text) c = Val(Trim(Text3.Text) If a b Then p = a: a = b: b = p If a c Then p = a: a = c: c = p If b c Then p = b: b = c: c = p Label5.Caption = 从大到小是： & a & , & b & , & c End SubPrivate Sub Command2_Click() Unload MeEnd Sub（2）If语句的嵌套：即大的分支结构

14、中完整包含小的分支结构。语法格式：If Then 语句列1ElseIf Then 语句列2Else 语句列3 End IfEnd If说明： 如果If语句中语句列1或语句列2本身又是一个If语句，则称为If语句的嵌套。 Else与If配套原则为，就近且未配对，不能出现交错结构。【例6-2】 已知如下分段函数，请输入x的值，输出y值，程序运行结果如图6-7所示。 代码如下：图6-7 分段函数Private Sub Command1_Click() Dim x As Single, y As Single x = Val(Text1.Text) If x = 0 Then If x = 0 The

15、n y = 0 Else y = 1 End If Else y = 1 End If Text2.Text = Str(y)End SubPrivate Sub Text1_Change() Text2.Text = End Sub （4）多分支条件选择语句Select Case。特点：与If语句的嵌套格式ElseIf执行方式相似，从上至下匹配到第1个正确的Case ，执行语句列i后退出分支结构，否则执行Case Else部分并退出，如果没有Case Else部分，则不作任何操作就结束选择。语法格式为：Select Case Case Case Case Else End Select说明：

16、 测试条件为必要条件，可以是任何数值表达式或字符串表达式。 在Case子句中，表达式为必要参数，用来测试其中是否有值与测试条件相匹配。其中表达式列表的形式有：表达式To表达式，如Case 1000 To 2000；Is 关系运算表达式，如Case Is 3000；当使用多个表达式列表时，表达式与表达式之间要用逗号“，”隔开。 是可选项，是一条或多条语句，当表达式中有值与相匹配时执行。 Case Else子句用于指明其他语句列，当测试条件和所有的Case子句中的值都不匹配时，则会执行这些语句。【例6-3】 输入百分制成绩，输出对应的五分制等级，程序运行结果如图 6-9所示。代码：图6-9 程序界

17、面Private Sub Command1_Click() Dim s As Integer, p As String s = Val(Text1) Select Case s Case Is = 90 p = A Case Is = 80 p = B Case Is = 70 p = C Case Is = 60 p = D Case Else p = E End Select Text2 = pEnd Sub3循环结构循环结构可以重复执行一条或多条指令，直到满足条件退出循环。循环结构主要有以下两种。（1）当型（DO WHILE型）循环结构，当条件P满足时，反复执行。一旦条件P不满足时就不再

18、执行。（2）直到型（UNTIL型）循环结构，先执行，然后判断条件P是否满足，如条件P不满足，则反复执行，直到某一时刻，条件P满足则停止循环。图6-10 循环结构VB提供了3种不同格式的循环：当循环：WhileWend；Do循环：Doloop；计数循环：ForNext，For EachNext（1）WhileWend循环。语法格式：While 条件 循环体 Wend 说明： 条件可以是各种表达式，当条件的值为数值时，则非0的数为真，0为假。 在循环体中一定要有修改循环条件的语句，使条件为False，跳出循环。（2）Do Loop循环。VB中循环语句有前测试型DoLoop循环和后测试型DoLoop

19、循环。在此类循环中首先要在循环体外给循环变量赋初值，在循环体内有修改循环条件的语句，使条件为False，跳出循环。 前测试型Do Loop循环a前测试当型循环 b前测试直到型循环语法格式：Do While 条件 Do Until 条件 循环体 循环体 Loop Loop 前测试当型循环先判断循环条件是否为真，若为真，则执行循环体，否则不执行。前测试直到型循环刚好与当型相反，条件为真时结束循环。可在此循环中任何位置放置任意个Exit Do语句，可以随时跳出循环，但只能跳出它所在的那层循环。【例6-4】 输入一个自然数m，求1到m的和，如图6-12所示。代码如下： Private Sub Comm

20、and1_Click() Dim s As Integer, n As Integer图6-12 求和计算 m = Val(Text1.Text) n = 1 s = 0 Do While n = m s = s + n n = n + 1 Loop Label2.Caption = 1到 & m & 的加和为： & sEnd Sub 后测试型DoLoop循环特点：先执行循环体，再判断条件，根据条件真假决定是否继续执行循环体。因此，循环体至少会被执行一次。a后测试当型循环 b后测试直到型循环语法格式：Do Do 循环体 循环体 Loop While条件 Loop Until条件（3）ForNe

21、xt语句。不知道循环次数的时候宜用DoLoop循环；若知道循环次数，最好用ForNext循环。语法格式：For =初值 To 终值 Step 步长 循环体 Exit For Next 循环变量,循环变量说明：“循环变量”是循环次数的计数器，初值、终值、步长可以是数值型的常量、变量或表达式（若不为整数，VB自动取整），但变量不能是数组元素。变量、初值、终值必不可少，但步长可省略，则表示步长为1。 步长可以是正数或负数；若步长0，则初值=终值；步长=终值；循环次数=(终值-初值)/步长+1。 循环执行的过程如下：循环变量在初值与终值之间，则执行循环体，加Step 步长后继续。 可在循环体中放任意个

22、Exit For 强制退出循环。 For、Next必须成对出现，且For语句必须在Next之前。【例6-5】 求5！，程序运行结果如图6-14所示。图 6-14 5！的运行结果Private Sub Command1_Click()t = 1For i = 1 To 5 t = t * iNext iText1 = tEnd Sub（4）循环嵌套及算法举例。循环嵌套：指一个循环体中完整地包含另一个循环。DoLoop几类循环和For Next可互相嵌套。在使用循环嵌套时，要注意以下两个问题：其一，内外循环不应交叉；其二，内外循环变量名不应相同。以上3种基本控制结构（顺序结构、选择结构、循环结构）有以下共同的特点。 只有一个入口和一个出口。 结构内的每一部分都有机会被执行到，也就是说，每一个框都应当有一条从入口到出口的路径通过它。 结构内没有死循环（无限循环）。1971年，尼克劳斯沃斯发布的PASCAL语言是第一个系统地体现了迪杰斯特拉定义的结构化程序设计概念的语言。同一时代产生的程序设计语言BASIC、C语言等也是典型的结构化程序设计语言。教学总结：本章主要学习了算法的定义及特征，了解结构化程序设计方法的三种基本结构。 作业布置：作业：P164 一操作题：在VB中设计求5！的简单程序。教学后记：