高中数学 第一章 算法初步 1.1.1 算法的概念课件1 新人教A版必修3.ppt

第一章算法初步1 1算法与程序框图1 1 1算法的概念 1 一个农夫带着一只狼 一只山羊和一篮蔬菜要过河 但只有一条小船 乘船时 农夫只能带一样东西 当农夫在场的时候 这三样东西相安无事 一旦农夫不在 狼会吃羊 羊会吃菜 请设计一个方案 使农夫能安全地将这三样东西带过河 注意事项 农夫一次只能运一样东西 如果农夫不在旁边的话 狼会吃羊 羊会吃菜 我们该怎样帮帮农夫呢 1 理解算法的概念 体会算法的思想 重点 2 掌握简单问题算法的表述 重点 难点 3 会写出解线性方程 组 的算法 提示 先进行括号里的运算 再算乘法 最后算加法 探究 算法的概念 思考一 6 5 4 2 的计算步骤是什么 假设家中生火泡茶有以下几个步骤 a 生火b 将水倒入壶中c 找茶叶d 洗茶壶 茶碗e 用开水冲茶请选出一个最优方案 注意 有些工作可以同时进行 a abcdeb bacdec cadbed dcabe 广义的算法是指完成某项工作的方法和步骤 那么我们可以说洗衣机的使用说明书是操作洗衣机的算法 菜谱是做菜的算法等 到底什么是算法呢 思考二 b 算法的概念 算法 algorithm 一词出现于12世纪 指的是用阿拉伯数字进行算术运算的过程 在数学中 算法通常是指按照一定规则解决某一类问题的明确和有限的步骤 现在 算法通常可以编成计算机程序 让计算机执行并解决问题 1 算法定义的理解在数学中 现代意义上的 算法 通常是指可以用计算机来解决的某一类问题的程序或步骤 这些程序或步骤必须是明确和有效的 而且能够在有限步之内完成 提升总结 2 算法的基本特征明确性 算法的每一个步骤都是确切的 能有效执行且得到确定结果 不能模棱两可 有限性 算法应由有限步组成 至少对某些输入 算法应在有限多步内结束 并给出计算结果 有效性 算法从初始步骤开始 分为若干明确的步骤 每一步都只能有一个确定的继任者 只有执行完前一步才能进入到后一步 并且每一步都确定无误后 才能解决问题 不惟一性 求解某一个问题的算法不一定是惟一的 对于同一个问题可以有不同的算法 写出解方程组的步骤第一步 消元 2 得7x 11 第二步 解一元一次方程 解 得第三步 代入求解 将代入 得 写出解第二个方程组的算法 第一步 a2 a1得 a2b1 a1b2 y a2c1 a1c2 第二步 解 得第三步 将 代入 得 推广 问题1 这两个解方程组算法的比较 第一步 2 得7x 11 第二步 解 得第三步 将代入 得 第一步 a2 a1得 a2b1 a1b2 y a2c1 a1c2 第二步 解 得第三步 将 代入 得 解方程组第一步 取a1 3 b1 2 c1 3 a2 2 b2 1 c2 4 第二步 计算第三步 给出运算结果 问题2 请你说出登录腾讯qq的步骤 电脑已经打开 第一步 打开qq程序 第二步 输入qq号码 第三步 输入密码 第四步 点击登录 问题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 因为余数不为0 所以2不能整除7 第二步 用3除7 得到余数1 因为余数不为0 所以3不能整除7 第三步 用4除7 得到余数3 因为余数不为0 所以4不能整除7 第四步 用5除7 得到余数2 因为余数不为0 所以5不能整除7 第五步 用6除7 得到余数1 因为余数不为0 所以6不能整除7 因此 7是质数 设计一个算法 判断35是否为质数 第一步 用2除35 得到余数1 因为余数不为0 所以2不能整除35 第二步 用3除35 得到余数2 因为余数不为0 所以3不能整除35 第三步 用4除35 得到余数3 因为余数不为0 所以4不能整除35 第四步 用5除35 得到余数0 因为余数不为0 所以5能整除35 因此 35不是质数 变式练习 想一想 什么是二分法 对于区间 a b 上连续不断且f a f b 0的函数y f x 通过不断地把函数f 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 设计算法要本着简单方便的原则 d 2 设计一个算法求三角形的面积 把下列步骤补充完整 1 求出三角形的底边长 2 3 根据三角形的面积公式求出三角形的面积 解析 由题意知 第 2 步应为求底边上的高 答案 求底边上的高 3 写出求1 2 3 100的一个算法 可运用公式1 2 3 n 直接计算 第一步 第二步 第三步输出计算结果 解析 第一步 取n 100 第二步 计算的值 答案 取n 100计算的值 4 作为家里的一员 在平时分担一些力所能及的家务是我们应尽的义务 你每天都帮家里做家务吗 你会烧开水吗 请写出你在家中烧开水的过程 提示 1 往壶内注水 2 点火加热 3 观察 如果水开 则停止烧火 否则继续烧火 4 如果水未开 重复过程 3 直至水开 5 任意给定一个大于1的正整数n 设计一个算法求出n的所有因数 解析 第一步 依次以2 n 1 为除数去除n 检查余数是否为0 若是 则是n的因数 若不是 则不是n的因数 第二步 在n