江西省遂川二中高中数学 算法的基本思想课件（2） 北师大版必修3.ppt

复习回顾 1 算法的概念 在数学中 算法是解决某一类问题的一系列步骤或程序 只要按照这些步骤执行 都能使问题得到解决 2 算法的特征 1 确定性 算法的每一步应该是确定的 能有效地执行且得到确定的结果 而不应当模棱两可 2 顺序性与正确性 算法从初始步骤开始 分为若干明确的步骤 前一步是后一步的前提 只有执行完前一步 才能执行下一步 并且每一步都准确无误 才能解决问题 3 不唯一性 求解某一个问题的算法不一定是唯一的 对于一个问题可以有不同的解法 4 有限性 算法的步骤序列是有限的 一个算法必须能够在执行有限步之后结束 不能无限循环 3 问题讨论 一个人带着三只狼和三只羊过河 只有一条船 同船可容纳一个人和两支动物 没有人在的时候 如果狼的数量不少于羊的数量狼就会吃羊 该人如何将动物转移过河 请你写出解决问题的步骤 参考答案 算法步骤 1 人带两只狼过河 并自己返回 2 人带一只狼过河 自己返回 3 人带两只羊过河 并带两只狼返回 4 人带一只羊过河 自己返回 5 人带两只狼过河 1算法的基本思想 2 一 具体算法案例分析 韩信像 例1 韩信点兵 问题 韩信是汉高祖刘邦手下的大将 他英勇善战 智谋超群 为建立汉朝立下汗马功劳 据说他在点兵的时候 为了保住军事机密 不让敌人知道自己部队的实力 采用下述点兵方法 先令士兵从1 3报数 结果最后一个士兵报2 再令士兵从1 5报数 结果最后一个士兵报3 又令士兵从1 7报数 结果最后一个士兵报4 这样 韩信很快就算出了自己部队士兵的总人数 请设计一个算法 求出士兵至少有多少人 解 算法步骤如下 先令士兵从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 5 在第4步得到的一列数中找出满足除以7余4的最小数 53 这就是所求的数 这5个步骤称为解决 韩信点兵 问题的一个算法 解法二算法步骤如下 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 概括 同一个问题 可能有多种算法 先令士兵从1 3报数 结果最后一个士兵报2 再令士兵从1 5报数 结果最后一个士兵报3 又令士兵从1 7报数 结果最后一个士兵报4 请设计一个算法 求出士兵至少有多少人 一位商人有9枚银元 其中有1枚略轻的是假银元 你能用天平 不用砝码 将假银元找出来吗 解算法步骤如下 1 任取2枚银元分分别放在天平的两边 如果天平左右不平衡 则轻的一边就是假银圆 如果天平平衡 则进行第2步 2 取下右边的银圆 放在一边 然后把剩余的7枚银圆依次放在右边进行称量 直到天平不平衡 偏轻的那一枚就是假银圆 例2 真假银元 问题 思考 这种算法最少要称 次 最多要称 次 1 7 一位商人有9枚银元 其中有1枚略轻的是假银元 你能用天平 不用砝码 将假银元找出来吗 解算法步骤如下 1 将银元分成3组 每组3枚 2 先将两组分别放在天平的两边 如果天平不平衡 那么假银元就在轻的那一组 如果天平左右平衡 则假银元就在未称的那一组 3 取出含假银元的那一组 从中任取两枚银元放在天平的两边 如果左右不平衡 则轻的那一边是假银元 如果天平两边平衡 则未称的那一枚是假银元 概括 算法有优劣之分 在实际问题中 找出好的算法是一项重要的工作 例2 真假银元 问题 思考 这种算法只要称 次 2 2 二分法求方程f x 0的近似解的基本思想是 将方程的有解区间平分为两个小区间 然后判断解在哪个小区间 继续把有解的区间平分并进行判断 直到求出满足精度要求的近似解 二 最优策略 二分法 1 当且仅当 方程f x 0在区间 a b 上有解x x0 其算法步骤如下 要求近似解精确到10 n 1 确定有解区间 a b f a f b 0 2 取 a b 的中点 3 计算函数f x 在中点处的函数值 4 判断函数值是否为零 1 若为0 就是方程的解 问题就得到解决 2 若不为0 则分下列两种情形 若 则确定新的有解区间为 若 则确定新的有解区间为 5 判断新的有解区间的长度是否大于精度 1 若新的有解区间长度大于精度 则在新的有解区间的基础上重复上述步骤 2 如果新的有解区间长度小于或等于精度 则这个有解区间中的任意一个数均为方程的满足精度的近似值 例3 求方程在 0 1 上的近似解 精到0 1 解算法步骤如下 1 因为f 0 1 f 1 1 f 0 f 1 0 则区间 0 1 为有解区间 2 取 0 1 的区间中点0 5 3 计算f 0 5 0 625 4 由于f 0 5 f 1 0 可得新的有解区间 0 5 1 5 取 0 5 1 的区间中点0 75 6 计算f 0 75 0 015625 7 因为f 0 75 f 1 0 可得新的有解区间 0 75 1 8 取 0 75 1 的区间中点0 875 9 计算f 0 875 0 435546875 10 因为f 0 75 f 0 875 0 可得新的有解区间 0 75 0 875 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 75 0 8125 中的任一数值 都可以作为方程的近似解 0 8125 0 75 0 0625 0 1 设 三 课堂练习 1 有一个围棋子 5个5个地数 最后余下两个 7个7个地数 最后余下3个 9个9个地数 最后余下4个 请设计一种算法 求出这把棋子至少有多少个 2 一个大油瓶装8kg油 还有两个空油瓶 一个能装5kg油 另一个能装3kg油 请设