c语言 第2章算法.ppt

第二章算法和程序设计方法学 掌握算法的概念理解算法的特点掌握流程图 N S图表示算法的方法了解程序设计方法学理解结构化程序设计方法了解面向对象程序设计方法 程序 算法 数据结构 程序设计方法 语言环境 灵魂 加工对象 工具 结构化程序设计 顺序 循环 选择 描述数据的类型 组织形式 描述对数据的操作步骤 程序是用来控制计算机操作的代码 目的是利用计算机对现实问题求解 算法的概念 做事情都有 方法 步骤 顺序 决定事情成败 1 算法 为解决一个问题而采用的方法和步骤 就称为算法 选择合适的算法非常重要 2 算法分两类 数值算法和 非数值算法 求数值解 成熟 事务管理 广泛 3 算法特性 有穷性 确定性 有零个或多个输入 有一个或多个输出 有效性4 算法的描述 算法的描述方法有多种归纳为两类 1 文字2 图形 符号 算法的描述方法 常用的算法描述方法1 带序号的自然语言描述易懂 不直观 不严格2 流程图 灵活 自由 形象 直观 可表示任何算法 流程图包括以下几个组成部分 表示相应操作的框 带箭头的流程线 框内外必要的文字 3 N S图 盒图 完全去掉了带箭头的流程线 算法的所有处理步骤都写在一个大的矩形框中 表示简单 符合结构化思想 4 伪代码 用介于自然语言与计算机语言之间的文字及符号来描述算法 方便 易懂 便于向计算机语言过渡 A 顺序 判断 循环 当型循环 直到型循环 B 例1 计算 写出其算法 自然语言描述 0 S单元1 n单元S n S单元n 1 n单元判断n 100 是转3 否转6输出S的值 流程图描述 开始 0 S 1 n S n S n 1 n n 100 输出S 结束 T F N S图描述 0 S 1 n 输出S的值 n 100 S n S n 1 n 伪代码描述 0 S1 nifn 100S n Sn 1 nprintS 思考 1 如果题目改成求 1 1 3 5 99 2 1 3 5 99 3 1 1 2 1 3 1 100 4 1 2 3 100 相应算法应做如何修改 2 如果步骤1 2改成1 S单元2 n单元这样会带来什么样的变化 程序设计方法学简介 1 程序设计方法学 1 基本研究目标通过对程序本质属性的研究来提高程序的效率 并保证程序的正确性 说明什么样的程序是一个 优秀 的程序 怎样才能设计出 优秀 的程序 2 程序设计过程分析实际问题并抽象 利用数学建模技术构建问题的数学模型 借助计算方法和数据模型构造合适数据结构 进而设计算法 最后借助计算机语言实现算法形成程序 3 主要程序设计方法结构化程序设计方法面向对象程序设计方法 结构化程序设计方法 1 概况 1 1966年提出三种基本结构 用这三种结构作为表示一种良好算法的基本单元 顺序 选择 循环 2 基本思想 任何程序都可以用三种基本结构表示 由三种基本结构反复嵌套构成的程序叫结构化程序 3 采用 自顶向下 逐步求精 的程序设计方法 4 采用 单入口单出口 的控制结构 5 特点 模块化 层次化 逐步求精 a 3 b 4 c a b 三种基本结构顺序结构 操作步骤按书写的顺序执行 选择结构 分支结构 二分支选择结构 多分支选择结构 if x 0 y sin x x elsey 1 注 A B A1 An可以是一个简单语句 也可以是一个基本结构 循环结构 根绝条件P决定是否重复执行循环体中的操作 当型循环结构先判断 后执行 直到型循环结构先执行 后判断 两者的区别 A循环体执行的次数 注意 1 流程图中无专门针对循环的符号 2 流程图中箭头指向表明算法执行顺序 与画法无关 当型循环 sum 0 n 1 while n 100 sum n n 直到型循环 sum 0 n 1 Do sum n n while n 100 对应C语言程序段 注意 C中一般不使用直到型循环 结构化程序设计过程 1 确定算法 分析问题 建立数学模型 将大问题模块化 层次化 逐步求精 写出算法描述 2 编写程序 用计算机语言写出实现算法的程序3 上机调试 输入 编辑 程序编译 连接 执行程序输出结果 例如 计算并打印计算机专业12级所有学生C语言成绩平均分 计算并打印平均分 计算平均分 打印平均分 sum 0 累加器清零 n 0 计数器清零 逐个读入分数x 且sum sum xn n 1 计数 计算平均分aver sum n 例 张丘建 算经 中提出 百鸡问题 鸡翁一值钱五 鸡母一值钱三 鸡雏三值钱一 百钱买百鸡 问鸡翁 母 雏各几何 体会编程步骤 1 分析 cocks hens chickens 1005 cocks 3 hens chickens 3 100其中 0 cocks 19 0 hens 33 0 chickens 100思路 依次取cocks的值域中的值 然后求其余两数 看是否合乎题意 累试法 枚举法 遍历法 一 程序设计过程 1 已知 百钱买百鸡 求 鸡翁 母 雏各几何 2 数学模型 cocks hens chickens 1005 cocks 3 hens chickens 3 100其中 0 cocks 19 0 hens 33 0 chickens 100 3 算法思路 依次取cocks的值域中的值 然后求其余两数 看是否合乎题意 累试法 枚举法 遍历法 算法描述 cocks 0当cocks 19时 找满足题意的hens chickens数cocks加1 细化 cocks 0当cocks 19时 hens 0当hens 33时 找满足题意的chickens数hens加1 cocks加1 细化 cocks 0当cocks 19时 hens 0当hens 33时 Chickens 100 cocks hens如果5 cocks 3 hens chickens