第3章3.3 算法和程序设计

3.3算法和程序设计3.3.1算法3.3.2程序设计语言3.3.3程序设计语言处理器23.4算法和数据结构3.3.1算法33.3算法和程序设计计算机求解问题的步骤(1)确定并理解问题；(2)寻找解决问题的方法与步骤，并将其表示成算法(Algorithm)；(3)使用某种程序设计语言描述该算法(编程),并进行调试；(4)运行程序，获得问题的解答；(5)进行评估，改进算法和程序43.3算法和程序设计1.什么是算法？53.3算法和程序设计算法是解决问题的方法与步骤63.3算法和程序设计3.算法的表示文字叙述流程图表示伪代码描述73.3算法和程序设计文字(自然语言)描述“比较Ａ与Ｂ的重量，若Ａ＝Ｂ，则Ｃ是伪造的；否则再比较Ａ与Ｃ的重量，若Ａ＝Ｃ，则Ｂ是伪造的；否则Ａ是伪造的。”缺点：容易产生歧义，很难“精确”地进行表达叙述冗长，很难清楚地表达算法的逻辑流程83.3算法和程序设计算法的流程图表示流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件流程图符号：比文字描述简明，但当算法比较复杂时，理解困难，容易产生错误端点符处理判断预定义功能原始数据放在数组A中；令i=1确定A[i]到A[n]中最小整数的位置,设为jA[i]和A[j]交换位置i=i+1i=n?结束开始用流程图表示选择排序算法93.3算法和程序设计将原始数据放在数组A中；设置i的初值为1，循环执行下列操作，直到i=n：{确定A[i]到A[n]中最小整数的位置，设为j；交换A[i]和[j]；i=i+1}使用伪代码描述“选择排序”算法使用伪代码描述算法伪代码(Pseudocode)是用来描述算法的一种语言，它既类似于自然语言，又使用与程序设计语言相似的方法描述算法优点：结构清晰，代码简单，可读性好，可以容易地以任何一种编程语言(Pascal,C,Java等)实现每个整数是A的一个元素：A[1],A[2],···,A[n]103.3算法和程序设计4.算法的分析113.3算法和程序设计算法分析的基本内容正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果简单性算法是否容易理解，是否容易验证其正确性，程序是否容易调试简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单时间复杂性(TimeComplexity)：当问题的规模n充分大时，运行该算法所需要的时间的数量级表示空间复杂性(SpaceComplexity)：除原始数据之外，额外占用的存储空间的大小123.3算法和程序设计关于算法的小结133.3算法和程序设计计算机中处处是算法！例1：Word程序如何在文档中查找用户指定的词语？例2：在Word文档的表格中如何将表格内容排序？例3：如何把一幅彩色图片转换为灰度(黑白)图片？例4：Windows如何在硬盘中找到用户指定的文件？例5：媒体播放器如何把MP3文件转换成动听的音乐？例6：搜索引擎如何在网中找到用户需要的网页？143.3算法和程序设计算法是计算机软件的灵魂计算机的通用性是因为它能运行各种各样的程序，而程序之所以能解决问题，是因为它所体现了正确的算法算法所解决的是一类问题而不是一个特定的问题，例如排序(sort)可以是表格内容的排序，也可以是文件夹中文件的排序，可以按数字或文字排序，也可以按日期排序，等等查找(search)，可以在文档中查找某个单词或在硬盘中查找某个文件，也可在Web上查找某个网页，等等开发计算机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上实现(即开发成为软件)153.3算法和程序设计计算机算法的4个特点目的：完成某个特定的信息处理任务必须满足的性质：①确定性：算法中每一步操作的含义必须清楚明确，无二义性②能行性：算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内③有穷性：算法在执行了有限步操作后必须结束④算法结束后至少产生一个输出（包括参量或状态的变化）163.3算法和程序设计3.3.2程序设计语言机器语言汇编语言高级程序设计语言173.3算法和程序设计什么是程序设计语言？什么是程序？程序是为了用计算机解决某个问题而采用程序设计语言编写的一个指令序列什么是程序设计语言？语言的目的是用于通信程序设计语言用于人与计算机之间的通信程序设计语言是由人使用但计算机可以理解的一种语言程序设计语言用于编制程序，表达需要计算机完成什么任务和怎样完成任务，然后交给计算机去完成183.3算法和程序设计程序设计语言填补了人与计算机交流的鸿沟计算机硬件仅仅知道0和1有问题需要计算机解决的人交流的鸿沟计算机硬件仅仅知道0和1有问题需要计算机解决的人程序设计语言193.3算法和程序设计计算机中使用多种“语言”程序设计语言：主要用于描述算法机器语言、汇编语言、高级语言数据描述语言：主要用于描述数据（文档、音乐、图形、图像、视频等）的规范、结构和文件格式HTML、XML、MIDI、MP3、OpenGL、JPEG、MPEG、······脚本语言：用于编写嵌入在文档中的程序的程序设计语言VBA、VBScript、JavaScript计算机通信语言（通信协议）：用于描述计算机-计算机之间的会话（请求-应答）的语法和语义HTTP、POP3、SMTP、FTP、Telnet、TCP、IP、······数据库语言：用于数据操作，如SQL语言······203.3算法和程序设计B87F01BB210203D8B81F042BC3（计算1055-(383+545)的5条机器指令）机器语言机器语言就是计算机的指令系统指令是使用二进制编码表示的用机器语言编程序,也就是直接使用二进制代码编写程序优点：可以直接被计算机执行缺点：记不住、难理解、效率低、不易维护不同的机器语言程序，相互不兼容现在已不直接用机器语言编制程序！操作码操作数(或操作数的地址)1条机器指令操作数地址操作码213.3算法和程序设计汇编语言用助记符号来表示机器指令中的操作符与操作数优点：操作数直接使用十进制程序相对容易理解缺点：大型程序难以开发依赖于具体计算机将383传送到AX寄存器将545传送到BX寄存器将BX内容加AX内容，结果在BX中将1055传送到AX寄存器将AX内容减BX内容，结果在AX寄存器中B87F01BB210203D8B81F042BC3（计算1055-(383+545)的5条机器指令）机器语言程序MOVAX383MOVBX545ADDBXAXMOVAX1055SUBAXBX汇编语言程序223.3算法和程序设计高级程序设计语言目的：克服汇编语言的缺陷，提高编程和维护的效率特点：接近人们日常使用的自然语言（主要是英语）容易理解、记忆和使用可在不同计算机上通用对使用的符号、词汇、语法和语义等各种语言成分都有严格的规定意义：使程序设计的难度降低，导致了计算机的发展进入新的阶段MOVAX383MOVBX545ADDBXAXMOVAX1055SUBAXBX汇编语言程序S=1055-(383+545)233.3算法和程序设计高级程序设计语言的发展50年代：Fortran，ALGOL60年代：COBOL语言，BASIC语言70年代：Pascal语言，C语言80年代：Ada语言，PROLOG语言，LISP语言90年代起：面向对象语言C++、JAVA、C#等243.3算法和程序设计FORTRAN语言FORTRAN是FORmulaTRANslation（公式翻译）的缩写词，它是一种主要用于数值计算的面向过程的程序设计语言。FORTRAN语言的特点是接近数学公式，简单易用目前最新的国际标准是FORTRAN2003253.3算法和程序设计BASIC和VisualBasic语言BASIC语言的特点是简单易学VisualBASIC(VB)语言是微软公司基于BASIC发展而来的一种程序设计语言，特点是：是一种可视化的、面向对象的、采用事件驱动方式的结构化高级程序设计语言具有高效率、简单易学及功能强大的特点可以高效、快速地开发Windows环境下功能强大、图形界面丰富的应用软件263.3算法和程序设计资料：VBA和VBScriptVBA（VisualBasicforApplication）VB的子集，包含在Office软件（如Word、Excel、Access、PowerPoint）中用途：扩展Office软件的功能特点：寄生于已有的应用程序（如Word），不需要另外的开发环境，也不能生成.exe文件，所开发出来的程序（称为“宏”）必须由它的宿主程序调用才能运行VBScript语言也是VB的子集，嵌入在HTML文档中使用所编写的脚本程序可以扩充网页的功能，例如：动态修改网页的内容和控制文档的展现检验用户的输入信息是否正确等273.3算法和程序设计Java语言由SUNMicrosystem公司于1995年发布的一种面向对象的、用于网络环境的程序设计语言基本特征：适用于网络分布环境具有一定的平台独立性安全性和稳定性好应用举例：从网络下载到浏览器中运行的跨平台小程序Javaapplets便携式数字设备(如手机)中的应用程序283.3算法和程序设计C语言和C++语言C语言是1972～1973年间由AT＆T公司Bell实验室开发而成C语言兼有高级语言的优点和汇编语言的效率，有效地处理了简洁性和实用性、可移植性和高效性之间的矛盾C++语言以C语言为基础发展而成，既有数据抽象和面向对象能力，运行性能高，又能与C语言兼容，因而C++语言迅速流行，成为当前面向对象程序设计的主流语言293.3算法和程序设计3.3.3程序设计语言处理系统303.3算法和程序设计程序设计语言的翻译程序把甲语言编写的程序翻译为等价的乙语言编写的程序。其中甲语言程序称为源程序，乙语言程序称为目标程序翻译程序源程序目标程序常用的有下列几种：汇编程序(汇编器)汇编语言源程序机器语言目标程序编译程序(编译器)高级语言源程序机器语言或汇编语言目标程序解释程序(解释器)高级语言源程序边解释边执行，不产生目标程序313.3算法和程序设计编译程序与解释程序的区别解释：解释器直接解释并且执行源语言程序，不产生目标程序（相当于“口译”）编译：把源程序编译为机器语言目标程序后，再由计算机运行（相当于“笔译”）源程序目标程序编译器计算机编译方式计算机源程序解释器解释方式BASIC、VisualBasic、VBScript、Java、JavaScript等都是解释执行的语言C、C++等都是需要编译的语言323.3算法和程序设计编译程序的处理过程源程序目标程序可执行代码程序库编译程序链接程序.c.h.obj.exe1.编辑2.编译3.链接4.运行