高中数学：1.1.1《算法的概念》课件（4）（新人教B版必修3）.ppt

1 1 1算法的概念 普通高中课程标准试验教科书人教a版数学必修3第一章算法初步 一位商人有9枚金币 其中有一枚略轻的假币 你能用天平 无砝码 将假币找出来吗 写出解决这一问题的算法 一 创设情境 第一步 把9枚金币平均分成三组 每组三枚 第三步 取出含假币的那一组 从中任取两枚金币放在天平两边进行称量 如果天平不平衡 则假金币在轻的那一边 若平衡 则未称的那一枚就是假币 第二步 先将其中的两组放在天平的两边 如果天平不平衡 那么假金币就在轻的那一组 如果天平左右平衡 则假金币就在未称量的那一组里 人鬼过河 现在河的岸边有三个人和三个鬼 河上只有一条小船 船上最多能坐两个 人 在河的任何一边 当鬼的个数比人多时 鬼就会吃掉人 请问如何才能使人和鬼都平安的到达对岸 解二元一次方程组的求解过程 并归纳求解步骤 解 第一步 第二步 解 3 得y 3 5 第三步 将y 3 5代入 1 得x 1 5 第四步 得到方程组的解 回顾 2 1 2得5y 3 3 写出解第二个方程组的算法 第一步 第二步 第三步 解 得 将 代入 得 变一变 第四步 得到方程组的解 二 新课研探 1 定义 算法 algorithm 一词出现于12世纪 指的是用阿拉伯数字进行算术运算的过程 在数学中 算法 通常是指按照一定规则来解决某一类问题的明确和有限的步骤 现在算法通常可以编成计算机程序 让计算机执行并解决问题 2 算法的特点 明确性 算法中的每一个步骤都是确切的 能有效的执行且得到确定的结果 不能模棱两可 你对以下的 算法 如何理解 问 要把大象装冰箱 分几步 2 算法的特点 明确性 算法中的每一个步骤都是确切的 能有效的执行且得到确定的结果 不能模棱两可 有限性 算法应由有限步组成 必须在有限操作之后停止 并给出计算结果 有人对歌德巴赫猜想 任何大于4的偶数都能写成两个奇质数之和 设计了如下操作步骤 第一步 检验6 3 3第二步 检验8 3 5第三步 检验10 5 5 利用计算机无穷地进行下去 请问 利用这种程序能够证明猜想的正确性吗 这是一种算法吗 2 算法的特点 明确性 算法中的每一个步骤都是确切的 能有效的执行且得到确定的结果 不能模棱两可 有序性 算法从初始步骤开始 分为若干明确的步骤 每一步都只能有一个确定的继任者 只有执行完前一步才能进入到后一步 并且每一步都确定无误后 才能解决问题 不唯一性 求解某一个问题的解法不一定是唯一的 对于同一个问题可以有不同的解法 但算法有优劣之分 好的算法是我们追求的目标 普适性 写出的算法必须能解决一类问题 并且能重复使用 这是设计算法的一条基本原则 这样才能使算法更有价值 有限性 算法应由有限步组成 必须在有限操作之后停止 并给出计算结果 4 任意给定一个大于2的整数n 试设计一个算法 对n是否为质数做出判定 例1 1 设计一个算法 判断7是否为质数 2 设计一个算法 判断35是否为质数 3 设计一个算法 判断53是否为质数 答案 第一步 给定大于2的整数n第二步 令i 2第三步 用i除n 得余数r第四步 判断 r 0 是否成立 若是 则n不是质数 结束算法 若不是将i的值增加1 仍用i表示 第五步 判断 i n 1 是否成立 若是 则n是质数 结束算法 否则返回第三步 小结 算法实际上就是解决某一类问题的步骤和方法 在解决问题时形成的规律性东西 按照算法的规则与步骤一步一步地去做 最终解决问题 1 任意给定一个正实数 设计一个算法求以这个数为半径的圆的面积 第一步 输入任意一个正实数r 第二步 计算圆的面积 s r2 第三步 输出圆的面积s 三 练习 2 任意给定一个大于1的正整数n 设计一个算法求出n的所有因数 答案1 第一步 依次以2 n 1 为除数去除n 检查余数是否为0 若是 则是n的因数 若不是 则不是n的因数 第二步 在n的因数中加入1和n 第三步 输出n的所有因数 答案2 第一步 给定大于1的整数n第二步 令i 2第三步 用i除n 得余数r第四步 判断 r 0 是否成立 若是 则i是n的因数 输出i 第五步 将i的值增加1 仍用i表示 第六步 判断 i n 1 是否成立 若是 再输出n和1 结束算法 否则返回第三步 在中央电视台幸运52节目中 有一个猜商品价格的环节 竟猜者如在规定的时间内大体猜出某种商品的价格 就可获得该件商品 现有一商品 价格在0 8000元之间 采取怎样的策略才能在短的时间内说出正确 大体上 的答案呢 第一步 报 4000 第二步 若主持人说高了 第三步 重复第二步的报数方法取中间数 直至得到正确结果 说明答案在0 4000之间 就报 2000 否则 答数在4000 8000之间 报 6000 例2用二分法设计一个求方程x2 2 0 x 0 的近似解的算法 算法分析 回顾二分法的解方程的过程 并假设所求近似根与准确解的差的绝对值不超过0 005 则不难设计出以下步骤 第一步 令f x x2 2 给定精确度d 第二步 令m a b 2 判断f m 是否为0 若是 则m为所求 结束算法 若否 则继续判断f a f m 大于0还是小于0 第三步 第四步 若f a f m 0则含零点的区间为 a m 否则为 m b 将新得到的含零点的区间仍记为 a b 第五步 判断 a b 0 005是否成立 若是 则a b之间的任意取值均为满足条件的近似根 若否 则返回第三步 确定区间 a b 满足f a f b 0 1 知识结构 算法的概念 算法的步骤 课堂小结 2 算法的特点 明确性 有限性 有序性 不唯一性 普适性 3 设计算法的注意事项 1 认真分析问题 联系解决此问题的一般数学方法 2 综合考虑此类问题中可能涉及的各种情