计算机程序设计基础-绪论.pptVIP

11 33 1 自我介绍 姓名 王坤E mail wk Phone11 33 2 教学用书 西南交通大学出版社 计算机程序设计基础 C 2009年2月第1版 11 33 3 第一章引论 西南交通大学软件学院计算机基础教研室 计算机程序设计基础与VisualC 11 33 4 教学内容 1 程序设计和软件开发的概念 2 程序设计语言发展史3 算法的相关概念 4 程序设计过程的简单示例 11 33 5 一 什么是程序 程序就是让计算机完成某项任务的一系列命令的集合 人们编写程序的过程称为程序设计 程序开发 程序设计和软件开发的概念 程序作为商品以有形介质为载体进行交易时即为软件软件泛指程序和相关文档的集合文档是为方便了解程序所需要的资料说明 二 什么是软件 三 软件开发过程 从开始软件的研制到废弃该软件的整个期间 称为软件生命期传统的软件开发过程可划分为问题定义与可行性研究 需求分析 概要设计 详细设计 编码和单元测试 测试和使用维护七个阶段每一阶段的工作建立在前一阶段工作的基础上 问题定义与可行性研究 关键的任务是要确切地定义用户 要解决的问题是什么 有可行的解吗 需求分析 目的是要弄清楚系统应该 必须 做什么 需求分析是软件开发项目得以成功的基础 概要设计 回答 应该如何解决这个问题 总体上说 系统应该如何实现 详细设计 目标是确定应该怎样具体地实现所要求的系统 编码和单元测试 把对于软件的定义 描述和设计的结果翻译成计算机能 理解 和执行的形式测试 通过精心选择的测试数据 观察程序执行的结果是否与规定的预期结果相符 使用维护 校正性维护 排除使用中暴露出的错误适应性维护 使软件适应运行环境变化完善性维护 对软件的功能加以扩充 四 程序设计方法 1 面向过程的程序设计为了得到问题的解而执行的一步一步的操作 称为过程面向过程的程序设计是一种基于功能分析及每个功能由计算机的一个操作过程实现的程序设计方法 又称为传统的程序设计 面向过程程序设计的关键是规划算法和数据结构 程序 算法 数据结构 2 面向对象的程序设计面向对象程序设计模拟自然界认识和处理事物的方法 将数据和对数据的操作方法组织在一起 形成一个相对独立的整体 称为对象对象是活动的 对象行为靠消息触发而激活 面向对象程序设计的关键是确定对象并对其分类 程序 对象 对象 对象 算法 数据结构 五 程序设计过程 1 分析问题通过原始资料 取得对问题的一个清晰的理解 进而确定解决问题的目标 称为输出 以及实现该目标所需要的条件 称为输入 2 设计算法与数据结构数据结构描述了问题涉及的对象之间的联系和组织结构 算法描述了求解问题的步骤或规则 设计合理的数据结构可以简化算法 好的算法使程序具有更高的效率 3 检查算法使用多组样本数据 通过手工计算 对方案的正确性进行证明和验证4 编码实现选用一种程序设计语言 如C 语言 将算法转换成计算机能够理解的程序 称为编程 5 测试和调试程序 测试 是在计算机上用样本数据运行程序 测试代码的正确性 调试 就是查找和排除程序错误 直到能够得到正确的运行结果为止程序中的错误可能是语法错误 也可能是逻辑错误 大多数语法错误容易找到和改正 但逻辑错误就较难找到 因为导致逻辑错误的原因很多 11 33 18 程序设计语言发展史 程序设计语言 计算机语言 人与机器交换信息的语言 四个阶段 1 机器语言2 汇编语言3 面向过程的高级语言4 面向对象的高级语言 1 机器语言 由二进制数组成的指令代码的集合 机器能直接识别 各种机器指令系统互不相同 计算机编码 常用ASCII码 美国标准信息交换编码 AmericanStandardCodeforInformationInterchange 示例 按ASCII码将A 1 2写成机器语言字符ASCII码十进制A0100000165 001111016110011000149 001010114320011001050 按ASCII码写出的A 1 2的机器语言 010000010011110100110001001010110011001机器语言优点 质量高 执行速度快 占存储空间小 机器语言缺点 编程难度大 指令难记 繁琐 直观性差 容易出错 检查调试困难 通用性差不兼容 2 汇编语言用助记符代替指令代码 符号化例 ADD 加法 DIV 除法 汇编语言不能直接在机器上运行 要转换成机器语言才能执行 例 汇编语言源程序 mainprocpaymovax dsegmovax 0b00haddax dxmoval blmulbl axmovbl 04h 汇编语言优点 质量高 执行速度快 占存储空间小 可读性有所提高 汇编语言缺点 类似机器语言 通用性 可移植性差 与人的自然语言还相差很悬殊 机器语言和汇编语言也称为低级语言 3 面向过程的高级语言特点 接近人们习惯用的自然语言和数学语言 通用性强 可移植性好 input Entername name input Enterhoursworked hoursinput Enterpayrate rategrossPay hours ratefederalTax 02 grossPaysocSecTax 07 grossPaystateTax 06 grossPaynetPay grossPay federalTax socSecTax stateTaxprintname netPay 常见语言 BASIC PASCAL FORTRAN C 高级语言所编写的程序同样不能直接在计算机上执行 要转换成机器指令代码 两种转换方式 1 编译方式通过编译程序 编译 链接 将整个程序转换为机器语言 2 解释方式通过解释程序 逐行转换为机器语言 转换一行运行一行 编译方式 解释方式 4 面向对象的高级语言面向对象的程序设计方法 围绕真实世界的概念来组织模型 classDate public voidchangeDate intmonth intday intyear voiddisplayDate private intmonth intday intyear DatepayDay 常见的面向对象程序设计语言 VisualC VisualBasic Java 面向对象的程序设计方法的优点 问题求解更容易程序的编制 调试和维护更容易 11 33 30 算法的相关概念 一 什么是算法 算法是解决某类具体问题的方法 是解决问题的步骤序列二 什么是计算机算法 是指利用计算机解决问题的方法 简称算法 分为数值算法和非数值算法两大类 三 算法的主要特征 有效性 算法中的每一步骤都应当是可执行的 并能得到确定的结果 有穷性 算法应该在执行有限的步骤后结束 不能是无限的 确定性 组成算法的每一步骤应该有确定的语义 不能有任何歧义 有零个或多个输入 部分数据在操作之前需要通过外界赋值 称为输入 有一个或多个输出 算法的运算结果即是算法的输出 四 算法的主要因素 五 算法的表示方法 1 自然语言2 传统流程图3 结构化流程图4 N S流程图5 伪代码 1 自然语言表示算法 例 计算n 2 I 2 传统流程图表示算法 11 33 39 11 33 40 例 将求5 的算法用传统流程图表示 3 结构化流程图表示算法 1 顺序结构 1966年 Bohra和Jacopini提出了三种基本结构作为表示算法的基本单元 2 选择结构 又称选取结构 11 33 43 3 循环结构 又称重复结构 11 33 44 4 N S流程图描述算法 选择结构 循环结构 例 用N S流程图表示求5 的算法 5 伪代码描述算法 例 用伪代码表示求5 的算法 六 算法设计策略 1 枚举法枚举法也称为穷举法 其设计思想是 在有限的范围中 列举和检验所有可能的结果 从中找出那些符合要求的候选解作为问题的解 11 33 51 例 设有算式 ABCD CDC ABC 其中的A B C D均为一位非负整数 要求找出A B C D各值思路分析 设正整数A B C D A和C的取值范围应是 1 9 B和D的取值范围应是 0 9 分别对相应范围中的每一个数值进行检测 输出满足条件 1000 a 100 b 10 c d 100 c 10 d c 100 a 10 b c 的数值 11 33 52 算法描述 fora 1step1until9doforb 0step1until9doforc 1step1until9doford 0step1until9dox 1000 a 100 b 10 c dy 100 c 10 d cz 100 a 10 b cifx y zthen输出a b c dend 2 递推法递推法的设计思想是 利用问题本身所具有的一种递推关系求问题的解 即从已求得的规模为1 2 n 1的一系列解 构造出问题规模为n的解 例 计算n 思路分析 1 1 由1 2得2 由2 3得3 由 n 1 n得n 算法描述 f 1i 1whilei ndof f ii i 1printf 3 递归法递归法的设计思想是 为求解规模较大的问题 设法将它分解成规模较小的问题 然后从这些小问题的解方便地构造出大问题的解 并且这些规模较小的问题也能采用同样的分解和综合方法 分解成规模更小的问题 并从这些更小问题的解构造出规模较大问题的解 特别地 当规模N 1时 能直接得解 11 33 56 例 计算斐波那契数列的第n项值 思路分析 斐波那契数列为 0 1 1 2 3 即f 0 0f 1 1f n f n 1 f n 2 当n 1时 算法描述 callFibonacci n ifn 0thenreturn0ifn 1thenreturn1ifn 1thenreturnFibonacci n 1 Fibonacci n 2 4 分治法分治法的设计思想是 将一个难以直接解决的大问题 分割成一些规模较小的子问题 以便各个击破 分而治之 由分治法产生的子问题往往是原问题的较小模式 在这种情况下 反复应用分治手段 可以使子问题与原问题类型一致而其规模却不断缩小 最终使子问题缩小到很容易直接求出其解 这自然导致递归过程的产生 分治与递归像一对孪生兄弟 经常同时应用在算法设计之中 并由此产生许多高效算法 11 33 58 例 欲在按非降次序排列的n个元素a1 a2 an ai ai 1 中查找是否有与b相同的元素 七 算法复杂性分析 11 33 59 算法二 采用折半查找 二分查找 的方法 即先用位居 中点 的元素a n 2 与b比较 若b a n 2 则查找成功 若b a n 2 同时b a n 2 则在a1 a2 a n 2 1 中采用上述方法继续查找 否则在a n 2 1 a n 2 2 an中采用上述方法继续查找 这种算法显然要优越于前一种算法 因为最多也只需要比较log2n次 不同类型的问题有不同的算法同一类型的问题也有多种算法解决一个实际问题时 可能会有多种算法可供使用 我们需要对这些算法进行分析 选择最优的一个使用 八 结构化程序设计思想 结构化程序就是用高级语言表示的结构化算法 结构化程序设计的思路是 采用面向过程的程序设计方法 自顶向下 逐步细分 程序结构按功能划分为若干基本模块 各模块之间在功能上相对独立 每一模块内部均由顺序 选择和循环三种基本结构组成 总体结构基本由系统的功能分解构成 11 33 62 程序设计过程的简单示例 IPO图 用输入 Input 处理 Processing 输出 Output 来组织和总结问题分析结果的图表 处理项 处理过程中用到的中间值 例 Martin已经在Builder公司工作了4年 去年Martin的周薪提高了4 这样她目前周薪达到了250美元 下周Martin的周薪还要提高3 编程显示其下周涨薪后的周薪 分析 想要得到什么 下周涨薪后的周薪 新的周薪 怎么样才能得到 下周涨薪后的周薪 下周涨薪前的周薪 当前周薪 下周涨薪前的周薪 增长率要得到 下周涨薪后的周薪 需要知道什么 下周涨薪前的周薪 当前周薪 增长率 通过上面分析已确定本任务的输入 输出项 规划算法 建立数学模型 设计算法 怎么样求得 新的周薪 当前周薪 当前周薪 增长率算法 S1 输入当前周薪和增长率S2 计算周薪增长数目 当前周薪 增长