度高中数学 1.3.1 辗转相除法与更相减损术同步辅导与检测课件 新人教A版必修3.ppt

算法初步 1 3算法案例1 3 1辗转相除法与更相减损术 理解辗转相除法与更相减损术的含义和运算 基础梳理 1 我们求最大公约数的方法就是辗转相除法 也叫欧几里得算法 它是由欧几里得在公元前300年左右首先提出的 利用辗转相除法求最大公约数的步骤如下 第一步 用较大的数m除以较小的数n得到一个商q0和一个余数r0 第二步 若r0 0 则n为m n的最大公约数 若r0 0 则用除数n除以余数r0得到一个商q1和一个余数r1 第三步 若r1 0 则r0为m n的最大公约数 若r1 0 则用除数r0除以余数r1得到一个商q2和一个余数r2 依次计算直至rn 0 此时所得到的rn 1即为所求的最大公约数 例如 12与18的最大公约数为多少 解析 18 12 1 6 12 6 2 所以12与18的最大公约数6 2 更相减损术求最大公约数的步骤如下 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 翻译成现代语言为 第一步 任意给定两个正整数 判断它们是否都是偶数 若是 用2约简 若不是 执行第二步 第二步 以较大的数减去较小的数 接着把较小的数与所得的差比较 并以大数减小数 继续这个操作 直到所得的数相等为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 例如 用更相减损术求两个正数12与18的最大公约数 3 51与72的最大公约数为 4 语句r mmodn表示m除以n余数为r 问 14mod3等于 解析 12为偶数 减半为6 18为偶数 减半为9 9 6 3 6 3 3 所以12与18的最大公约数为3 2 6 3 2 思考应用 1 如何求两个数的最大公约数 解析 先用两个公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来 如下图所示 25和35的最大公约数为5 2 辗转相除法与更相减损术有何区别 解析 辗转相除法与更相减损术都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 自测自评 1 下列各组关于最大公约数的说法中不正确的是 a 16和12的最大公约数是4b 78和36的最大公约数是6c 85和340的最大公约数是17d 105和315的最大公约数是105 c 2 在对16和12求最大公约数时 整个操作如下 16 12 4 12 4 8 4 4 由此可以看出12和16的最大公约数是 a 4b 12c 16d 8 a 3 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 a 2333b 23c 46d 694 284和1024的最小公倍数是 a 1024b 142c 72704d 568 b 解析 可以求得284和1024的最大公约数为4 所以最小公倍数为284 1024 4 72704 答案 c 辗转相除法求最大公约数 用辗转相除法求820与500的最大公约数 解析 820 500 1 320 500 320 1 180 320 180 1 140 180 140 1 40 140 40 3 20 40 20 2 所以820与500的最大公约数为20 跟踪训练 1 用 辗转相除法 求得459和357的最大公约数是 a 3b 9c 17d 51 解析 459 357 1 102 357 102 3 51 102 51 2 所以51是102和51的最大公约数 也就是459和357的最大公约数 答案 d 更相减损术求最大公约数 用更相减损术求98与63的最大公约数 解析 由于63不是偶数 把98和63以大数减小数 并辗转相减 即 98 63 3563 35 2835 28 728 7 2121 7 1414 7 7所以 98与63的最大公约数是7 跟踪训练 2 用 更相减损术 求225与135的最大公约数为 a 45b 5c 9d 15 解析 225 135 90 135 90 45 90 45 45 所以选a 答案 a 比较辗转相除法与更相减损术 用辗转相除法求下面两数的最大公约数 并用更相减损术检验你的结果 1 80 36 2 294 84 分析 使用辗转相除法 我们可依据a nb r这个式子 反复执行 直到r 0为止 用更相减损术就是根据r a b这个式子 反复执行 解析 1 80 36 2 836 8 4 48 4 2 0即80与36的最大公约数是4 验证 80 36 44 44 36 8 36 8 28 28 8 20 20 8 12 12 8 4 8 4 4 80与36的最大公约数为4 2 294 84 3 4284 42 2即294与84的最大公约数是42 验证 294与84都是偶数可同时除以2 即取147与42的最大公约数后再乘2 147 42 105 105 42 63 63 42 21 42 21 21 294与84的最大公约数为21 2 42 点评 由该题可以看出 辗转相除法求最大公约数步骤较少 而更相减损术运算简易 解题时要灵活运用 跟踪训练 3 用更相减损术求98与64的最大公约数 解析 由于64是偶数 减半为32 把98和32以大数减小数 并辗转相减 即 98 32 66 66 32 34 34 32 2 32 2 30 30 2 28 4 2 2 所以 98与64的最大公约数是2 辗转相除法的程序框图与程序 写出辗转相除法的程序框图及程序 解析 r mmodn表示m除以n的余数为r 例如 3 15mod6程序框图 程序 input m minput n nifm nthenx mm nn xendif r mmodnwhiler0r mmodnm nn rwendprintmend 跟踪训练 4 下边程序运行后输出的结果为 a 50b 5c 25d