高中数学 第二章 算法初步 1 算法的基本思想课件 北师大版必修3.ppt

第二章算法初步 1算法的基本思想 学习目标1 了解算法的含义 体会算法的思想 能够用自然语言叙述算法 2 掌握正确的算法应满足的要求 3 学会将一整数分解成素因数之积 会设计求两整数的最大公因数的算法 了解 韩信点兵 问题及二分法求方程近似解 题型探究 问题导学 内容索引 当堂训练 问题导学 有一碗酱油 一碗醋和一个空碗 现要把两碗盛的物品交换一下 试用自然语言表述你的操作方法 思考 知识点一算法的概念 答案 先把醋倒入空碗 再把酱油倒入原来盛醋的碗 最后把倒入空碗中的醋倒入原来盛酱油的碗 就完成了交换 梳理一般地 算法是解决某类问题的一系列 只要按照这些步骤执行 都能使问题得到解决 一般来说 用算法解决问题 都是可以利用帮助完成的 同一个问题可能存在多种算法 一个算法也可以解决某一类问题 步骤或程序 计算机 知识点二算法的特点 思考 设想一下电脑程序需要计算无限多步 会怎么样 若有无限步 必将陷入死循环 解决不了问题 故算法必须在有限步内解决问题 答案 梳理一般地 算法的特点有 1 有穷性一个算法应包括的操作步骤 能在执行有穷的操作步骤之后 2 确定性算法的计算规则及相应的计算步骤必须是唯一确定的 3 可行性算法中的每一个步骤都是可以在的时间内完成的基本操作 并能得到的结果 有限 结束 确定 有限 题型探究 例1在电视台的某个娱乐节目中 要求参与者快速猜出物品价格 主持人出示了一台价值在1000元以内的随身听 并开始了竞猜 下面是主持人和参与者之间的一段对话 参与者 800元 主持人 高了 参与者 400元 主持人 低了 参与者 600元 主持人 低了 试把参与者的竞猜策略概括成一系列的步骤 类型一生活中的算法案例 解答 1 报出首次价格t1 2 根据主持人的回答确定价格区间 1 若报价小于商品价格 则商品的价格区间为 t1 1000 2 若报价大于商品价格 则商品的价格区间为 0 t1 3 若报价等于商品价格 则游戏结束 3 如果游戏没有结束 则报出上面确定的价格区间的中点t2 按照上述方法 继续判断 直到游戏结束 像这样的一系列步骤通常称为解决这个问题的一个算法 生活中有很多蕴含算法思想的案例 反思与感悟 跟踪训练1一个大人和两个小孩一起渡河 渡口只有一条小船 每次只能渡1个大人或两个小孩 他们三人都会划船 但都不会游泳 试问他们怎样渡过河去 请写出一个渡河方案 解答 1 两个小孩同船过河去 2 一个小孩划船回来 3 一个大人划船过河去 4 对岸的小孩划船回来 5 两个小孩同船渡过河去 类型二数学中的算法思想 例2设计一个算法 求840与1764的最大公因数 解答 算法步骤如下 1 先将840进行素因数分解 840 23 3 5 7 2 然后将1764进行素因数分解 1764 22 32 72 3 确定它们的公共素因数 2 3 7 4 确定公共素因数的指数 公共素因数2 3 7的指数分别为2 1 1 5 最大公因数为22 31 71 84 以上这个算法的思想具有一般性 它可以帮助设计求三个或者三个以上正整数的最大公因数的算法 反思与感悟 跟踪训练2设计一个算法 求98与63的最大公因数 解答 算法步骤如下 1 先将98进行素因数分解 98 2 72 2 然后将63进行素因数分解 63 32 7 3 确定它们的公共素因数 7 4 确定公共素因数的指数 公共素因数的指数是1 5 最大公因数为7 例3 韩信点兵 问题韩信是汉高祖刘邦手下的大将 他英勇善战 智谋超群 为建立汉朝立下了汗马功劳 据说他在点兵的时候 为了保住军事机密 不让敌人知道自己部队的实力 采用下述点兵方法 先令士兵从1 3报数 结果最后一个士兵报2 再令士兵从1 5报数 结果最后一个士兵报3 又令士兵从1 7报数 结果最后一个士兵报4 这样 韩信很快就算出了自己部队士兵的总人数 请设计一个算法 求出士兵至少有多少人 解答 算法步骤如下 1 首先确定最小的满足除以3余2的正整数 2 2 依次加3就得到所有除以3余2的正整数 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 3 在上列数中确定最小的满足除以5余3的正整数 8 4 然后依次加上15 得到8 23 38 53 不难看出 这些数既满足除以3余2 又满足除以5余3 5 在第4步得到的一列数中找出满足除以7余4的最小数53 这就是我们要求的数 在完成上述步骤后 就找到了所求的数53 这5个步骤称为解决 韩信点兵 问题的一个算法 反思与感悟 跟踪训练3在例3中 我们颠倒一下3 5 7的顺序 请再设计一个算法 解答 算法步骤如下 1 首先确定最小的除以7余4的正整数 4 2 依次加7就得到所有除以7余4的正整数 4 11 18 25 32 39 46 53 60 3 在第2步得到的一列数中确定最小的除以5余3的正整数 18 4 然后依次加上35 得到18 53 88 5 在第4步得到的一列数中找出最小的满足除以3余2的正整数 53 类型三用二分法求方程近似解 例4求方程x3 x2 1 0在 0 1 上的近似解 精度为0 1 解答 根据上述分析 可以通过下列步骤求得方程的近似解 设f x x3 x2 1 1 因为f 0 1 f 1 1 f 0 f 1 0 1 5 取 0 5 1 的区间中点0 75 6 计算f 0 75 0 015625 7 由于f 0 75 f 1 0 1 8 取 0 75 1 的区间中点0 875 9 计算f 0 875 0 435546875 10 由于f 0 75 f 0 875 0 1 11 取 0 75 0 875 的区间中点0 8125 12 计算f 0 8125 0 196533203125 13 由于f 0 75 f 0 8125 0 可得新的有解区间 0 75 0 8125 0 8125 0 75 0 0625 0 1 所以 区间 0 75 0 8125 中的任一数值 都可以作为方程的近似解 二分法求方程近似解的基本思想 逐渐缩小有解区间的长度 直到满足精度的要求 虽然看似烦琐 但很适合计算机执行 反思与感悟 跟踪训练4用二分法设计一个求方程x2 2 0的近似正根的算法 精度为0 05 解答 1 因为f 1 1 f 2 2 f 1 f 2 0 05 2 取 1 2 的中点1 5 3 计算f 1 5 0 25 4 由于f 1 f 1 5 0 05 5 取 1 1 5 的中点1 25 6 计算f 1 25 0 4375 7 由于f 1 25 f 1 5 0 05 当得到新的有解区间 1 40625 1 4375 时 由于 1 4375 1 40625 0 03125 0 05 该区间精度已满足要求 所以取区间 1 40625 1 4375 的任一数值 都可以作为方程的一个近似解 当堂训练 1 下列关于算法的说法 正确的个数为 求解某一类问题的算法是唯一的 算法必须在有限步操作之后停止 算法的每一步操作必须是明确的 不能有歧义或模糊 算法执行后一定产生确定的结果 a 1b 2c 3d 4 答案 解析 由于算法具有有穷性 确定性 输出性等特点 所以 正确 而解决某类问题的算法不一定唯一 所以 错误 2 3 4 1 答案 解析 由算法过程可知 m为三数之和 n为这三数的平均数 故选d 2 3 4 1 3 看下面的四段话 其中不是解决问题的算法是 1 从济南到北京旅游 先坐火车 再坐飞机抵达 2 解一元一次方程的步骤是去分母 去括号 移项 合并同类项 系数化为1 3 方程x2 1 0有两个实根 4 求1 2 3 4 5的值 先计算1 2 3 再计算3 3 6 6 4 10 10 5 15 最终结果为15 2 3 4 1 答案 解析 由于 3 不是解决某一类问题的步骤 故 3 不是解决问题的算法 3 4 已知直角三角形两直角边长为a b 求斜边长c的一个算法分下列三步 1 计算c 2 输入直角三角形两直角边长a b的值 3 输出斜边长c的值 其中正确的顺序是 答案 解析 算法的步骤是有先后顺序的 第一步是输入 最后一步是输出