1、算 法 案 例(第一课时 )求以下几组正整数的最大公约数。（ 1）（ 18， 30） （ 2）（ 24， 16）（ 3）（ 63， 63） （ 4）（ 72， 8） （ 5）（ 301， 133 ）解： 2 1 8 2 4 用公有质因数 2除，3 9 1 2 用公有质因数 3除， 3 4 3和 4互质不除了。 得： 18和 24最大公约数是： 2 3 6 想一想，如何求 8251与 6105的最大公约数？ 例、求 18与 24的最大公约数：6； 8；63； 8；7；短除法辗转相除法（欧几里得算法）观察用辗转相除法求 8251和 6105的最大公约数的过程 第一步 用两数中较大的数除以较小的数，
2、求得商和余数8251=61051+2146结论： 8251和 6105的公约数就是 6105和 2146的公约数，求 8251和6105的最大公约数，只要求出 6105和 2146的公约数就可以了。第二步 对 6105和 2146重复第一步的做法6105=21462+1813同理 6105和 2146的最大公约数也是 2146和 1813的最大公约数。 完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例 2 用辗转相除法求 225和 135的最大公约数225=1351+901
3、35=901+4590=452显然 37是 148和 37的最大公约数，也就是 8251和 6105的最大公约数 显然 45是 90和 45的最大公约数，也就是225和 135的最大公约数 思考 1：从上面的两个例子可以看出计算的规律是什么？ S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复 S1，直到余数为 0练习：用辗转相除法求下列两数的最大公约数：（ 1）（ 225， 135） （ 2）（ 98， 196）（ 3）（ 72， 168） （ 4）（ 153， 119）45 9824 17辗转相除法求两个数的最大公约数，其算法可以描述如下：辗转相除法是一个反复执行直到余数等于
4、 0停止的步骤，这实际上是一个循环结构 思考：辗转相除直到何时结束？主要运用的是哪种算法结构？ 给定两个正整数 m和 n； 计算 m除以 n的余数 r； m=n， n=r。 若 r=0,则 m,n的最大公约数等于 m;否则返回第二步 .辗转相除除法的程序框图与程序开始输入 m,nr=mMODn m=nn=rr=0？输出 m结束否是INPUT m,nDOr=mMODnm=nn=rLOOP UNTIL r=0PRINT mEND 九章算术 更相减损术 算理： 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步： 任意给定两个正整数；判断他们是否都是偶数。若是，
5、则用 2约简；若不是则执行第二步。第二步： 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。例、用更相减损术求 98与 63的最大公约数（自己按照步骤求解）解：由于 63不是偶数，把 98和 63以大数减小数，并辗转相减 。= 7所以， 98和 63的最大公约数等于 7。（ 98， 63）=（ 63， 35）98-63=3563-35=28 =（ 35， 28）35-28=7 =（ 28， 7）28-7=21 =（ 21， 7）21-7=14 =（ 14， 7）14-7=7 =（ 7， 7）练习：用更相减损术求下列两数的最大公约数：（ 1）（ 225， 135） （ 2）（ 98， 196）（ 3）（ 72， 168） （ 4）（ 153， 119）45 9824 17
