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

第一章算法初步1 1算法与程序框图1 1 1算法的概念 1 理解算法的概念 体会算法的思想 重点 2 掌握简单问题算法的表述 重点 难点 3 会写出解线性方程 组 的算法 2000春晚小品 钟点工 1 把冰箱门打开 2 把大象装进去 3 把冰箱门关上 把大象放进冰箱里需要几步 思考一 6 5 4 2 的计算步骤是什么 先进行括号里的运算 再算乘法 最后算加法 探究1 算法的概念 假设家中生火泡茶有以下几个步骤 a 生火b 将水倒入锅中c 找茶叶d 洗茶壶 茶碗e 用开水冲茶请选出一个最优方案 a abcdeb bacdec cadbed dcabe 广义的算法是指完成某项工作的方法和步骤 那么我们可以说洗衣机的使用说明书是操作洗衣机的算法 菜谱是做菜的算法等 到底什么是算法呢 思考二 b 算法 algorithm 一词出现于12世纪 指的是用阿拉伯数字进行算术运算的过程 在数学中 算法通常是指按照一定规则解决某一类问题的明确和有限的步骤 现在 算法通常可以编成计算机程序 让计算机执行并解决问题 据说英文algorithm来源于阿拉伯数学家花拉子米的拉丁译名algoritmi 算法的概念 明确性 有效性 有限性 1 算法定义的理解在数学中 现代意义上的 算法 通常是指可以用计算机来解决的某一类问题的程序或步骤 这些程序或步骤必须是明确和有效的 而且能够在有限步之内完成 2 算法的要求 1 写出的算法 必须能解决一类问题 例如解任意一个二元一次方程组 并且能重复使用 2 算法过程要能一步一步执行 每一步执行的操作 必须确切 不能含混不清 而且在有限步之内完成后能得出结果 提升总结 3 算法的基本特征明确性 算法的每一个步骤都是确切的 能有效执行且得到确定结果 不能模棱两可 有限性 算法应由有限步组成 至少对某些输入 算法应在有限多步内结束 并给出计算结果 有效性 算法从初始步骤开始 分为若干明确的步骤 每一步都只能有一个确定的继任者 只有执行完前一步才能进入到后一步 并且每一步都确定无误后 才能解决问题 不惟一性 求解某一个问题的算法不一定是惟一的 对于同一个问题可以有不同的算法 写出解方程组的步骤第一步 消元 2 得7x 11 第二步 解一元一次方程 解 得第三步 代入求解 将代入 得 写出解第二个方程组的算法 第一步 a2 a1得 a2b1 a1b2 y a2c1 a1c2 第二步 解 得第三步 将 带入 得 推广 问题1 这两个解方程组算法的比较 第一步 a2 a1得 a2b1 a1b2 y a2c1 a1c2 第二步 解 得第三步 将 代入 得 第一步 2 得7x 11 第二步 解 得第三步 将代入 得 解方程组第一步 取a1 3 b1 2 c1 3 a2 2 b2 1 c2 4 第二步 计算第三步 给出运算结果 问题2 你对以下的 算法 如何理解 问 要把大象装进冰箱 分几步 答 分三步 第一步 打开冰箱门 第二步 把大象装进冰箱 第三步 关上冰箱门 问题3 一位商人有9枚金币 其中有一枚略轻的假币 你能用天平 无砝码 将假币找出来吗 写出解决这一问题的算法 第一步 把9枚金币平均分成三组 每组三枚 第二步 先将其中的两组放在天平的两边 如果天平不平衡 那么假金币就在轻的那一组 如果天平左右平衡 则假金币就在未称量的那一组里 第三步 取出含假币的那一组 从中任取两枚金币放在天平两边进行称量 如果天平不平衡 则假金币在轻的那一边 若平衡 则未称的那一枚就是假币 问题4 有人对歌德巴赫猜想 任何大于4的偶数都能写成两个奇质数之和 设计了如下操作步骤 第一步 检验6 3 3 第二步 检验8 3 5 第三步 检验10 5 5 利用计算机无穷地进行下去 请问 利用这种程序能够证明猜想的正确性吗 这是一种算法吗 不能 不是 例1 设计一个算法 判断7是否为质数 算法分析 根据质数的定义 可以这样判断 依次用2 6除7 如果它们中有一个能整除7 则7不是质数 否则7是质数 根据以上分析 可写出如下算法 第一步 用2除7 得到余数1 所以2不能整除7 第二步 用3除7 得到余数1 所以3不能整除7 第三步 用4除7 得到余数3 所以4不能整除7 第四步 用5除7 得到余数2 所以5不能整除7 第五步 用6除7 得到余数1 所以6不能整除7 因此 7是质数 设计一个算法 判断35是否为质数 第一步 用2除35 得到余数1 所以2不能整除35 第二步 用3除35 得到余数2 所以3不能整除35 第三步 用4除35 得到余数3 所以4不能整除35 第四步 用5除35 得到余数0 所以5能整除35 因此 35不是质数 探究2 你能写出 判断整数n n 2 是否为质数 的算法吗 第一步 给定一个大于2的整数n 第二步 令i 2 第三步 用i除n 得到余数r 第四步 判断 r 0 是否成立 若是 则n不是质数 结束算法 否则 将i的值增加1 仍用i表示 第五步 判断 i n 1 是否成立 若是 则n是质数 结束算法 否则 返回第三步 想一想 什么是二分法 对于区间 a b 上连续不断且f a f b 0 x 例2 写出用 二分法 求方程x2 2 0 x 0 的近似解的算法 第一步 令f x x2 2 给定精确度d 第二步 确定区间 a b 满足f a f b 0 第三步 取区间中点第四步 若f a f m 0 则含零点的区间为 a m 否则 含零点的区间为 m b 将新得到的含零点的区间仍记为 a b 第五步 判断 a b d是否成立或f m 是否等于0 若是 则m是方程的近似解 否则 返回第三步 对于方程x2 2 0 x 0 给定d 0 005 此步骤也是求的近似值的一个算法 于是 开区间 1 4140625 1 41796875 中的实数都是当精度为0 005时的原方程的近似解 任意给定一个正实数 设计一个算法求以这个数为半径的圆的面积 第一步 输入任意一个正实数r 第二步 计算圆的面积s r2 第三步 输出圆的面积s 给出一个问题 设计算法时应注意的问题 1 认真分析问题 联系解决此问题的一般数学方法 2 综合考虑此类问题中可能涉及的各种情况 3 将解决问题的过程划分为若干个步骤 4 用简练的语言将各个步骤表示出来 总结提升 1 算法的有穷性是指 a 算法必须包含输出 b 算法中每个步骤都是可执行的 c 算法的步骤必须有限 d 以上说法均不对 解析 选c 算法通常是指按照一定规则解决某一类问题的明确和有限的步骤 c 2 写出解二元一次方程组的一个算法 第一步 2 2 1 得x 2 第二步 第三步 输出x y的值 解析 利用解方程组的步骤可得 将x 2代入 2 得y 4 答案 将x 2代入 2 得y 4 3 写出求1 2 3 100的一个算法 可运用公式1 2 3 n 直接计算 第一步 第二步 第三步输出计算结果 解析 第一步 取n 100 第二步 计算的值 答案 取n 100计算的值 4 你要乘火车去外地办一件急事 请你写出从自己房间出发到坐在车厢内的三步主要算法 第一步 去车站 第二步 买车票 第三步 凭票上车对号入座 5 任意给定一个大于1的正整数n 设计一个算法求出n的所有因数 第一步 依次以2 n 1 为除数去除n 检查余数是否为0 若是 则是n的因数 若不是 则不是n的因数 第二步 在n的因数中加入1和n 第三步 输出n的所有因数 知识结构 算法的概念