《1.4算法案例》课件1.ppt

数学 必修3 苏教版 第1章算法初步1 4算法案例 情景切入韩信是秦末汉初的著名军事家 据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场 刘邦问韩信有什么方法 不要逐个报数 就能知道场上的士兵的人数 韩信先令士兵排成3列纵队 结果有2人多余 接着立即下令将队形成为5列纵队 这一改 又多出3人 随后他又下令改为7列纵队 这次又剩下2人无法成整行 在场的人都哈哈大笑 以为韩信不能清点出准确的人数 不料笑声刚落 韩信高声报告共有士兵2333人 众人听了一愣 不知道韩信用什么方法这么快就能得出正确的结果的 同学们 你知道吗 1 理解辗转相除法与更相减损术求最大公约数的方法 2 理解中国剩余定理在数学中的应用 3 理解二分法求方程的近似解的算法 1 孙子剩余定理即 在近代数学和电子计算机程序设计中有着广泛的应用 2 公元前3世纪 欧几里得在 原本 中介绍的求两个正整数的最大公约数的方法 称为 3 63与231的最大公约数是 中国剩余定理 欧几里得辗转相除法 21 一 中国剩余定理 中国剩余定理 也称为孙子剩余定理 该定理在近代数学和电子计算机程序设计中有着广泛的应用 1 剩余问题 在整数除法里 一个数分别除以几个数 得到整数商后 均有剩余 已知各除数及其对应的余数 从而要求出适合条件的这个被除数的问题 叫做剩余问题 2 两个性质 性质1 几个数相加 如果只有一个加数不能被数a整除 而其他加数均能被数a整除 那么它们的和就不能被数a整除 如 10能被5整除 15能被5整除 但7不能被5整除 所以 10 15 7 不能被5整除 性质2 二数不能整除 若被除数扩大 或缩小 了几倍 而除数不变 则其余数也同时扩大 或缩小 相同的倍数 余数必小于除数 如 22 7 3 1 22 4 7 12 1 4 4 要余2 则22 2 7 6 2 22 9 7 28 1 9 7 2 要余5 则22 5 7 15 5 3 中国剩余定理 中国数学史书上记载 在两千多年前的我国古代算书 孙子算经 中 有这样一个问题 称为 物不知数 问题 及其解法 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二问物几何 答曰 二十三 术曰 三三数之剩二 置一百四十 五五数之剩三 置六十三 七七数之剩二 置三十 并之 得二百三十三 以二百一十减之即得 术 即解法 书中还介绍了上述问题中余数为一的一般解法 凡三三数之剩一 则置七十 五五数之剩一 则置二十一 七七数之剩一 则置十五 一百六以上 以一百五减之即得 在明朝程大位著 算术统宗 一书中 把上述问题的基本解法 用诗句概括为 三人同行七十稀 五树梅花廿一枝 七子团圆正半月 除百减五便得知 依定理译成算式为 70 2 21 3 15 2 233 233 105 2 23 这就是享誉中外的 中国剩余定理 4 物不知数 问题的算法分析与算法的流程图与伪代码表示 请直接参见教材相关部分 1 辗转相除法 公元前3世纪欧几里得在 原本 中提出的 设有不相等的二数 从大数中连续减去小数直到余数小于小数 再从小数中连续减去余数直到小于余数 这样一直下去 若余数总是量不尽其前一个数 直到最后的余数为一个单位 则该二数互质 二 求两个正整数的最大公约数的算法 辗转相除法就是把给定的两个数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数 继续上面的除法 直到余数为零 此时的除数就是所求的最大公约数 从算法思想我们可以看出 辗转相除法的基本步骤是用较大的数 用a表示 除以较小的数 用b表示 得到 a nb r 0 r b 由于这是一个反复执行的步骤 且执行的次数由余数r是否等于0决定 所以我们可以把它看作一个循环体 用循环结构就可以实现其算法 2 更相减损术 用更相减损术求两个正整数的最大公约数的过程与算法设计 对于给定的两个正整数 用较大的数减去较小的数 接着将得到的差与较小的数比较 用这两个数中的较大的数减去较小的数 继续上述的操作 大数减小数 直到产生一对相等的数为止 那么这个数 等数 就是所求的最大公约数 这是因为每次操作后所得的两数与前两数具有相同的最大公约数 而两数的值逐渐减小 经过有限步操作后一定可得相等的两数 要点导航 3 更相减损术 与 辗转相除法 的异同点 更相减损术 与 辗转相除法 这两种算法分别来源于东西方古代数学名著 但二者的算理确是相似的 有异曲同工之妙 主要区别在于辗转相除法进行的是除法运算 即辗转相除 而更相减损术进行的是减法运算 即辗转相减 但实质都是一个不断的递归过程 辗转相除法的理论依据是 由a nb r a b r a nb得a b与b r有相同的公约数 更相减损术的理论依据是 由a b r a b a b r得a b与b r 要点导航 有相同的公约数 所以 它们有相同的理论依据 只不过一个用除法 另一个用减法罢了 三 二分法 例1我国 算经十书 之一 孙子算经 中有这样一个问题 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 你能用程序解决这个问题吗 这个问题的通用解法称为 孙子剩余定理 或 中国剩余定理 著名的 韩信点兵问题 即为此例的应用 因此 可以让m从2开始检验 若三个条件中有任何一个不成立 则m递增1 一直到m同时满足三个条件为止 流程图如下图所示 伪代码如下 典例剖析 变式训练 1 有一堆桃子不知数目 猴子第一天吃掉一半 觉得不过瘾 又多吃了一个 第二天照此办法 吃掉剩下桃子的一半另加一个 天天如此 到第十天早上剩下一个桃子 问这堆桃子有多少个 第十天桃子数 S10 1 个 第九天桃子数 S9 1 1 2 4 个 第八天桃子数 S8 1 4 2 10 个 第一天桃子数 S1 S2 1 2 个 所以递推关系是S10 1 Sn Sn 1 1 2 n 1 2 9 故可用循环结构设计算法 流程图如右上图所示 典例剖析 例2写出求两个正整数a b a b 的最大公约数的一个算法 并画出流程图 写出相应的伪代码 利用辗转相除法 求出数列a b r1 r2 rn 0 这列数从第三项开始每项都是前两项相除 小的除大的 所得的余数 余数0的前一个rn即为a和b的最大公约数 典例剖析 算法如下 S1输入两个正整数a b a b S2r a b的余数 S3a b b r S4如果r 0 转S2 S5输出最大公约数b 伪代码如下 流程图如下图所示 典例剖析 辗转相除法是解决求最大公约数的通法 也是解决求两个正整数最小公倍数的通法 可以输入不同的a b值 先求两数的最大公约数 变式训练 2 下述伪代码输出的结果是 伪代码是求375和85的最大公约数 375 85 4 35 85 35 2 15 35 15 2 5 15 5 3 0 375与85的最大公约数是5 5 典例剖析 例3现有长度为360cm和780cm两种规格的钢筋若干 要焊接一批正方体模型 问怎样才能保证正方体体积最大且不浪费 编写算法流程图 并写出相应的伪代码 正方体的所有棱长都相等 故必须将钢筋剪裁成长度相等的钢筋条 又必须不浪费 这就说明必须剪后无剩余 于是为了保证正方体的体积最大 剪的钢筋的最大长度为360cm和780cm的最大公约数 可用更相减损术求最大公约数 典例剖析 根据更相减损术求780和360的最大公约数的步骤如下 780 360 420 420 360 60 360 60 300 300 60 240 240 60 180 180 60 120 120 60 60 60 60 0 典例剖析 则60即为360和780的最大公约数 流程图如下图所示 典例剖析 伪代码如下 典例剖析 1 更相减损术的基本步骤是用较大的数 用a表示 减去较小的数 用b表示 每次操作后所得的两数与前两数具有相同的最大公约数 而两数的值逐渐减小 经过有限步操作后 总能得到相等的两个数 即求得两数的最大公约数 典例剖析 2 辗转相除法进行的是除法运算 执行次数由余数是否为0决定 更相减损术进行的是减法运算 执行次数由差数与较小的数是否相等决定 二者实质都是一个不断递归的过程 是一个反复执行的步骤 因而用循环结构就可实现其算法 典例剖析 3 运行下面的伪代码 当输入78和36时 输出的结果是 变式训练 典例剖析 伪代码是求78与36的最大公约数 78 36 42 36 6 36 6 30 6 24 6 18 6 12 6 6 所以78和36的最大公约数为6 6 典例剖析 例4已知函数f x x2 5 写出求方程f x 0在 2 3 上的近似解 精确到0 001 的算法伪代码 并画出流程图 由题目可获取以下主要信息 1 已知函数f x x2 5 2 求方程f x 0在 2 3 上的近似解 典例剖析 3 精确到0 001 解答本题可先回忆一下二分法求近似根的步骤 由步骤画出流程图 然后再写出算法的伪代码 流程图如下图所示 典例剖析 典例剖析 伪代码为 典例剖析 针对这个类型的题目书写伪代码时一定要注意伪代码的具体格式 另外循环语句中一定包含有条件结构的语句 求高次方程近似解时 一定要给出精确度 典例剖析 变式训练 4 写算法 用二分法求log230的值 精确到0 001 并画出流程图 写出伪代码 典例剖析 设log230 m 令f x log230 x 据估计m 4 5 令a 4 b 5 其算法步骤可表示为 第一步取 a b 中点m0 a b 将区间一分为二 第二步若f m0 0 则m0即为所求 否则 判断m在m0的左侧还是右侧 若f a f m0 0 则m m0 b 以m0代替a 若