高中数学 1.1.1算法的概念课件 新人教A版必修3.ppt

算法的概念 在中央电视台幸运52节目中 有一个猜商品价格的环节 竟猜者如在规定的时间内大体猜出某种商品的价格 就可获得该件商品 现有一商品 价格在0 8000元之间 采取怎样的策略才能在短的时间内说出正确 大体上 的答案呢 第一步 报 4000 第二步 若主持人说高了 说明答案在0 4000之间 就报 2000 否则 答数在4000 8000之间 报 6000 第三步 重复第二步的报数方法取中间数 直至得到正确结果 先去括号 再乘除 后加减 1 什么是算法呢 2 两个大人和两名儿童一起渡河 渡口只有一条小船 一次只能渡过一个大人或两名儿童 他们四人都会划船 但都不会游泳 请你帮他们设计一个渡河方案 什么是算法呢 第一步 两个小孩同船渡过河去 第二步 一个小孩划船回来 第三步 一个大人独自划船渡过河去 第四步 对岸的小孩划船回来 第五步 两个小孩再同船渡过河去 第六步 一个小孩划船回来 第七步 余下的一个大人独自划船渡过河去 第八步 对岸的小孩划船回来 第九步 两个小孩再同船渡过河去 简单地说 算法就是解决问题的程序或步骤 什么是算法呢 一般地 按照一定规则解决某一类问题的明确和有限的步骤称为算法 algorithm 按照这样的理解 我们可以设计出很多具体数学问题的算法 下面看几个例子 所谓 算法 就是解题方法的精确描述 从更广义的角度来看 并不是只有 计算 的问题才有算法 日常生活中处处都有 如乐谱是乐队演奏的算法 菜谱是做菜肴的算法 珠算口诀是使用算盘的算法 它是解决某一类问题的程序或步骤 第一步 第二步 第三步 消元 解一元一次方程 2 得 解 得 代入求解 将代入 得 写一写 写出解第二个方程组的算法 第一步 第二步 第三步 解 得 将 代入 得 变一变 第一步 第二步 第三步 解 得 将 代入 得 解 得 一位商人有9枚金币 其中有一枚略轻的假币 你能用天平 无砝码 将假币找出来吗 写出解决这一问题的算法 第一步 把9枚金币平均分成三组 每组三枚 先将其中的两组放在天平的两边 如果天平不平衡 那么假金币就在轻的那一组 如果天平左右平衡 则假金币就在未称量的那一组里 取出含假币的那一组 从中任取两枚金币放在天平两边进行称量 如果天平不平衡 则假金币在轻的那一边 若平衡 则未称的那一枚就是假币 第二步 第三步 有人对歌德巴赫猜想 任何大于4的偶数都能写成两个奇质数之和 设计了如下操作步骤 第一步 检验6 3 3 第二步 检验8 3 5 利用计算机无穷地进行下去 请问 利用这种程序能够证明猜想的正确性吗 第三步 检验10 5 5 这是一种算法吗 在数学中 现代意义上的 算法 通常是指可以用计算机来解决的某一类问题的程序或步骤 这些程序或步骤必须是明确和有效的 而且能够在有限步之内完成 2 算法的要求 1 写出的算法 必须能解决一类问题 例如解任意一个二元一次方程组 并且能重复使用 2 算法过程要能一步一步执行 每一步执行的操作 必须确切 不能含混不清 而且在有限步之内完成后能得出结果 1 算法定义的理解 3 算法的基本特征 明确性 算法对每一个步骤都有确切的 能有效执行且得到确定结果的 不能模棱两可 有效性 算法从初始步骤开始 分为若干明确的步骤 每一步都只能有一个确定的继任者 只有执行完前一步才能进入到后一步 并且每一步都确定无误后 才能解决问题 有限性 算法应由有限步组成 至少对某些输入 算法应在有限多步内结束 并给出计算结果 不唯一性 求解某一个问题的解法不一定是唯一的 对于同一个问题可以有不同的解法 例1 任意给定一个整数n n 2 若用i表示2 n 1 的任意一个整数 试设计一个程序或步骤对n是否为质数做出判定 第一步 给定大于2的整数n 第三步 用i除n 得到余数r 第二步 令i 2 第四步 判断 r 0 是否成立 若是 则n不是质数 结束算法 否则 将i的值增加1 仍用i表示 第五步 判断 i n 1 是否成立 若是 则n是质数 结束算法 否则 返回第三步 例2 用二分法设计一个求方程x2 2 0的近似根的算法 第一步 令f x x2 2 给定精确度d 第三步 令m 判断f m 是否为0 若是 则m为所求 若否 则继续判断f a f m 大于0还是小于0 算法分析 回顾二分法解方程的过程 并假设所求近似根与精确解的差的绝对值不超过0 005 则不难设计出以下步骤 第二步 确定区间 a b 满足f a f b 0 第四步 若f a f m 0 则零点的区间为 a m 否则 含零点的区间为 m b 将得到的含零点的区间仍记为 a b 第五步 判断 a b 0 005是否成立 若是 则a或b 或任意值 为满足条件的近似根 若否 则返回第二步 于是开区间中的实数都是满足假设条件的原方程的近似根 1 任意给定一个正实数 设计一个算法求以这个数为半径的圆的面积 第一步 输入任意一个正实数r 第二步 计算圆的面积 s r2 第三步 输出圆的面积s 课堂练习 2 你要乘火车去外地办一件急事 请你写出从自己房间出发到坐在车厢内的三步主要算法 第一步 去车站 第二步 买车票 第三步 凭票上车对号入座 3 任意给定一个大于1的正整数n 设计一个算法求出n的所有因数 第一步 依次以2 n 1 为除数去除n 检查余数是否为0 若是 则是n的因数 若不是 则不是n的因数 第二步 在n的因数中加入1和n 第三步 输出n的所有因数 p5练习2 1 知识结构 算法的概念 算法的步骤 算法的特点 算法 课堂小结 2 算法的特点 思路简单清晰 叙述复杂 步骤繁琐 计算量大 完全依靠人力难以完成 而这些恰恰就是计算机的特长 它能不厌其烦地完成枯燥的 重复的繁琐的工作 正因为这些 现代算法的作用之一就是使计算机代替人完成某些工作 这也是我们学习算法的重要原因之一 课堂小结 3 设计算法的注意事项 1 认真分析问题 联系解决此问题的一般数学方法 2 综合考虑此类问题中可能涉及的各种情况 3 借助有关的变量或参数对算法加以表达 4 将解决问题的过程划分为若干个步骤 5 然后用简练的语言将各个步骤表示出来 现有有限个实数 怎样从中找出最大值 先假定这些实数中的第一个数为 最大值 将这些实数中的下一个数与 最大值 比较 如果它大于此 最大值 这时就假定 最大值 是这个实数 如果还有其他实数 重复第二步 一直到没有可比的数为止 这时假定的 最大值 就是这有