第3章33算法和程序设计.ppt

3.3 算法和程序设计 3.3.1 算法 3.3.2 程序设计语言 3.3.3 程序设计语言处理器 3.3.1 算法 计算机求解问题的步骤 (1) 确定并理解问题； (2) 寻找解决问题的方法与步骤，并将其表示成算法(Algorithm) ； (3) 使用某种程序设计语言描述该算法(编程), 并编译成目标程序和进行调试； (4) 运行程序，获得问题的解答； (5) 进行评估，改进算法和程序 1. 什么是算法？ 算法是解决问题的方法与步骤 例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？ 分析： 方法明确而有序 按提供的条件进行操作 任何人均可仿照进行(共享智能) 关于算法的三方面问题 如何确定算法（算法设计）？ 如何表示算法（算法表示）？ 如何使算法更有效（算法分析）？ 2. 算法设计举例 典型问题：如何对数据进行排序 问题：任给一组(n个)整数，将它们从小到大进行排序 “选择排序”算法的思路： ① 从所有整数中选一个最小数，作为已排序的第一个数 ② 从剩下未排序整数中选最小的数，添加到已排序整数的后面 ③ 反复执行步骤②，直到所有整数都处理完毕 “选择排序”算法举例 3. 算法的表示 文字(自然语言)描述 “比较Ａ与Ｂ的重量，若Ａ＝Ｂ，则Ｃ是伪造的；否则再比较Ａ与Ｃ的重量，若Ａ＝Ｃ，则Ｂ是伪造的；否则Ａ是伪造的。” 缺点： 容易产生歧义，很难 “精确”地进行表达 叙述冗长，很难清楚地表达算法的逻辑流程 算法的流程图表示 流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件 流程图符号 ： 使用伪代码描述算法 伪代码(Pseudo code)是用来描述算法的一种语言，它既类似于自然语言，又使用与程序设计语言相似的方法描述算法 4. 算法的分析 算法分析的基本内容 正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果 简单性 算法是否容易理解，是否容易验证其正确性，程序是否容易调试 简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单 时间复杂性(Time Complexity) ： 当问题的规模n充分大时，运行该算法所需要的时间的数量级表示 空间复杂性(Space Complexity) ： 除原始数据之外，额外占用的存储空间的大小 选讲： 选择排序算法的时间复杂性 假设参加排序的整数有n个 （1）比较操作的次数： 在第i趟排序中选出最小整数时，需做n-i次比较操作， 因此，总的比较操作次数为：n(n-1)/2 = (n2 -n)/2 （2）移动操作的次数： 最好情况(原始数据已经排序)时，移动次数为0最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3次传送)，总的移动次数取最大值为：3(n-1) 所以，直接选择排序的时间复杂性 为 O(n2) 关于算法的小结 计算机中处处是算法！ 例1：Word程序如何在文档中查找用户指定的词语？ 例2：在Word文档的表格中如何将表格内容排序？ 例3：如何把一幅彩色图片转换为灰度(黑白)图片？ 例4： Windows如何在硬盘中找到用户指定的文件？ 例5：媒体播放器如何把MP3文件转换成动听的音乐？ 例6：有哪些信誉好的足球投注网站引擎如何在WWW网中找到用户需要的网页？ 算法是计算机软件的灵魂 计算机的通用性是因为它能运行各种各样的程序，而程序之所以能解决问题，是因为它所体现了正确的算法 算法所解决的是一类问题而不是一个特定的问题，例如 排序(sort) 可以是表格内容的排序，也可以是文件夹中文件的排序，可以按数字或文字排序，也可以按日期排序，等等 查找(search)， 可以在文档中查找某个单词或在硬盘中查找某个文件，也可在Web上查找某个网页，等等 开发计算机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上实现(即开发成为软件) 计算机算法的4个特点 目的：完成某个特定的信息处理任务 必须满足的性质： ① 确定性：算法中每一步操作的含义必须清楚明确，无二义性 ② 能行性： 算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内 ③ 有穷性： 算法在执行了有限步操作后必须结束 ④ 算法结束后至少产生一个输出（包括参量或状态的变化） 3.3.2 程序设计语言 机器语言 汇编语言 高级程序设计语言 什么是程序设计语言？ 什么是程序？ 程序是为了用计算机解决某个问题而采用程序设计语言编写的一个指令序列 什么是程序设计语言？ 语言的目的是用于通信 程序设计语言用于人与计算机之间的通信 程序设计语言是由人使用但计算机可以理解的一种语言 程序设计语言用于编制程序，表达需要计算机完成什么任务和怎样完成任务，然后交给