第6章 算法与程序设计.docx
《第6章 算法与程序设计.docx》由会员分享,可在线阅读,更多相关《第6章 算法与程序设计.docx(16页珍藏版)》请在冰点文库上搜索。
第6章算法与程序设计
教 案
授课时间
11月4日至11月10日
课时数
3+1
授课方式
理论课☑讨论课□习题课□实验课□上机课☑技能课□其他□
授课单元
第六章:
算法与程序设计
目的
与
要求
1.理解算法的定义。
2.掌握算法的基本特征。
3.了解流程图、N-S图等算法表示方法。
4.掌握结构化程序设计方法的三种基本结构。
重点
与
难点
重点:
掌握算法的基本特征;掌握结构化程序设计方法。
难点:
掌握选择结构、循环结构的特点。
主
要
内
容
1.算法定义、基本特征、表示方法。
2.常用程序设计语言简介。
3.常用程序设计方法简介;结构化程序设计方法中三种基本结构。
教学方法手段(教具)
使用多媒体投影与国家一级考试模拟系统辅助教学。
采用案例教学和任务驱动等教学法授课。
参考资料
《计算机基础及应用》机械工业出版社郑坚主编
《等级考试学习笔记---一级office》人民邮电出版社李琳主编
思考题、
作业
作业:
P164一
操作题:
在VB中设计求5!
的简单程序。
讲 稿
第六章算法与程序设计
[旧课复习]:
复习内容:
1.PowerPoint幻灯片的基本制作方法
2.PowerPoint幻灯片的动画设计
复习目的:
加强学生熟练掌握PowerPoint基本操作
复习时长:
大约5分钟
[新课导入]:
导入方式:
展示一个自制应用程序
导入目的:
让学生初步了解程序设计的应用理念
导入时长:
大约5分钟
[新课讲授]:
重点:
掌握算法的基本特征;掌握结构化程序设计方法。
难点:
掌握选择结构、循环结构的特点。
方法:
运用多媒体辅助教学,采用案例教学和任务驱动等教学法。
6.1计算机求解问题的方法
(1)界定问题。
(2)分析问题。
(3)建模。
(4)分析模型建立算法。
6.2算法及算法的描述
6.2.1算法的定义
算法(Algorithm)是指完成某一特定任务所需要的具体方法和步骤,是有穷规则的集合。
6.2.2算法的基本特征
算法是程序设计的“灵魂”,算法+数据结构=程序。
算法独立于任何具体的程序设计语言,一个算法可以用多种程序设计语言来实现。
算法具有以下基本特征。
(1)输入:
一个算法有0个或多个输入,用以表征算法开始之前运算对象的初始情况。
(2)输出:
一个算法必须有一个或多个输出,输出是算法计算的结果,没有任何输出的程序是没有意义的。
(3)确定性:
算法对每一步骤的描述必须确切而无歧义,以保证算法的实际执行结果精确地符合要求或期望。
(4)有穷性:
算法必须在有穷步骤内完成任务,并且每一步骤都可以在有穷时间内完成。
(5)可行性:
算法中描述的操作都是可以通过已经实现的基本运算,执行有限次数来实现。
6.2.3算法的评价
对于算法的评价有两个基本标准:
时间复杂度和空间复杂度。
所谓时间复杂度,即执行这个算法需要多少时间。
所谓空间复杂度,即执行这个算法需要占用多少资源(可以理解为占用了多少计算机存储单元)。
6.2.4算法的描述
计算机算法无非是将人脑抽象出的模型程序化,而求解问题的关键还是在于人类本身的思维。
算法的描述是基于一种形式地表达
6.2.5算法的表示
常用的描述工具有:
流程图、N-S图、PAD图、伪码等。
1.流程图
流程图是算法表达最常用的一种方法。
流程图是一种用程序框、流程线及文字说明来表示算法的图形。
在程序框图中,一个或几个程序框的组合表示算法中的一个步骤,带有方向箭头的流程线将程序框连接起来,表示算法步骤的执行顺序。
流程图中常用的元件
起止框表示一个算法的起始和结束,是任何流程图不可少的
输入、输出框表示一个算法输入和输出的信息,可用在算法中任何需要输入、输出的位置
处理框赋值、计算。
算法中处理数据需要的算式、公式等分别写在不同的用以处理数据的处理框内。
判断框判断某一条件是否成立,成立时在出口处标明“是”或“Y”;不成立时标明“否”或“N”
流程线连接程序框,带有控制方向
连接点连接程序框的两部分
2.伪代码
伪代码(pseudocode)也叫虚拟代码,是一种由自然语言和没有限定的多种编程语言元素混合而成的。
介于自然语言和计算机语言之间。
6.3程序设计语言及程序设计
6.3.1程序设计语言
程序设计语言是指一组由关键字和语法规则构成的,并且可以被计算机所处理和执行的指令规则。
其基本成分主要包括以下4种。
(1)数据成分。
用以描述程序中所涉及的数据,如常量、变量、各种数据类型等。
(2)运算成分。
用以描述程序中所包含的运算,包含运算符号和运算规则,有算术运算、逻辑运算、关系运算等。
(3)控制成分。
用以描述程序中的控制构造,如顺序结构、选择结构和循环结构。
(4)传输成分。
用以描述程序中数据的传输。
在程序设计语言的发展中,经历了如下几个阶段。
1.机器语言
机器语言是直接用二进制代码指令表达的计算机语言。
。
2.汇编语言
汇编语言比机器语言直观,它的每一条符号指令与相应的机器指令有对应关系,同时又增加了一些宏、符号地址等功能。
机器语言和汇编语言同属于低级语言。
3.高级语言
高级语言提供给程序员的指令更像人类自然语言,它为计算机应用的普及起到了重要作用。
例如,高级语言中的关键字Print或Write代表的命令,能够代替数行的汇编语言操作码或者冗长的机器语言的0、1指令序列。
用高级程序设计语言编程直观、方便,但计算机最终执行的还是二进制表示的机器指令,这中间需要编译程序或解释程序来做翻译工作。
高级程序设计语言不再与具体的计算机硬件相对应,同一高级程序设计语言,只要给出不同的编译程序或解释程序,就可以用在不同类型的计算机上。
这就是高级程序设计语言的通用性。
高级语言又分为过程性语言、面向对象语言和专用语言。
(1)过程性语言
过程性编程语言适合于那些结构化设计的算法。
用过程性语言编写的程序有一个起点和一个终点,程序从起点到终点执行的流程是直线型的。
BASIC、COBOL、FORTRAN、C、Pascal都属于过程性语言。
(2)面向对象语言
面向对象语言是建立在用对象编程方法的基础上的。
程序被看成是正在进行通信的若干对象的集合,程序设计就是定义对象、建立对象间的通信关系。
面向对象的程序设计语言提供了类库,类库中定义了包括窗口类在内的各种各样的类供程序使用,从而使大型软件的开发变得容易。
面向对象的程序设计语言有VisualBasic、C++、Java、Delphi等。
(3)专用语言
专用语言是为特殊应用而设计的语言。
通常有特殊的语法形式,面对特定的问题,输入结构及词汇表与该问题的范围密切相关。
专用语言针对特殊用途设计,一般应用面窄,翻译过程简便、高效,但与通用语言相比,可移植性和可维护性差。
4.第四代编程语言—4GL(Fourth-GenerationLanguage)
使用广泛的第四代语言是数据库查询语言,它支持用户以复杂的方式操作数据库。
流行的结构化查询语言(StructuredQueryLanguage,SQL)支持数据库的定义和操作,功能强大,简单易学。
6.3.2程序设计过程
程序设计过程。
1.编写源程序
用合适的编辑软件进行相应语言源程序的书写。
2.编译/解释
编译就是用相应的编译器对源程序进行编译,产生计算机能够识别的目标文件。
3.链接
经过编译产生的目标文件与程序执行所需要的相关函数库。
4.发布
使其可以脱离编程环境独立运行。
6.4程序设计方法
在此我们将以VisualBasic(简称VB)开发工具作为示范用例及平台。
VB6.0又分三个不同版本:
(1)普及版(Learning):
适合初学者及教学使用。
(2)专业版(Professional):
适合专业程序开发人员使用。
(3)企业版(Enterprise):
适合企业用户开发大型客户服务器应用程序。
图6-4顺序结构
6.4.1结构化程序设计方法
结构化程序设计的主要思想是采用自顶向下、逐步细化的程序设计方法,同时严格使用3种基本控制结构来构造程序。
3种基本控制结构是指顺序结构、选择结构和循环结构。
计算机科学家Bohm和Jacopini证明了任何简单或复杂的算法都可以由这3种基本结构组合而成。
1.顺序结构
顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的。
其流程如图6-4所示。
2.选择结构
选择结构也称为分支结构,根据所列条件的正确与否选择执行路径,如图6-5所示。
VB中分支结构的使用形式:
(1)单行结构条件语句If…Then…Else语句。
语法格式:
If<条件>Then[<语句序列1>][Else<语句序列2>]
说明:
①条件可以是关系表达式、布尔表达式或数值表达式。
如果以数值表达式作条件,则非0值为真,0为假。
②如果没有Else子句,则[<语句序列1>]为必要参数,在<条件>为True时执行。
【例6-1】输入三个数,按照从大到小的顺序排序,程序运行结果如图6-6所示。
代码如下:
PrivateSubCommand1_Click()
DimaAsDouble,bAsDouble,cAsDouble,pAsDouble
图6-6三个数从大到小排序
a=Val(Trim(Text1.Text))
b=Val(Trim(Text2.Text))
c=Val(Trim(Text3.Text))
Ifaa=b:
b=p
Ifaa=c:
c=p
Ifbb=c:
c=p
Label5.Caption="从大到小是:
"&a&","&b&","&c
EndSub
PrivateSubCommand2_Click()
UnloadMe
EndSub
(2)If语句的嵌套:
即大的分支结构中完整包含小的分支结构。
语法格式:
If<条件1>Then
[语句列1]
Else
If<条件2>Then
[语句列2]
Else
[语句列3]
…
EndIf
EndIf
说明:
①如果If语句中[语句列1]或[语句列2]本身又是一个If语句,则称为If语句的嵌套。
②Else与If配套原则为,就近且未配对,不能出现交错结构。
【例6-2】已知如下分段函数,请输入x的值,输出y值,程序运行结果如图6-7所示。
代码如下:
图6-7分段函数
PrivateSubCommand1_Click()
DimxAsSingle,yAsSingle
x=Val(Text1.Text)
Ifx>=0Then
Ifx=0Then
y=0
Else
y=1
EndIf
Else
y=-1
EndIf
Text2.Text=Str(y)
EndSub
PrivateSubText1_Change()
Text2.Text=""
EndSub
(4)多分支条件选择语句SelectCase。
特点:
与If语句的嵌套格式ElseIf执行方式相似,<测试条件>从上至下匹配到第1个正确的[Case<表达式i>,执行语句列i后退出分支结构,否则执行CaseElse部分并退出,如果没有CaseElse部分,则不作任何操作就结束选择。
语法格式为:
SelectCase<测试条件>
[Case<表达式1>
[<语句列1>]
[Case<表达式2>
[<语句列2>]
…
[CaseElse
[<其他语句列>]]
EndSelect
说明:
①测试条件为必要条件,可以是任何数值表达式或字符串表达式。
②在Case子句中,表达式为必要参数,用来测试其中是否有值与测试条件相匹配。
其中表达式列表的形式有:
表达式To表达式,如Case1000To2000;Is关系运算表达式,如CaseIs<3000;当使用多个表达式列表时,表达式与表达式之间要用逗号“,”隔开。
③<语句列>是可选项,是一条或多条语句,当表达式中有值与<测试条件>相匹配时执行。
④CaseElse子句用于指明其他语句列,当测试条件和所有的Case子句<表达式>中的值都不匹配时,则会执行这些语句。
【例6-3】输入百分制成绩,输出对应的五分制等级,程序运行结果如图6-9所示。
代码:
图6-9程序界面
PrivateSubCommand1_Click()
DimsAsInteger,pAsString
s=Val(Text1)
SelectCases
CaseIs>=90
p="A"
CaseIs>=80
p="B"
CaseIs>=70
p="C"
CaseIs>=60
p="D"
CaseElse
p="E"
EndSelect
Text2=p
EndSub
3.循环结构
循环结构可以重复执行一条或多条指令,直到满足条件退出循环。
循环结构主要有以下两种。
(1)当型(DOWHILE型)循环结构,当条件P满足时,反复执行。
一旦条件P不满足时就不再执行。
(2)直到型(UNTIL型)循环结构,先执行,然后判断条件P是否满足,如条件P不满足,则反复执行,直到某一时刻,条件P满足则停止循环。
图6-10循环结构
VB提供了3种不同格式的循环:
当循环:
While…Wend;
Do循环:
Do…loop;
计数循环:
For…Next,ForEach…Next
(1)While…Wend循环。
语法格式:
While条件
循环体
Wend
说明:
①条件可以是各种表达式,当条件的值为数值时,则非0的数为真,0为假。
②在循环体中一定要有修改循环条件的语句,使条件为False,跳出循环。
(2)Do…Loop循环。
VB中循环语句有前测试型Do…Loop循环和后测试型Do…Loop循环。
在此类循环中首先要在循环体外给循环变量赋初值,在循环体内有修改循环条件的语句,使条件为False,跳出循环。
①前测试型Do…Loop循环
a.前测试当型循环b.前测试直到型循环
语法格式:
DoWhile条件DoUntil条件
循环体循环体
LoopLoop
前测试当型循环先判断循环条件是否为真,若为真,则执行循环体,否则不执行。
前测试直到型循环刚好与当型相反,条件为真时结束循环。
可在此循环中任何位置放置任意个ExitDo语句,可以随时跳出循环,但只能跳出它所在的那层循环。
【例6-4】输入一个自然数m,求1到m的和,如图6-12所示。
代码如下:
PrivateSubCommand1_Click()
DimsAsInteger,nAsInteger
图6-12求和计算
m=Val(Text1.Text)
n=1
s=0
DoWhilen<=m
s=s+n
n=n+1
Loop
Label2.Caption="1到"&m&"的加和为:
"&s
EndSub
②后测试型Do…Loop循环
特点:
先执行循环体,再判断条件,根据条件真假决定是否继续执行循环体。
因此,循环体至少会被执行一次。
a.后测试当型循环b.后测试直到型循环
语法格式:
DoDo
循环体循环体
LoopWhile条件LoopUntil条件
(3)For…Next语句。
不知道循环次数的时候宜用Do…Loop循环;若知道循环次数,最好用For…Next循环。
语法格式:
For<循环变量>=初值To终值[Step步长]
循环体
[ExitFor]
Next循环变量[,循环变量]
说明:
①“循环变量”是循环次数的计数器,初值、终值、步长可以是数值型的常量、变量或表达式(若不为整数,VB自动取整),但变量不能是数组元素。
变量、初值、终值必不可少,但步长可省略,则表示步长为1。
②步长可以是正数或负数;若步长>0,则初值<=终值;步长<0,则初值>=终值;循环次数=(终值-初值)/步长+1。
③循环执行的过程如下:
循环变量在初值与终值之间,则执行循环体,加Step步长后继续。
④可在循环体中放任意个ExitFor强制退出循环。
⑤For、Next必须成对出现,且For语句必须在Next之前。
【例6-5】求5!
,程序运行结果如图6-14所示。
图6-145!
的运行结果
PrivateSubCommand1_Click()
t=1
Fori=1To5
t=t*i
Nexti
Text1=t
EndSub
(4)循环嵌套及算法举例。
循环嵌套:
指一个循环体中完整地包含另一个循环。
Do…Loop几类循环和For…Next可互相嵌套。
在使用循环嵌套时,要注意以下两个问题:
其一,内外循环不应交叉;其二,内外循环变量名不应相同。
以上3种基本控制结构(顺序结构、选择结构、循环结构)有以下共同的特点。
①只有一个入口和一个出口。
②结构内的每一部分都有机会被执行到,也就是说,每一个框都应当有一条从入口到出口的路径通过它。
③结构内没有死循环(无限循环)。
1971年,尼克劳斯•沃斯发布的PASCAL语言是第一个系统地体现了迪杰斯特拉定义的结构化程序设计概念的语言。
同一时代产生的程序设计语言BASIC、C语言等也是典型的结构化程序设计语言。
[教学总结]:
本章主要学习了算法的定义及特征,了解结构化程序设计方法的三种基本结构。
[作业布置]:
作业:
P164一
操作题:
在VB中设计求5!
的简单程序。
[教学后记]: