2013_2014学年高中数学人教A版必修三同步辅导与检测：1.3.1辗转相除法与更相减损术.ppt

算法初步;理解辗转相除法与更相减损术的含义和运算．;基础梳理;第三步：若r1＝0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2； …… 依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数． 例如：12与18的最大公约数为多少？;2．更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之． 翻译成现代语言为： 第一步：任意给定两个正整数；判断它们是否都是偶数．若是，用2约简；若不是，执行第二步． 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．;例如：用更相减损术求两个正数12与18的最大公约数． 3．51与72的最大公约数为________． 4．语句r＝m MOD n表示m除以n余数为r，问： 14 MOD 3等于________？;思考应用;2．辗转相除法与更相减损术有何区别？;自测自评;2．在对16和12求最大公约数时，整个操作如下：(16,12)→(4,12)→(4,8)→(4,4)，由此可以看出12和16的最大公约数是(　 　) A．4　　　　 B．12　　　　 C．16　　　　 D．8;3．“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何”(　 　) A.2333 B.23 C.46 D.69 4．284和1024的最小公倍数是(　 　) A．1024 B．142 C．72704 D．568;辗转相除法求最大公约数;跟踪训练;更相减损术求最大公约数;跟踪训练;比较辗转相除法与更相减损术;验证：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＋42 84＝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. 点评：由该题可以看出，辗转相除法求最大公约数步骤较少，而更相减损术运算简易，解题时要灵活运用．;跟踪训练;辗转相除法的程序框图与程序;程序：;跟踪训练;1．求最大公约数的方法要熟练使用但一般不要求会编写相应的程序． 2．三个数的最大公约数求法一般是第一与第二个数的最大公约数，然后求这个最大公约数与第三个数的最大公约数．;祝