算法和程序设计

1、算法和程序设计求解问题的步骤求解问题的步骤(1) 确定并理解问题；确定并理解问题；(2) 寻找解决问题的方法与步骤，并将其表示成寻找解决问题的方法与步骤，并将其表示成算法算法(Algorithm) ；(3) 使用某种程序设计语言描述该算法使用某种程序设计语言描述该算法(编程编程), 并并进行调试；进行调试；(4) 运行程序，获得问题的解答；运行程序，获得问题的解答；(5) 进行评估，改进算法和程序进行评估，改进算法和程序1. 什么是算法？什么是算法？算法是解决问题的方法与步骤算法是解决问题的方法与步骤n例：有三个硬币，其中一个是伪造例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重的

2、，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，量略有不同。现在提供一座天平，如何找出伪币呢？如何找出伪币呢？n分析：分析：n方法明确而有序方法明确而有序n按提供的条件进行操作按提供的条件进行操作n任何人均可仿照进行任何人均可仿照进行(共享智共享智能能)开始开始C是伪币是伪币B是伪币是伪币A是伪币是伪币AB？AC？是是否否否否是是关于算法的三方面问题关于算法的三方面问题n如何确定算法（算法设计）？如何确定算法（算法设计）？n如何表示算法（算法表示）？如何表示算法（算法表示）？n如何使算法更有效（算法分析）？如何使算法更有效（算法分析）？ 2. 算法设计举例算法设计举例典型问题：如何对

3、数据进行排序典型问题：如何对数据进行排序n问题：任给一组问题：任给一组(n个个)整数，将它们从小到大进行整数，将它们从小到大进行排序排序n“选择排序选择排序”算法的思路：算法的思路： 从所有整数中选一个最小数，作为已排序的第一个数从所有整数中选一个最小数，作为已排序的第一个数 从剩下未排序整数中选最小的数，添加到已排序整数从剩下未排序整数中选最小的数，添加到已排序整数的后面的后面 反复执行步骤，直到所有整数都处理完毕反复执行步骤，直到所有整数都处理完毕“选择排序选择排序”算法举例算法举例2345789第第6次循环后，排序结束次循环后，排序结束2937845与首元素交换，第与首元素交换，第1次循

4、环结束次循环结束4937825数组的初态，全部是未排序元素数组的初态，全部是未排序元素4937825在未排序元素中确定最小数位置在未排序元素中确定最小数位置2397845与首元素交换，第与首元素交换，第2次循环结束次循环结束2937845在未排序元素中确定最小数位置在未排序元素中确定最小数位置2347895与首元素交换，第与首元素交换，第3次循环结束次循环结束2397845在未排序元素中确定最小数位置在未排序元素中确定最小数位置3. 算法的表示算法的表示n文字叙述文字叙述n流程图表示流程图表示n伪代码描述伪代码描述文字文字(自然语言自然语言)描述描述n“比较与的重量，若，则是伪造的；比较与的重

5、量，若，则是伪造的；否则再比较与的重量，若，则是伪造否则再比较与的重量，若，则是伪造的；否则是伪造的。的；否则是伪造的。”n缺点：缺点：n容易产生歧义，容易产生歧义，很难很难 “精确精确”地进行表达地进行表达n叙述冗长，很难清楚地表达算法的逻辑流程叙述冗长，很难清楚地表达算法的逻辑流程算法的流程图表示算法的流程图表示n流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件操作的条件n流程图符号流程图符号 ：n比文字描述简明，但当算法比文字描述简明，但当算法比较复杂时，理解困难，容比较复杂时，理解困难，容易产生错误易产生

6、错误 端点符端点符处理处理判断判断预定义功能预定义功能原始数据放在原始数据放在数组数组A中；令中；令 i=1确定确定Ai到到An中最中最小整数的位置小整数的位置,设为设为jAi 和和Aj交换位置交换位置i = i + 1i = n ?结束结束开始开始用流程图表示选择用流程图表示选择排序算法排序算法将原始数据放在数组将原始数据放在数组A中；中；设置设置i的初值为的初值为1，循环执行下列操作，直到，循环执行下列操作，直到i = n ： 确定确定Ai 到到An中最小整数的位置，设为中最小整数的位置，设为j ； 交换交换Ai和和j ； i = i +1 使用伪代码描述使用伪代码描述“选择排序选择排序”

7、算法算法使用伪代码描述算法使用伪代码描述算法n伪代码伪代码(Pseudo code)是用来描述算法的一种语言，它既类是用来描述算法的一种语言，它既类似于自然语言，又使用与程序设计语言相似的方法描述算法似于自然语言，又使用与程序设计语言相似的方法描述算法n优点：结构清晰，代码简单，可读性好，可以容易地以任优点：结构清晰，代码简单，可读性好，可以容易地以任何一种编程语言何一种编程语言(Pascal, C, Java等等)实现实现每个整数是每个整数是A的一个元素：的一个元素：A1, A2, , An4. 算法的分析算法的分析算法分析的基本内容算法分析的基本内容n正确性：给定有效输入后，经过有限时间的

8、计算，产生正确的输正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果出结果n简单性简单性n 算法是否容易理解，是否容易验证其正确性，程序是否容易调试算法是否容易理解，是否容易验证其正确性，程序是否容易调试n简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单n时间复杂性时间复杂性(Time Complexity) ：n当问题的规模当问题的规模n充分大时，运行该算法所需要的时间的数量级表示充分大时，运行该算法所需要的时间的数量级表示 n空间复杂性空间复杂性(Space Complexity) ：n除原始数据之外，额外

9、占用的存储空间的大小除原始数据之外，额外占用的存储空间的大小选讲：选讲： 选择排序算法的时间复杂性选择排序算法的时间复杂性假设参加排序的整数有假设参加排序的整数有n个个（1）比较操作的次数：）比较操作的次数：在第在第i趟排序中选出最小整数时，需做趟排序中选出最小整数时，需做n-i次比较操作，次比较操作，因此，总的比较操作次数为：因此，总的比较操作次数为：n(n-1)/2 = (n2 -n)/2（2）移动操作的次数：）移动操作的次数：最好情况最好情况(原始数据已经排序原始数据已经排序)时，移动次数为时，移动次数为0最坏情况最坏情况(原始数据逆序排列原始数据逆序排列)时，每趟均要执行交换操作时，每

10、趟均要执行交换操作(3次次传送传送)，总的移动次数取最大值为：，总的移动次数取最大值为：3(n-1) 所以，直接选择排序的时间复杂性所以，直接选择排序的时间复杂性 为为 O(n2)设置设置i的初值为的初值为1，循环执行下列操作，直到，循环执行下列操作，直到I = n ： 确定确定Ai 到到An中最小的整数元素的位置，设为中最小的整数元素的位置，设为j ； 交换交换Ai和和j ； i = i +1 关于算法的小结关于算法的小结计算机中处处是算法！计算机中处处是算法！例例1：Word程序如何在文档中查找用户指定的词语？程序如何在文档中查找用户指定的词语？例例2：在：在Word文档的表格中如何将表格

11、内容排序？文档的表格中如何将表格内容排序？例例3：如何把一幅彩色图片转换为灰度：如何把一幅彩色图片转换为灰度(黑白黑白)图片？图片？例例4： Windows如何在硬盘中找到用户指定的文件？如何在硬盘中找到用户指定的文件？例例5：媒体播放器如何把：媒体播放器如何把MP3文件转换成动听的音乐？文件转换成动听的音乐？例例6：搜索引擎如何在：搜索引擎如何在WWW网中找到用户需要的网页？网中找到用户需要的网页？算法是计算机软件的灵魂算法是计算机软件的灵魂n计算机的通用性是因为它能运行各种各样的程序，而程序之所以计算机的通用性是因为它能运行各种各样的程序，而程序之所以能解决问题，是因为它所体现了正确的算法

12、能解决问题，是因为它所体现了正确的算法n算法所解决的是一类问题而不是一个特定的问题，例如算法所解决的是一类问题而不是一个特定的问题，例如n排序排序(sort) 可以是表格内容的排序，也可以是文件夹中文件的排序，可以是表格内容的排序，也可以是文件夹中文件的排序，可以按数字或文字排序，也可以按日期排序，等等可以按数字或文字排序，也可以按日期排序，等等n查找查找(search)， 可以在文档中查找某个单词或在硬盘中查找某个文件，可以在文档中查找某个单词或在硬盘中查找某个文件，也可在也可在Web上查找某个网页，等等上查找某个网页，等等n开发计算机应用的核心是：根据实际问题给出解题的算法，然后再开发计算

13、机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上实现将该算法在计算机上实现(即开发成为软件即开发成为软件)计算机算法的计算机算法的4个特点个特点n目的：完成某个特定的信息处理任务目的：完成某个特定的信息处理任务n必须满足的性质：必须满足的性质： 确定性：算法中每一步操作的含义必须清楚明确，确定性：算法中每一步操作的含义必须清楚明确，无二义性无二义性 能行性：能行性： 算法中有待实现的操作都是计算机可执行算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内的，即必须在计算机的能力范围之内 有穷性：有穷性： 算法在执行了有限步操作后必须结束算法在执行了有限步操作

14、后必须结束 算法结束后至少产生一个输出（包括参量或状态的算法结束后至少产生一个输出（包括参量或状态的变化）变化） 3.3.2 程序设计语言程序设计语言n机器语言机器语言n汇编语言汇编语言n高级程序设计语言高级程序设计语言什么是程序设计语言？什么是程序设计语言？n什么是程序？什么是程序？n程序是为了用计算机解决某个问题而采用程序设计程序是为了用计算机解决某个问题而采用程序设计语言编写的一个指令序列语言编写的一个指令序列n什么是程序设计语言？什么是程序设计语言？n语言的目的是用于通信语言的目的是用于通信n程序设计语言用于人与计算机之间的通信程序设计语言用于人与计算机之间的通信n程序设计语言是由人使

15、用但计算机可以理解的一种程序设计语言是由人使用但计算机可以理解的一种语言语言n程序设计语言用于编制程序，表达需要计算机完成程序设计语言用于编制程序，表达需要计算机完成什么任务和怎样完成任务，然后交给计算机去完成什么任务和怎样完成任务，然后交给计算机去完成程序设计语言填补了程序设计语言填补了 人与计算机交流的鸿沟人与计算机交流的鸿沟计算机硬件仅仅计算机硬件仅仅知道知道0和和1有 问 题 需 要有 问 题 需 要计 算 机 解 决计 算 机 解 决的人的人交流的鸿沟交流的鸿沟计算机硬件仅仅计算机硬件仅仅知道知道0和和1有 问 题 需 要有 问 题 需 要计 算 机 解 决计 算 机 解 决的人的人

16、程序设计语言程序设计语言计算机中使用多种计算机中使用多种“语言语言”n程序设计语言：主要用于描述算法程序设计语言：主要用于描述算法n机器语言、汇编语言、高级语言机器语言、汇编语言、高级语言n数据描述语言：主要用于描述数据（文档、音乐、图形、图像、视频等）的规范、数据描述语言：主要用于描述数据（文档、音乐、图形、图像、视频等）的规范、结构和文件格式结构和文件格式nHTML、XML、MIDI、MP3、OpenGL、JPEG、MPEG、n脚本语言：用于编写嵌入在文档中的程序的程序设计语言脚本语言：用于编写嵌入在文档中的程序的程序设计语言nVBA、VBScript、JavaScript n计算机通信语

17、言（通信协议）：用于描述计算机计算机通信语言（通信协议）：用于描述计算机-计算机之间的会话（请求计算机之间的会话（请求-应应答）的语法和语义答）的语法和语义nHTTP、POP3、SMTP、 FTP、 Telnet、TCP、IP、n数据库语言：用于数据操作，如数据库语言：用于数据操作，如SQL语言语言nB8 7F 01BB 21 0203 D8B8 1F 042B C3（计算（计算1055-(383+545)的的5条机器指令）条机器指令） 机器语言机器语言 n机器语言就是计算机的指令系统机器语言就是计算机的指令系统n指令是使用二进制编码表示的指令是使用二进制编码表示的n用机器语言编程序用机器语言

18、编程序, 也就是直接使用二进制代码编写程序也就是直接使用二进制代码编写程序n优点：优点：n可以直接被计算机执行可以直接被计算机执行n缺点：缺点：n记不住、难理解、效率低、不易维护记不住、难理解、效率低、不易维护n不同的机器语言程序，相互不兼容不同的机器语言程序，相互不兼容n现在已不直接用机器语言编制程序！现在已不直接用机器语言编制程序！操作码操作码操作数操作数(或操作数的地址或操作数的地址)1条机器指令条机器指令操作数地址操作数地址操作码操作码例：机器语言程序例：机器语言程序n 在在MIPS计算机上求最大公约数（计算机上求最大公约数（GCD）的机器程）的机器程序（序（16进制表示）进制表示）M

19、ISP计算机的每条机器指令均为计算机的每条机器指令均为32个二进位，用个二进位，用8个个16进制数表示进制数表示 汇编语言汇编语言n用助记符号来表示机器指令用助记符号来表示机器指令中的操作符与操作数中的操作符与操作数n优点：优点：n操作数直接使用十进制操作数直接使用十进制n程序相对容易理解程序相对容易理解n缺点：缺点：n大型程序难以开发大型程序难以开发n依赖于具体计算机依赖于具体计算机将将383传送到传送到AX寄存器寄存器将将545传送到传送到BX寄存器寄存器将将BX内容加内容加AX内容，结果在内容，结果在BX中中将将1055传送到传送到AX寄存器寄存器将将AX内容减内容减BX内容，结果在内容

20、，结果在AX寄存器中寄存器中B8 7F 01BB 21 0203 D8B8 1F 042B C3（计算（计算1055-(383+545)的的5条机器指令）条机器指令）机器语言程序机器语言程序对应的汇编语言程序对应的汇编语言程序MOV AX 383MOV BX 545ADD BX AXMOV AX 1055SUB AX BX汇编语言程序汇编语言程序高级程序设计语言高级程序设计语言n目的：克服汇编语言的缺陷，提高编程和维目的：克服汇编语言的缺陷，提高编程和维护的效率护的效率 n特点：特点：n接近人们日常使用的自然语言接近人们日常使用的自然语言（主要是英语）容易（主要是英语）容易理解、记忆理解、记忆

21、和使用和使用n可在不同计算机上通用可在不同计算机上通用n对使用的符号、词汇、语法和语义等各对使用的符号、词汇、语法和语义等各种语言成分都有严格的规定种语言成分都有严格的规定n意义：使程序设计的难度降低，导致意义：使程序设计的难度降低，导致了计算机的发展进入新的阶段了计算机的发展进入新的阶段MOV AX 383MOV BX 545ADD BX AXMOV AX 1055SUB AX BX汇编语言程序汇编语言程序S=1055-(383+545)选择排序的选择排序的C语言程序语言程序void sort ( int A , int n) /* sort函数有函数有2个参数个参数:整型数组整型数组A和数

22、组元素个数和数组元素个数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;Ai=Aj; Aj=t; /* 把未排序数中的最小数交换到未排序数的首位把未排序数中的最小数交换到未排序数的首位*/ 数据成份数据成份运算成份运算成份控制控制成份成份传输成份传输成份高级程序设计语言的

23、发展高级程序设计语言的发展n50年代：年代：Fortran，ALGOLn60年代：年代：COBOL语言语言，BASIC语言语言n70年代：年代：Pascal 语言，语言，C语言语言n80年代：年代： Ada语言，语言，PROLOG语言，语言，LISP语言语言n90年代起：面向对象语言年代起：面向对象语言C+、 JAVA、C#等等FORTRAN语言语言 nFORTRAN是是FORmula TRANslation （公式翻译）（公式翻译）的缩写词，它是一种主要用于数值计算的面向过程的缩写词，它是一种主要用于数值计算的面向过程的程序设计语言。的程序设计语言。FORTRAN语言的特点是接近数语言的特点

24、是接近数学公式，简单易用学公式，简单易用 n目前最新的国际标准是目前最新的国际标准是FORTRAN 202X BASIC和和Visual Basic语言语言 nBASIC语言的特点是简单易学语言的特点是简单易学nVisual BASIC(VB)语言是微软公司基于语言是微软公司基于BASIC发发展而来的一种程序设计语言，特点是：展而来的一种程序设计语言，特点是：n是一种可视化的、面向对象的、采用事件驱动方式的是一种可视化的、面向对象的、采用事件驱动方式的结构化高级程序设计语言结构化高级程序设计语言n具有高效率、简单易学及功能强大的特点具有高效率、简单易学及功能强大的特点n可以高效、快速地开发可以

25、高效、快速地开发Windows 环境下功能强大、环境下功能强大、图形界面丰富的应用软件图形界面丰富的应用软件 资料：资料：VBA和和VBScriptnVBA（Visual Basic for Application）nVB的子集，包含在的子集，包含在Office软件（如软件（如Word、Excel、Access、Power Point）中中n用途：扩展用途：扩展Office软件的功能软件的功能n特点：寄生于已有的应用程序（如特点：寄生于已有的应用程序（如Word），不需要另外的开发环境，），不需要另外的开发环境，也不能生成也不能生成.exe文件，所开发出来的程序（称为文件，所开发出来的程序（称

26、为“宏宏”）必须由它的宿）必须由它的宿主程序调用才能运行主程序调用才能运行nVBScript语言语言n也是也是VB的子集，嵌入在的子集，嵌入在HTML文档中使用文档中使用n所编写的脚本程序可以扩充网页的功能，例如：所编写的脚本程序可以扩充网页的功能，例如：n动态修改网页的内容和控制文档的展现动态修改网页的内容和控制文档的展现n检验用户的输入信息是否正确等检验用户的输入信息是否正确等Java语言语言 n由由SUN Microsystem公司于公司于202X年发布的一种面向对象的、用于年发布的一种面向对象的、用于网络环境的程序设计语言网络环境的程序设计语言n基本特征：基本特征：n适用于网络分布环境

27、适用于网络分布环境n具有一定的平台独立性具有一定的平台独立性n安全性和稳定性好安全性和稳定性好n应用举例：应用举例：n从网络下载到浏览器中运行的跨平台小程序从网络下载到浏览器中运行的跨平台小程序Java appletsn便携式数字设备便携式数字设备(如手机如手机)中的应用程序中的应用程序C语言和语言和C+语言语言 nC语言是语言是19721973年间由年间由ATT公司公司Bell实验室开发而成实验室开发而成nC语言兼有高级语言的优点和汇编语言的效率，有效地处理了语言兼有高级语言的优点和汇编语言的效率，有效地处理了简洁性和实用性、可移植性和高效性之间的矛盾简洁性和实用性、可移植性和高效性之间的矛盾nC+语言以语言以C语言为基础发展而成，既有