C++课件第一章.ppt

第一章引论 教学目标 1 了解编程求解问题的全过程 2 了解算法基础知识 3 掌握结构化算法的表示方法 4 理解常用算法设计思想 主要内容 1 1软件开发和程序设计 1 2计算机算法 1 3结构化程序设计思想 1 1软件开发和程序设计 几个基本概念 inta b result cout a b result 3 a 2 b 1 cout resultis result endl 软件 程序 语言 语言规则 概念 计算机语言 是规则和符号的集合 是与计算机交流的工具 程序 求解问题的指令序列 软件 程序 相关文档的集合 为何要自行开发软件 学习语言编写程序制作软件 计算机语言的发展 第一代 机器语言第二代 汇编语言第三代 面向过程语言第四代 面向对象语言 软件概念的变迁 在软件的发展过程中 软件从个性化的程序变为工程化的产品 人们对软件的看法发生了根本性的变化 从 软件 程序 软件 程序 数据 文档 1 1 1软件开发过程 软件生存周期 是指软件产品从考虑其概念开始到该软件产品交付使用 直至最终退役为止的整个过程 一般包括计划 分析 设计 实现 测试 集成 交付 维护等阶段 目的是要弄清楚系统应该 必须 做什么 需求分析是软件开发项目得以成功的基础 关键的任务是要确切地定义用户 要解决的问题是什么 有可行的解吗 目的 回答 应该如何解决这个问题 总体上说 系统应该如何实现 目标是确定应该怎样具体地实现所要求的系统 为成为持久满足用户需要的软件 维护包含3方面内容 校正性维护 排除使用中暴露出的错误 适应性维护 使软件适应运行环境的变化 完善性维护 对软件的功能加以扩充 软件开发的最终目标 把对于软件的定义 描述和设计的结果翻译成计算机能 理解 和执行的形式 即用某种程序设计语言书写的正确的程序 模块 通过精心选择的测试数据 观察程序执行的结果是否与规定的预期结果相符 如果发现有不一致的情况 查明原因加以纠正 1 1 2程序设计方法 程序设计 是用计算机语言对所要解决的问题中的数据以及处理问题的方法和步骤所做的完整而准确的描述 这个描述的过程就称为程序设计 两种程序设计方法 面向过程的程序设计方法面向过程的程序设计是一种基于功能分析及每个功能由计算机的一个操作过程实现的程序设计方法 又称为传统的程序设计 面向对象的程序设计方法面向对象程序设计是在吸取结构化程序设计的一切优点的基础上发展起来的一种新的程序设计方法 它的本质是把数据和处理数据的过程当成一个整体 对象 例如五子棋 面向过程的设计思路就是首先分析问题的步骤 1 开始游戏 2 黑子先走 3 绘制画面 4 判断输赢 5 轮到白子 6 绘制画面 7 判断输赢 8 返回步骤2 9 输出最后结果 把上面每个步骤用分别的函数来实现 问题就解决了 面向对象的设计则从另外的思路来解决问题 整个五子棋可以分为 1 黑白双方 这两方的行为是一模一样的2 棋盘系统 负责绘制画面3 规则系统 负责判定诸如犯规 输赢等 第一类对象 玩家对象 负责接受用户输入 并告知第二类对象 棋盘对象 棋子布局的变化 棋盘对象接收到了棋子的变化就要负责在屏幕上面显示出这种变化 同时利用第三类对象 规则系统 来对棋局进行判定 1 1 3程序设计过程 分析问题设计算法与数据结构检查算法编码实现测试和调试程序 1 2计算机算法 1 2 1算法的基本概念算法是完成一项任务的具体步骤 计算机算法分为数值算法和非数值算法两大类 数值算法的目的是求数值解 非数值算法应用范围十分广泛 最常见的是事务管理领域 例如图书检索 人事管理 行车调度管理等 目前 计算机在非数值方面的应用远远超过了在数值方面的应用 例子1 计算函数M x 的值 函数M x 为 算法分析 本题是一个数值运算问题 其中M代表要计算的函数值 有两个不同的表达式 根据x的取值决定采用哪一个算式 根据计算机具有逻辑判断的基本功能 用计算机解题的算法如下 将a b c和x的值输入到计算机 判断x a 如果条件成立 执行第 步 否则执行第 步 按表达式bx a2计算出结果存放到M中 然后执行第 步 按表达式a c x c2计算出结果存放到M中 然后执行第 步 输出M的值 算法结束 这是用自然语言描述的算法 例子2 有黑和蓝两个墨水瓶 但却错把黑墨水装在了蓝墨水瓶子里 而蓝墨水错装在了黑墨水瓶子里 要求将其互换 算法分析 这是一个非数值运算问题 因为两个瓶子的墨水不能直接交换 所以 解决这一问题的关键是需要引入第三个墨水瓶 设第三个墨水瓶为白色 其交换步骤如下 将黑瓶中的蓝墨水装入白瓶中 将蓝瓶中的黑墨水装入黑瓶中 将白瓶中的蓝墨水装入蓝瓶中 交换结束 广义的说 为解决一个问题而采取的方法和步骤就称为 算法 对同一个问题 可有不同的解题方法和步骤 算法决定了程序的质量 例子 求1 2 3 4 100 方法1 1 2 3 4 一直加到100 加99次方法2 100 1 99 2 98 49 51 50 100 49 100 50加55次 2 算法的主要特征 算法是一个有穷规则的集合 这些规则确定了解决某类问题的一个运算序列 有效性 算法中的每一步操作都应该能有效执行 一个不可执行的操作是无效的 有穷性 一个算法必须在执行有限个操作步骤后终止 确定性 算法中每一步的含义必须是确切的 不可出现任何二义性 有零个或多个输入一个或多个输出 3 算法主要因素 1 正确性 算法应满足具体问题的要求 2 可读性 一个可读性好的算法有助于对算法的理解 易于调试和修改 3 健壮性 当输入非法数据时 算法也能够作出适当的反应或处理 而不会产生一些莫名其妙的结果 更不会出现死机 系统崩溃等情况 4 高效性 算法的效率与算法占用计算机设备资源成反比 而最突出的就是计算机的运行时间和计算机的存储空间 占用时间越短效率越高 占用内存空间越少效率越高 1 2 2算法的表示 描述算法的方法有很多 常见的方法有 自然语言流程图 传统流程图 结构化流程图 伪代码IPO图PAD图等 1 用自然语言表示算法 自然语言是指人们日常使用的语言 如汉语 英语等 使用自然语言描述算法 通俗易懂 但叙述文字冗长 含义不尽严格 容易出现 歧义性 在程序设计中一般不用自然语言表示算法 将a b c和x的值输入到计算机 判断x a 如果条件成立 执行第 步 否则执行第 步 按表达式bx a2计算出结果存放到M中 然后执行第 步 按表达式a c x c2计算出结果存放到M中 然后执行第 步 输出M的值 算法结束 用自然语言描述的算法 其交换步骤如下 将黑瓶中的蓝墨水装入白瓶中 将蓝瓶中的黑墨水装入黑瓶中 将白瓶中的蓝墨水装入蓝瓶中 交换结束 用自然语言描述的算法 2 用传统流程图表示算法 流程图 就是对给定算法的一种图形解法 流程图又称为框图 它用规定的一系列图形 流程线及文字说明来表示算法中的基本操作和控制流程其优点是形象直观 简单易懂 便于修改和交流 传统流程图 美国国家标准化协会ANSI AmericanNationalStandardInstitute 规定了一些常用的符号表示特定的操作 这些符号已为世界各国程序工作者普遍采用 流程图符号 流程图符号 注释框 表示对算法中的某一操作或某一部分操作所作的必要的备注说明 流程图的用法 例子用传统流程图表示算法 描述求解5 的算法方法1 方法2 将黑瓶中的蓝墨水装入白瓶中 将蓝瓶中的黑墨水装入黑瓶中 将白瓶中的蓝墨水装入蓝瓶中 交换结束 课内练习一 用流程图表示如下的算法 解题算法用流程图表示 将黑瓶中的蓝墨水装入白瓶中 将蓝瓶中的黑墨水装入黑瓶中 将白瓶中的蓝墨水装入蓝瓶中 交换结束 C b 将a b c和x的值输入到计算机 判断x a 如果条件成立 执行第 步 否则执行第 步 按表达式bx a2计算出结果存放到M中 然后执行第 步 按表达式a c x c2计算出结果存放到M中 然后执行第 步 输出M的值 算法结束 课内练习二 用流程图表示如下的算法 解题算法用流程图表示 3 结构化流程图表示 1 三种基本结构的流程图1966年 计算机科学家Bohm和Jacopini证明了这样的事实 任何简单或复杂的算法都可以由顺序结构 选择结构和循环结构这三种基本结构组合而成 由这三种基本结构所构成的算法称为结构化算法 并可组合应用来解决任何复杂问题 1 顺序结构 表示程序中的各操作是按照它们出现的先后顺序执行的 2 选择结构 选择结构表示程序的处理步骤出现了分支 它需要根据某一特定的条件选择其中的一个分支执行 选择结构有单选择 双选择和多选择三种形式 多选择结构是指程序流程中遇到如图1 9所示的s1 s2 sn等多个分支 程序执行方向将根据条件确定 3 循环结构 循环结构又称重复结构 即重复执行一组操作 它可进一步分为当型循环结构和直到型循环结构两类 2 N S流程图 两位美国学者Nassi和Shneiderman于1973年就提出了一种新的流程图形式 这就是N S流程图 它是以两位创作者姓名的首字母取名 也称为NassiShneiderman图 N S流程图是结构化程序设计方法中用于表示算法的图形工具之一 对于结构化程序设计来说 传统流程图已很难完全适应了 因为传统流程图出现得较早 它更多地反映了机器指令系统设计和传统程序设计方法的需要 难以保证程序的结构良好 另外 结构化程序设计的一些基本结构在传统流程图中没有相应的表达符号 N S流程图 N S图的基本单元是矩形框 它只有一个入口和一个出口 长方形框内用不同形状的线来分割 可表示顺序结构 选择结构和循环结构 在N S流程图中 完全去掉了带有方向的流程线 程序的三种基本结构分别用三种矩形框表示 将这种矩形框进行组装就可表示全部算法 例子 用N S流程图表示前面例中求函数值m的算法 将a b c和x的值输入到计算机 判断x a 如果条件成立 执行第 步 否则执行第 步 按表达式bx a2计算出结果存放到M中 然后执行第 步 按表达式a c x c2计算出结果存放到M中 然后执行第 步 输出M的值 算法结束 2 例1 2 3 用传统流程图描述求解 5 的算法 用N S图表显示是什么样的呢 4 伪代码表示算法 伪代码是用介于自然语言与计算机语言之间的文字和符号来描述算法 它如同一篇文章 自上而下地写下来 每一行 或几行 表示一个基本操作 它不用图形符号 书写和修改方便 格式紧凑 比较好懂 且便于向计算机语言程序过渡 例子 例子 打印出50个学生中成绩高于80分者的学号和成绩 用伪代码表示算法如下 BEGIN1 iWhilei 80printn i andg i i 1 i END 算法结束 1 2 3算法设计策略 枚举法递推法递归法分治法 1 枚举法 枚举法也称为穷举法 它的基本思想是 首先根据问题的部分条件预估答案的范围 然后在此范围内对所有可能的情况进行逐一验证 直到全部情况均通过了验证为止 若某个情况使验证符合题目的全部条件 则该情况为本题的一个答案 若全部情况验证结果均不符合题目的全部条件 则说明该题无答案 例子 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 翁 母 雏各几何 枚举法解题需要以下步骤 1 分析题目 确定答案的大致范围 2 确定列举方法 常用的列举方法有 顺序列举 排列列举和组合列举 3 作试验 直到遍历所有情况 4 试验完后可能找到与题目要求完全一致的一组或多组答案 也可能没找到答案 即证明题目无答案 2 递推法 所谓递推法 是指利用递推公式 由简到繁逐次迭代求解 求解n 可由1 2 n 来完成 其算法存在如下递推过程 f 0 0 1f 1 1 1 0 1f 2 2 2 1 2f 3 3 3 2 6 f n n n n 1 n f n 1 3 递归法 什么是递归法 它与递推法有什么不同 递归法也是利用递推公式 所不同的是 它是由繁化简 用简单的问题和已知的操作运算来解决复杂的问题 包含两个过程 由繁到简的递推化简 由已知值f 1 经乘法运算回归到所求值 可见 递推与递归是有区别的 通常递归是这样定义的 如果一个过程直接或间接地有限次数地调用了它自身 则称这个该过程是递归的 例1 8 有如下递归定义函数 由函数的定义可见 如果n 0 xn的值是1 如果n 0 xn的值就是xn 1的x倍 用递归法分析 对于任何大于0的整数n xn的值是由xn 1的值确定的 而xn 1的值是由xn 2的值确定的 就这样逐次上溯调用其本身的求解过程 最终xn的值将归结到x0的定义上 而x0的定义是函数明确给出的 所以问题得到了结果 这就是递归的方法 递归与递推的关系 递归与递推是既有区别又有联系的两个概念 递推是从已知的初始条件出发 逐次递推出最后所求的值 而递归则是从需要求解的函数本身出发 逐次上溯调用其本身的求解过程 直到递归的出口 然后再从里向外倒推回来 得到最终的值 一般说来 一个递推算法总可以转换为一个递归算法 4 分治法 在求解一个复杂问题时 应尽可能地把这个问题分解为较小部分 找出各部分的解 然后再把各部分的解组合成整个问题的解 这就是所谓的分治法 1 2 4算法复杂性分析 评价算法好坏的标准求解同一计算问题可能有许多不同的算法 究竟如何来评价这些算法的好坏以便从中选出较好的算法呢 选用的算法首先应该是 正确 的 此外 主要考虑如下三点 执行算法所耗费的时间 执行算法所耗费的存储空间 其中主要考虑辅助存储空间 算法应易于理解 易于编码 易于调试等 算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量 需要时间资源的量称为时间复杂性 需要的空间资源的量称为空间复杂性 这个量应该只依赖于算法要解的问题的规模 算法的输入和算法本身的函数 算法性能选择 一个占存储空间小 运行时间短 其它性能也好的算法是很难做到的 原因是上述要求有时相互抵触 要节约算法的执行时间往往要以牺牲更多的空间为代价 而为了节