算法和程序设计.ppt

《算法和程序设计.ppt》由会员分享，可在线阅读，更多相关《算法和程序设计.ppt（41页珍藏版）》请在三一办公上搜索。

1、3.3 算法和程序设计,3.3.1 算法3.3.2 程序设计语言3.3.3 程序设计语言处理器,3.3.1 算法,计算机求解问题的步骤,(1)确定并理解问题；(2)寻找解决问题的方法与步骤，并将其表示成算法(Algorithm)；(3)使用某种程序设计语言描述该算法(编程),并进行调试；(4)运行程序，获得问题的解答；(5)进行评估，改进算法和程序,1.什么是算法？,算法是解决问题的方法与步骤,例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？分析：方法明确而有序按提供的条件进行操作任何人均可仿照进行(共享智能),关于算法的三方面问题,如

2、何确定算法（算法设计）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？,2.算法设计举例,典型问题：如何对数据进行排序,问题：任给一组(n个)整数，将它们从小到大进行排序“选择排序”算法的思路：从所有整数中选一个最小数，作为已排序的第一个数 从剩下未排序整数中选最小的数，添加到已排序整数的后面 反复执行步骤，直到所有整数都处理完毕,“选择排序”算法举例,3.算法的表示,文字叙述流程图表示伪代码描述,文字(自然语言)描述,“比较与的重量，若，则是伪造的；否则再比较与的重量，若，则是伪造的；否则是伪造的。”缺点：容易产生歧义，很难“精确”地进行表达叙述冗长，很难清楚地表达算法的逻辑流程,

3、算法的流程图表示,流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件流程图符号：,比文字描述简明，但当算法比较复杂时，理解困难，容易产生错误,用流程图表示选择排序算法,使用伪代码描述算法,伪代码(Pseudo code)是用来描述算法的一种语言，它既类似于自然语言，又使用与程序设计语言相似的方法描述算法,优点：结构清晰，代码简单，可读性好，可以容易地以任何一种编程语言(Pascal,C,Java等)实现,每个整数是A的一个元素：A1,A2,An,4.算法的分析,算法分析的基本内容,正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果简单性 算法是否容易理解，是否容

4、易验证其正确性，程序是否容易调试简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单时间复杂性(Time Complexity)：当问题的规模n充分大时，运行该算法所需要的时间的数量级表示 空间复杂性(Space Complexity)：除原始数据之外，额外占用的存储空间的大小,选讲：选择排序算法的时间复杂性,假设参加排序的整数有n个（1）比较操作的次数：在第i趟排序中选出最小整数时，需做n-i次比较操作，因此，总的比较操作次数为：n(n-1)/2=(n2-n)/2（2）移动操作的次数：最好情况(原始数据已经排序)时，移动次数为0最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3

5、次传送)，总的移动次数取最大值为：3(n-1)所以，直接选择排序的时间复杂性 为 O(n2),设置i的初值为1，循环执行下列操作，直到I=n：确定Ai 到An中最小的整数元素的位置，设为j；交换Ai和j；i=i+1,关于算法的小结,计算机中处处是算法！,例1：Word程序如何在文档中查找用户指定的词语？例2：在Word文档的表格中如何将表格内容排序？例3：如何把一幅彩色图片转换为灰度(黑白)图片？例4：Windows如何在硬盘中找到用户指定的文件？例5：媒体播放器如何把MP3文件转换成动听的音乐？例6：搜索引擎如何在WWW网中找到用户需要的网页？,算法是计算机软件的灵魂,计算机的通用性是因为它

6、能运行各种各样的程序，而程序之所以能解决问题，是因为它所体现了正确的算法算法所解决的是一类问题而不是一个特定的问题，例如排序(sort)可以是表格内容的排序，也可以是文件夹中文件的排序，可以按数字或文字排序，也可以按日期排序，等等查找(search)，可以在文档中查找某个单词或在硬盘中查找某个文件，也可在Web上查找某个网页，等等开发计算机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上实现(即开发成为软件),计算机算法的4个特点,目的：完成某个特定的信息处理任务必须满足的性质：确定性：算法中每一步操作的含义必须清楚明确，无二义性 能行性：算法中有待实现的操作都是计算机可执行

7、的，即必须在计算机的能力范围之内 有穷性：算法在执行了有限步操作后必须结束 算法结束后至少产生一个输出（包括参量或状态的变化）,3.3.2 程序设计语言,机器语言汇编语言高级程序设计语言,什么是程序设计语言？,什么是程序？程序是为了用计算机解决某个问题而采用程序设计语言编写的一个指令序列什么是程序设计语言？语言的目的是用于通信程序设计语言用于人与计算机之间的通信程序设计语言是由人使用但计算机可以理解的一种语言程序设计语言用于编制程序，表达需要计算机完成什么任务和怎样完成任务，然后交给计算机去完成,程序设计语言填补了 人与计算机交流的鸿沟,计算机中使用多种“语言”,程序设计语言：主要用于描述算法

8、机器语言、汇编语言、高级语言数据描述语言：主要用于描述数据（文档、音乐、图形、图像、视频等）的规范、结构和文件格式HTML、XML、MIDI、MP3、OpenGL、JPEG、MPEG、脚本语言：用于编写嵌入在文档中的程序的程序设计语言VBA、VBScript、JavaScript 计算机通信语言（通信协议）：用于描述计算机-计算机之间的会话（请求-应答）的语法和语义HTTP、POP3、SMTP、FTP、Telnet、TCP、IP、数据库语言：用于数据操作，如SQL语言,机器语言,机器语言就是计算机的指令系统指令是使用二进制编码表示的用机器语言编程序,也就是直接使用二进制代码编写程序优点：可以直

9、接被计算机执行缺点：记不住、难理解、效率低、不易维护不同的机器语言程序，相互不兼容现在已不直接用机器语言编制程序！,例：机器语言程序,在MIPS计算机上求最大公约数（GCD）的机器程序（16进制表示）,MISP计算机的每条机器指令均为32个二进位，用8个16进制数表示,汇编语言,用助记符号来表示机器指令中的操作符与操作数,优点：操作数直接使用十进制程序相对容易理解,缺点：大型程序难以开发依赖于具体计算机,将383传送到AX寄存器,将545传送到BX寄存器,将BX内容加AX内容，结果在BX中,将1055传送到AX寄存器,将AX内容减BX内容，结果在AX寄存器中,高级程序设计语言,目的：克服汇编语

10、言的缺陷，提高编程和维护的效率 特点：接近人们日常使用的自然语言（主要是英语）容易理解、记忆和使用可在不同计算机上通用对使用的符号、词汇、语法和语义等各种语言成分都有严格的规定意义：使程序设计的难度降低，导致了计算机的发展进入新的阶段,选择排序的C语言程序,void sort(int A,int n)/*sort函数有2个参数:整型数组A和数组元素个数n*/int i,j,t,k;/*定义4个整型变量*/for(i=0;in-1;i+)/*重复执行n-1次，每次增加1个已排序的数*/j=i;for(k=i+1;kn;k+)if(AkAj)j=k;/*在未排序整数中确定最小数的位置*/t=Ai;

11、Ai=Aj;Aj=t;/*把未排序数中的最小数交换到未排序数的首位*/,高级程序设计语言的发展,50年代：Fortran，ALGOL60年代：COBOL语言，BASIC语言70年代：Pascal 语言，C语言80年代：Ada语言，PROLOG语言，LISP语言90年代起：面向对象语言C+、JAVA、C#等,FORTRAN语言,FORTRAN是FORmula TRANslation（公式翻译）的缩写词，它是一种主要用于数值计算的面向过程的程序设计语言。FORTRAN语言的特点是接近数学公式，简单易用 目前最新的国际标准是FORTRAN 2003,BASIC和Visual Basic语言,BASI

12、C语言的特点是简单易学Visual BASIC(VB)语言是微软公司基于BASIC发展而来的一种程序设计语言，特点是：是一种可视化的、面向对象的、采用事件驱动方式的结构化高级程序设计语言具有高效率、简单易学及功能强大的特点可以高效、快速地开发Windows 环境下功能强大、图形界面丰富的应用软件,资料：VBA和VBScript,VBA（Visual Basic for Application）VB的子集，包含在Office软件（如Word、Excel、Access、Power Point）中用途：扩展Office软件的功能特点：寄生于已有的应用程序（如Word），不需要另外的开发环境，也不能生

13、成.exe文件，所开发出来的程序（称为“宏”）必须由它的宿主程序调用才能运行VBScript语言也是VB的子集，嵌入在HTML文档中使用所编写的脚本程序可以扩充网页的功能，例如：动态修改网页的内容和控制文档的展现检验用户的输入信息是否正确等,Java语言,由SUN Microsystem公司于1995年发布的一种面向对象的、用于网络环境的程序设计语言基本特征：适用于网络分布环境具有一定的平台独立性安全性和稳定性好应用举例：从网络下载到浏览器中运行的跨平台小程序Java applets便携式数字设备(如手机)中的应用程序,C语言和C+语言,C语言是19721973年间由ATT公司Bell实验室开

14、发而成C语言兼有高级语言的优点和汇编语言的效率，有效地处理了简洁性和实用性、可移植性和高效性之间的矛盾C+语言以C语言为基础发展而成，既有数据抽象和面向对象能力，运行性能高，又能与C语言兼容，因而C+语言迅速流行，成为当前面向对象程序设计的主流语言,3.3.3 程序设计语言 处理系统,程序设计语言的翻译程序,把甲语言编写的程序翻译为等价的乙语言编写的程序。其中甲语言程序称为源程序，乙语言程序称为目标程序,常用的有下列几种：,编译程序与解释程序的区别,解释：解释器直接解释并且执行源语言程序，不产生目标程序（相当于“口译”）编译：把源程序编译为机器语言目标程序后，再由计算机运行（相当于“笔译”）,BASIC、Visual Basic、VBScript、Java、JavaScript等都是解释执行的语言,C、C+等都是需要编译的语言,编译程序的处理过程,附：计算机软件技术,计算机软件技术有哪些内容？,