高中数学 第二章 算法初步本章归纳总结课件 北师大版必修3.ppt

成才之路 数学 路漫漫其修远兮吾将上下而求索 北师大版 必修3 算法初步 第二章 本章归纳总结 第二章 1 算法初步 1 算法的定义 在解决某些问题时 需要设计出一系列可操作或可计算的步骤 通过实施这些步骤解决问题 通常把这些步骤称为解决这类问题的算法 2 算法的特征 有穷性 确定性 顺序性 不唯一性 普适性 3 算法的三种描述方法 自然语言 流程图 程序语言 2 排序问题 1 排序 根据某种要求把被查询的对象用数字 或者符号 表示出来 并把数字按大小排列 2 有序列直接插入顺序 将新数据与原有序列中的数据从右到左依次进行比较 直到发现某一数据小于等于新数据 把新数据插入到此数据的右边 若新数据小于原有序列中所有数据 则把新数据插入到原有序列的最左边 3 折半插入排序 对于一个有序列 先将新数据与该有序列中的 中间位置 的数据进行比较 如果新数据小于 中间位置 的数据 则新数据插入的位置应该在最靠左边的一半 如果新数据等于 中间位置 的数据 则将新数据插入到 中间位置 的数据的右边 如果新数据大于 中间位置 的数据 则新数据插入的位置应该在靠右边的一半 反复进行这种比较直到确定新数据的位置 3 算法的三种基本结构 1 顺序结构 按照步骤依次执行的一个算法 称为具有顺序结构的算法 或者称为算法的顺序结构 如下图表示的是顺序结构的示意图 简单If语句 If条件Then语句1Else语句2EndIf复合If语句 If条件1Then 语句1ElseIf条件2Then语句2Else语句3EndIfEndIf 设计具体数学问题的算法 实际上就是寻求一类问题的算法 它可以通过计算机来完成 设计算法的关键是把过程分解成若干个明确的步骤 然后用计算机能接受的 语言 准确地描述出来 设计算法时要注意 1 应当先建立过程模型 也就是找到解决问题的方案 再把它细化为一个连续的步骤 从而设计出算法 2 算法的顺序性和普遍性 步骤的顺序不能颠倒 设计出的算法需具有解决一类问题的功能 用自然语言设计算法 算法的设计主要包括数值性问题的算法和非数值性问题的算法 对于数值性问题 如解方程 或方程组 解不等式 或不等式组 数的累加 累乘等一类问题的描述 一般可通过构建相应的数学模型借助数学计算方法 将解题过程条理化 分成几个顺序明确的步骤即可写出算法 对于非数值性问题 如排序 查找 变量替换 文字处理等 需要先建立过程模型 再通过模型进行算法设计与描述 算法设计与一般意义上的解决问题不同 它是对一类问题的一般解法的抽象与概括 它要借助一般的问题解决方法 又要包含这类问题的所有可能情形 它往往是把问题的解法划分为若干个可执行的步骤 有时甚至是重复多次 但最终都必须在有限个步骤之内完成 解法二 算法步骤如下 1 t 2 2 i 4 3 t t i 4 i i 2 5 如果i不大于12 返回重新执行第三步 否则输出t的值就是所求的结果 点评 从这两个算法中可以发现 解法一虽然正确 但比较繁琐 当连乘的数较多时 此种算法就显得更加冗长了 解法二不仅形式上显得简练 而且具有通用性和灵活性 对于多个有规律的数据运算尤为合适 1 算法流程图是用规定的框图和流程线来准确 直观 形象地表示算法的图形 画框图之前可以通过对问题的分析 建立相应的数学模型或过程模型 设计出合理有效的算法 然后分析算法的逻辑结构 根据逻辑结构画出相应的算法流程图 2 如果设计的算法框图较为复杂 就要采取 逐步求精 的思想 先将问题中的简单部分明确出来 再逐步对复杂部分进行细化 然后一步一步向前推进 算法流程图及其画法 规范解答 算法流程图如图所示 解决同一个问题 可以有多种算法 那么就有多种算法流程图和程序 因此高考试题中通常不会考查画算法框图或编写程序 由于学习本章的目的是体会算法的思想 所以已知算法流程图或程序 判断其结果是高考考查本章知识的主要形式 这也是课程标准和考试说明对本章的要求 其判断方法是具体运行所给的算法流程图或程序 即可得到算法的结果 如何判断算法的结果 已知一个算法流程图 要求将其设空的某个关键步骤补充完整 或已知一个流程图 要求我们判断其功能或求输出结果是一种重要题型 解决这类问题需要理清所要实现的算法的结构特点及流程规则 读懂算法流程图 完善框图所缺的条件 规范解答 本题考查了流程图 该程序依次如下运行 初值 S 1 k 1 k 2 S 4 k 3 S 11 k 4 S 26 k 5 S 57最后输出S 57 判断框中应填k 4 答案 A 答案 C 解析 注意到判断框中应是保证恰好是10名学生 再注意到走出判断框的结果将是10个数的和 于是选C 自然语言表述的算法和算法流程图是程序设计的基础 算法流程图侧重于直观性 而程序则倾向于计算机执行的实用性 编写程序的基本方法是 自上而下 逐步求精 即首先把一个复杂的大问题分解成若干个相对独立的小问题 如果小问题仍较复杂 则可以把这些小问题再继续分解成若干个子问题 这样不断分解 便可使得小问题或子问题简单到能够直接用程序的三种基本结构表达为止 然后 对应每一个小问题或子问题编写出一个功能上相对独立的程序模块来 每个模块各个击破 最后再统一组装 问题便可得到解决 程序语句的考查 规范解答 算法框图如图所示 A 17B 19C 21D 23 答案 C 解析 这是用DoLoop语句编写的程序 按DoLoop语句的运行程序可知最后一次执行循环体时S 2 7 2 3 21 一 选择题1 执行如图所示的程序框图 则输出s的值 A 10B 17C 19D 36 答案 C 解析 本题考查算法的循环结构和层层分析法 k 2 S 2 k 3 S 5 k 5 S 10 k 9 S 19 k 17时 结束循环 此时S 19 注意k与S循环时相匹配的取值 2 执行如图所示的程序框图 输出的S值为 A 1B 3C 7D 15 答案 C 解析 本题考查了程序框图的有关概念 S1 k 0 S 0 S2 S 20 1 k 1 S3 S 1 21 3 k 2 S4 S 3 22 7 k 3 S5 输出S 7 3 2015 北京理 3 执行如图所示的程序框图 输出的结果为 A 2 2 B 4 0 C 4 4 D 0 8 答案 B 解析 运行程序 x 1 y 1 k 0 s 1 1 0 t 1 1 2 x 0 y 2 k 0 1 1 因为1 3不满足 s 2 t 2 x 2 y 2 k 2 因为2 3不满足 s 4 t 0 x 4 y 0 k 3 因为3 3满足 输出 4 0 4 如图 该流程图是求函数f x x2 3x 5 当x 0 3 6 9 60 时函数值的一个流程图 则 处应填 A x x 3B x 3xC 3x xD x 3 x 答案 A 解析 给出的数为0 3 6 9 60 后一个数比前一个数大3 5 执行下面语句的过程中 执行循环体的次数是 i 1Doi i 1i i iLoopWhilei 10输出i A 2B 0C 3D 1 答案 A 解析 算法语句的执行过程是第一次执行循环体 i 1i 1 1 2i 2 2 4i 4 10成立第二次执行循环体 i 4i 4 1 5i 5 5 25i 25 10不成立退出循环 共执行循环体2次 二 填空题6 阅读下面的算法语句 如果输入x 2 则输出结果为 输入x Ifx0Theny 2 x 3Else y 0EndIfEndIf输出y 答案 5 7 如果执行如图所示的程序框图 输入x 4 5 则输出的数i 答案 4 解析 本题考查程序框图 循环结构等算法知识 i 1 x 4 5 1 3 5 i 2 x 3 5 1 2 5 i 3 x 2 5 1 1 5 i 4 x 1 5 1 0 5 0 5 1 输出i 4 8 执行下面的程序框图 若输入的x的值为1 则输出的n的值为 答案 3 解析 由x2 4x 3 0 解得1 x 3 当x 1时 满足1 x 3 所以x 1 1 2 n 0 1 1 当x 2时 满足1 x 3 所以x 2 1 3 n 1 1 2 当x 3时 满足1 x 3 所以x 3 1 4 n 2 1 3 当x 4时 不满足1 x 3 所以输出n 3 三 解答题9 给出30个数 1 2 4 7 其规律是 第1个数是1 第2个数比第1个数大1 第3个数比第2个数大2 第4个数比第3个数大3 依此类推 要计算第30个数的大小 现在已给出了该问题算法的流程图 如下图所示 1 请在图中判断框 处和执行框 处填上合适的语句 使之能完成该题算法功能 2 根据流程图写出程序 解析 1 中应填写 i 30 中应填写 P i 2 程序如下 P 1S 0i 1DoS S PP ii i 1LoopWhilei 30输出S