高中数学 1.3算法案例1课件 新人教A版必修3.ppt

1 3算法案例 1 辗转相除法与更相减损术 高中数学人教版必修三第一章 算法初步 表示算法的三种方式 算法步骤 自然语言 程序框图 图形语言 算法语句 程序语言 复习引入 315 945 问题1 在小学 我们已经学过求最大公约数的知识 你能求出12与16 18与90的最大公约数吗 1890 2 3 18和90的最大公约数是2 3 3 18 先用两个数公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来 问题2 求8251与6105的最大公约数 新课讲解 15 3 辗转相除法 欧几里得算法 观察用辗转相除法求8251和6105的最大公约数的过程 第一步用两数中较大的数除以较小的数 求得商和余数8251 6105 1 2146 结论 8251和6105的公约数就是6105和2146的公约数 求8251和6105的最大公约数 只要求出6105和2146的最大公约数就可以了 第二步对6105和2146重复第一步的做法6105 2146 2 1813同理6105和2146的最大公约数也是2146和1813的最大公约数 新课讲解 完整的过程 8251 6105 1 2146 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 显然37是148和37的最大公约数 也就是8251和6105的最大公约数 新课讲解 一 辗转相除法 欧几里得算法 1 定义 所谓辗转相除法 就是对于给定的两个数 用较大的数除以较小的数 若余数不为零 则将除数变被除数 余数变除数 继续上面的除法 直到大数被小数除尽 则这时最后的除数就是原来两个数的最大公约数 辗转相除法是一个反复执行直到余数等于0停止的算法 问题3 你能把辗转相除法写成算法步骤吗 研探新知 第四步 若r 0 则m n的最大公约数等于m 否则 返回第二步 辗转相除法求最大公约数算法步骤 第一步 给定两个正数m n m n 第二步 计算m除以n所得到的余数r 第三步 m n n r 研探新知 问题4 该算法的程序框图如何表示 求m除以n的余数r 新课讲解 问题5 该程序框图对应的程序如何表述 inputm n do r mmodn m n n r loopuntilr 0 printm end 求m除以n的余数r m n n r 新课讲解 问题6 如果用当型循环结构构造算法 求两个正整数m n的最大公约数的程序框图和程序分别如何表示 研探新知 inputm n whilen 0 r mmodn m n n r wend printm end 练习 1 用辗转相除法求下列两数的最大公约数 1 225 135 2 98 196 3 72 168 4 153 119 3 24 2 98 1 45 4 17 九章算术 更相减损术 算理 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 第一步 任意给定两个正整数 判断他们是否都是偶数 若是 则用2约简 若不是 执行第二步 第二步 以较大的数减较小的数 接着把所得的差与较小的数比较 并以大数减小数 继续这个操作 直到所得的减数和差相等为止 则这个等数就是所求的最大公约数 研探新知 2 更相减损术 1 定义 所谓更相减损术 就是对于给定的两个数 用较大的数减去较小的数 然后将差和较小的数构成新的一对数 再用较大的数减去较小的数 反复执行此步骤直到差数和较小的数相等 此时相等的两数便为原来两个数的最大公约数 研探新知 例用更相减损术求98与63的最大公约数 解 由于63不是偶数 把98和63以大数减小数 并辗转相减 即 98 63 3563 35 2835 28 728 7 2121 7 1414 7 7 所以 98与63的最大公约数是7 练习 用更相减损术求两个正数84与72的最大公约数 12 研探新知 辗转相除法与更相减损术的比较 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 研探新知 1 用辗转相除法求80和36的最大公约数 并用更相减损术检验所得结果 分析 将80作为大数 36作为小数 执行辗转相除法和更相减损术的步骤即可 解 用辗转相除法 80 36 2 8 36 8 4 4 8 4 2 0 故80和36的最大公约数是4 课堂测试 80 36 4444 36 836 8 2828 8 2020 8 1212 8 48 4 4 2 求三个数175 100 75的最大公约数 分析 求三个数的最大公约数时 可以先求出其中两个数的最大公约数 用这个最大公约数再与第三个数求最大公约数 所得结果就是这三个数的最大公约数 解 辗转相除法 先求175与100的最大公约数 175 100 1 75 100 75 1 25 75 25 3 175与100的最大公约数是25 课堂测试 以下再求25与75的最大公约数 75 25 3 25和75的最大公约数是25 故25是75和25的最大公约数 也就是175 100 75的最大公约数 课堂测试 175 100 75100 75 2575 25 5050 25 25 75 25 5050 25 25 1 用辗转相除法计算60与48的最大公约数时 需要做的除法次数是 a 1b 2c 3d 4解析 60 48 1 12 48 12 4 0 仅需要两步运算 答案 b 随堂练习 2用辗转相除法求294和84的最大公约数时 需要做除法的次数是 a 1b 2c 3d 4解析 294 84 3 42 84 42 2 故需做2次除法 答案 b 随堂练习 3求378和90的最大公约数 解 378 90 4 18 90 18 5 378和90的最大公约数是18 随堂练习 4 求三个数324 243 108的最大公约数 解 先求324与243的最大公约数 324 243 1 81 243 81 3 324与243的最大公约数为81 下面再求108与81的最大公约数 108 81 27 81 27 3 108与81的最大公约数是27 故324 243 108的最大公约数为27 随堂练习 1 辗转相除法 就是对于给定的两个正整数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽为止 这时的较小的数即为原来两个数的最大公约数 2 更相减损术 就是对于给定的两个正整数 用较大的数减去较小的数 然后将差和较小的数构成新的一对数 继续上面的减法 直到差和较小的数相等 此时相等的两数即为原来两个数的最大公约数 小结与作业 3 辗转相除法与更相减损术的区别 1 都是