1.3.1辗转相除法与更相减损术.ppt

金品质?高追求 我们让你更放心 ！ ◆数学?必修3?(配人教A版)◆ 金品质?高追求 我们让你更放心！ 返回 ◆数学?必修3?(配人教A版)◆ 算法初步 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＝m MOD n表示m除以n余数为r，问： 14 MOD 3等于________？ 解析：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的最大公约数是4 B．78和36的最大公约数是6 C．85和340的最大公约数是17 D．105和315的最大公约数是105 C 2．在对16和12求最大公约数时，整个操作如下：(16,12)→(4,12)→(4,8)→(4,4)，由此可以看出12和16的最大公约数是(　 　) A．4　　　　 B．12　　　　 C．16　　　　 D．8 A 3．“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何”(　 　) A.2333 B.23 C.46 D.69 4．284和1024的最小公倍数是(　 　) A．1024 B．142 C．72704 D．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．3 B．9 C．17 D．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＝35 63－35＝28 35－28＝7 28－7＝21 21－7＝14 14－7＝7 所以，98与63的最大公约数是7.