算法案例辗转相除法和更相减损术

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,1,、求两个正整数的最大公约数,（,1,）求,25,和,35,的最大公约数,（,2,）求,49,和,63,的最大公约数,2,、求,8251,和,6105,的最大公约数,25,（,1,）,5,5,35,7,49,（,2,）,7,7,63,9,所以，,25,和,35,的最大公约数为,5,所以，,49,和,63,的最大公约数为,7,辗转相除法,又名“欧几里德算法”（,Euclidean algorithm,）乃求两数之最大公因数算法。它是已知最古老的算法,其可追溯至前,300,年。它首次出现于欧几里德的,几何原本,中，而在中国则可以追溯至东汉出现的,九章算术,。它并不需要把二数作质因数分解,欧几里德,辗转相除法（欧几里得算法）,观察用辗转相除法求,8251,和,6105,的最大公约数的过程,第一步,用两数中较大的数除以较小的数，求得商和余数,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+333,1813=3335+148,333=1482+37,148=374+0,例,2,用辗转相除法求,225,和,135,的最大公约数,225=1351+90,135=901+45,90=452,显然,37,是,148,和,37,的最大公约数，也就是,8251,和,6105,的最大公约数,显然,45,是,90,和,45,的最大公约数，也就是,225,和,135,的最大公约数,思考,1,：从上面的两个例子可以看出计算的规律是什么？,S1,：用大数除以小数,S2,：除数变成被除数，余数变成除数,S3,：重复,S1,，直到余数为,0,辗转相除法是一个反复执行直到余数等于,0,停止的步骤，这实际上是一个循环结构。,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,m=n q,r,用程序框图表示出右边的过程,r=m MOD n,m=n,n=r,r=0?,是,否,思考,2,：辗转相除法中的关键步骤是哪种逻辑结构？,九章算术,更相减损术,算理：,可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：,任意给定两个正整数；判断他们是否都是偶数。若是，则用,2,约简；若不是则执行第二步。,第二步：,以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。,例,3,用更相减损术求,98,与,63,的最大公约数,解：由于,63,不是偶数，把,98,和,63,以大数减小数，并辗转相减,98,63,3563,35,2835,28,728,7,21,21,7,14,14,7,7,所以，,98,和,63,的最大公约数等于,7,练习：,课本,P45,练习第,1,题,