【金版学案】2014-2015学年高中数学（人教版必修三）课时训练第一章1.3.1辗转相除法与更相减损术.pptVIP

第一章　算法初步 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约简；若不是，执行第二步． 课标点击 预习导学 典例精析 栏目链接 第二步，以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数． 3．语句“r＝m MOD n”表示m除以n余数为r，则：“14 MOD 3”等于________． 2 课标点击 预习导学 典例精析 栏目链接 自测自评 1．下列各组关于最大公约数的说法中不正确的是(　　) A．16和12的最大公约数是4 B．78和36的最大公约数是6 C．85和340的最大公约数是17 D．105和315的最大公约数是105 2．在对16和12求最大公约数时，整个操作如下：(16,12)→(4,12)→(4,8)→(4,4)，由此可以看出12和16的最大公约数是(　　) A．4　　　　B．12　　　　C．16　　　　D．8 C A 课标点击 预习导学 典例精析 栏目链接 3．今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何(　　) A．2 323 B．23 C．46 D．69 4．284和1 024的最小公倍数是(　　) A．1 024 B．142 C．72 704 D．568 B C 课标点击 预习导学 典例精析 栏目链接 学习目标 预习导学 典例精析 栏目链接 题型一 辗转相除法求最大公约数 例1 　用辗转相除法求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 D 课标点击 预习导学 典例精析 栏目链接 题型二 更相减损术求最大公约数 例2 用更相减损术求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. 课标点击 预习导学 典例精析 栏目链接 跟 踪训 练 2．用更相减损术求225与135的最大公约数为(　　) A．45 B．5 C．9 D．15 A 课标点击 预习导学 典例精析 栏目链接 题型三 比较辗转相除法与更相减损术 例3 用辗转相除法求