算法和程序设计

3.3算法和程序设计3.3.1

算法3.3.2

程序设计语言3.3.3程序设计语言处理器3.3.1算法计算机求解问题的步骤(1)确定并理解问题；(2)寻找解决问题的方法与步骤，并将其表示成算法(Algorithm)；(3)使用某种程序设计语言描述该算法(编程),并编译成目标程序和进行调试；(4)运行程序，获得问题的解答；(5)进行评估，改进算法和程序1.什么是算法？算法是解决问题的方法与步骤例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？分析：方法明确而有序按提供的条件进行操作任何人均可仿照进行(共享智能)开始C是伪币B是伪币A是伪币A＝B？A＝C？是否否是ABC关于算法的三方面问题如何确定算法（算法设计）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？2.算法设计举例典型问题：如何对数据进行排序问题：任给一组(n个)整数，将它们从小到大进行排序“选择排序”算法的思路：①从所有整数中选一个最小数，作为已排序的第一个数②从剩下未排序整数中选最小的数，添加到已排序整数的后面③反复执行步骤②，直到所有整数都处理完毕“选择排序”算法举例2345789第6次循环后，排序结束2937845与首元素交换，第1次循环结束4937825数组的初态，全部是未排序元素4937825在未排序元素中确定最小数位置2397845与首元素交换，第2次循环结束2937845在未排序元素中确定最小数位置2347895与首元素交换，第3次循环结束2397845在未排序元素中确定最小数位置3.算法的表示文字叙述流程图表示伪代码描述文字(自然语言)描述“比较Ａ与Ｂ的重量，若Ａ＝Ｂ，则Ｃ是伪造的；否则再比较Ａ与Ｃ的重量，若Ａ＝Ｃ，则Ｂ是伪造的；否则Ａ是伪造的。”缺点：容易产生歧义，很难“精确”地进行表达叙述冗长，很难清楚地表达算法的逻辑流程算法的流程图表示流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件流程图符号：比文字描述简明，但当算法比较复杂时，理解困难，容易产生错误端点符处理判断预定义功能原始数据放在数组A中；令i=1确定A[i]到A[n]中最小整数的位置,设为jA[i]和A[j]交换位置i=i+1i=n?结束开始用流程图表示选择排序算法将原始数据放在数组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]4.算法的分析算法分析的基本内容正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果简单性算法是否容易理解，是否容易验证其正确性，程序是否容易调试简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单时间复杂性(TimeComplexity)

：当问题的规模n充分大时，运行该算法所需要的时间的数量级表示空间复杂性(SpaceComplexity)：除原始数据之外，额外占用的存储空间的大小选讲：

选择排序算法的时间复杂性假设参加排序的整数有n个（1）比较操作的次数： 在第i趟排序中选出最小整数时，需做n-i次比较操作， 因此，总的比较操作次数为：n(n-1)/2=(n2-n)/2（2）移动操作的次数： 最好情况(原始数据已经排序)时，移动次数为0

最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3次传送)，总的移动次数取最大值为：3(n-1)所以，直接选择排序的时间复杂性为O(n2)设置i的初值为1，循环执行下列操作，直到I=n：{确定A[i]到A[n]中最小的整数元素的位置，设为j；交换A[i]和[j]；i=i+1}关于算法的小结计算机中处处是算法！例1：Word程序如何在文档中查找用户指定的词语？例2：在Word文档的表格中如何将表格内容排序？例3：如何把一幅彩色图片转换为灰度(黑白)图片？例4：Windows如何在硬盘中找到用户指定的文件？例5：媒体播放器如何把MP3文件转换成动听的音乐？例6：搜索引擎如何在WWW网中找到用户需要的网页？算法是计算机软件的灵魂计算机的通用性是因为它能运行各种各样的程序，而程序之所以能解决问题，是因为它所体现了正确的算法 算法所解决的是一类问题而不是一个特定的问题，例如排序(sort)可以是表格内容的排序，也可以是文件夹中文件的排序，可以按数字或文字排序，也可以按日期排序，等等查找(search)，可以在文档中查找某个单词或在硬盘中查找某个文件，也可在Web上查找某个网页，等等开发计算机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上实现(即开发成为软件)计算机算法的4个特点目的：完成某个特定的信息处理任务必须满足的性质：①确定性：算法中每一步操作的含义必须清楚明确，无二义性②能行性：算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内③有穷性：算法在执行了有限步操作后必须结束④算法结束后至少产生一个输出（包括参量或状态的变化）3.3.2程序设计语言机器语言汇编语言高级程序设计语言什么是程序设计语言？什么是程序？程序是为了用计算机解决某个问题而采用程序设计语言编写的一个指令序列什么是程序设计语言？语言的目的是用于通信程序设计语言用于人与计算机之间的通信程序设计语言是由人使用但计算机可以理解的一种语言程序设计语言用于编制程序，表达需要计算机完成什么任务和怎样完成任务，然后交给计算机去完成程序设计语言填补了

人与计算机交流的鸿沟计算机硬件仅仅知道0和1有问题需要计算机解决的人交流的鸿沟计算机硬件仅仅知道0和1有问题需要计算机解决的人程序设计语言计算机中使用多种“语言”程序设计语言：主要用于描述算法机器语言、汇编语言、高级语言数据描述语言：主要用于描述数据（文档、音乐、图形、图像、视频等）的规范、结构和文件格式HTML、XML、MIDI、MP3、OpenGL、JPEG、MPEG、······脚本语言：用于编写嵌入在文档中的程序的程序设计语言VBA、VBScript、JavaScript计算机通信语言（通信协议）：用于描述计算机-计算机之间的会话（请求-应答）的语法和语义HTTP、POP3、SMTP、FTP、Telnet、TCP、IP、······数据库语言：用于数据操作，如SQL语言······B87F01BB210203D8B81F042BC3（计算1055-(383+545)的5条机器指令）机器语言

机器语言就是计算机的指令系统指令是使用二进制编码表示的用机器语言编程序,也就是直接使用二进制代码编写程序优点：可以直接被计算机执行缺点：记不住、难理解、效率低、不易维护不同的机器语言程序，相互不兼容现在已不直接用机器语言编制程序！操作码操作数(或操作数的地址)1条机器指令操作数地址操作码例：机器语言程序在MIPS计算机上求最大公约数（GCD）的机器程序（16进制表示）MISP计算机的每条机器指令均为32个二进位，用8个16进制数表示汇编语言用助记符号来表示机器指令中的操作符与操作数优点：操作数直接使用十进制程序相对容易理解缺点：大型程序难以开发依赖于具体计算机将383传送到AX寄存器将545传送到BX寄存器将BX内容加AX内容，结果在BX中将1055传送到AX寄存器将AX内容减BX内容，结果在AX寄存器中B87F01BB210203D8B81F042BC3（计算1055-(383+545)的5条机器指令）机器语言程序对应的汇编语言程序MOVAX383MOVBX545ADDBXAXMOVAX1055SUBAXBX汇编语言程序高级程序设计语言目的：克服汇编语言的缺陷，提高编程和维护的效率特点：接近人们日常使用的自然语言（主要是英语）容易理解、记忆和使用可在不同计算机上通用对使用的符号、词汇、语法和语义等各种语言成分都有严格的规定意义：使程序设计的难度降低，导致了计算机的发展进入新的阶段MOVAX383MOVBX545ADDBXAXMOVAX1055SUBAXBX汇编语言程序S=1055-(383+545)选择排序的C语言程序voidsort(intA[],intn)/*sort函数有2个参数:整型数组A和数组元素个数n*/{inti,j,t,k;/*定义4个整型变量*/for(i=0;i<n-1;i++){/*重复执行n-1次，每次增加1个已排序的数*/

j=i;for(k=i+1;k<n;k++)if(A[k]<A[j])j=k;/*在未排序整数中确定最小数的位置*/

t=A[i];A[i]=A[j];A[j]=t;/*把未排序数中的最小数交换到未排序数的首位*/}}数据成份运算成份控制成份传输成份高级程序设计语言的发展50年代：Fortran，ALGOL60年代：COBOL语言，BASIC语言70年代：Pascal语言，C语言80年代：Ada语言，PROLOG语言，LISP语言90年代起：面向对象语言C++、JAVA、C#等FORTRAN语言FORTRAN是FORmula

TRANslation

（公式翻译）的缩写词，它是一种主要用于数值计算的面向过程的程序设计语言。FORTRAN语言的特点是接近数学公式，简单易用目前最新的国际标准是FORTRAN2008BASIC和VisualBasic语言BASIC语言的特点是简单易学VisualBASIC(VB)语言是微软公司基于BASIC发展而来的一种程序设计语言，特点是：是一种可视化的、面向对象的、采用事件驱动方式的结构化高级程序设计语言具有高效率、简单易学及功能强大的特点可以高效、快速地开发Windows环境下功能强大、图形界面丰富的应用软件资料：VBA和VBScriptVBA（VisualBasicforApplication）VB的子集，包含在Office软件（如Word、Excel、Access、PowerPoint）中用途：扩展Office软件的功能特点：寄生于已有的应用程序（如Word），不需要另外的开发环境，也不能生成.exe文件，所开发出来的程序（称为“宏”）必须由它的宿主程序调用才能运行VBScript语言也是VB的子集，嵌入在HTML文档中使用所编写的脚本程序可以扩充网页的功能，例如：动态修改网页的内容和控制文档的展现检验用户的输入信息是否正确等Java语言由SUNMicrosystem公司于1995年发布的一种面向对象的、用于网络环境的程序设计语言基本特征：适用于网络分布环境具有一定的平台独立性安全性和稳定性好应用举例： 从网络下载到浏览器中运行的跨平台小程序JavaappletsAndroid手机中运行的应用程序大多是Java程序C语言和C++语言C语言是1972～1973年间由AT＆T公司Bell实验室开发而成C语言兼有高级语言的优点和汇编语言的效率，有效地处理了简洁性和实用性、可移植性和高效性之间的矛盾C++语言以C语言为基础发展而成，既有数据抽象和面向对象能力，运行性能高，又能与C语言兼容，因而C++语言迅速流行，成为当前面向对象程序设计的主流语言iOS操作系统运行的应用程序大多是C++编写的程序3.3.3程序设计语言

处理系统程序设计语言的翻译程序把甲语言编写的程序翻译为等价的乙语言编写的程序。其中甲语言程序称为源程序，乙语言程序称为目标程序翻译程序源程序目标程序常用的有下列几种：汇编程序(汇编器)汇编语言源程序机器语言目标程序编译程序(编译器)高级语言源程序机器语言或汇编语言目标程序解释程序(解释器)高级语言源程序边解释边执行，不产生目标程序编译程序与解释程序的区别解释：解释器直接解释并且执行源语言程序，不产生目标程序（相当于“口译”）编译：把源程序编译为机器语言目标程序后，再由计算机运行（相当于“笔译”）源程序目标程序编译器计算机编译方式