13算法案例1cankao.ppt

《13算法案例1cankao.ppt》由会员分享，可在线阅读，更多相关《13算法案例1cankao.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.3 1.3 算法案例算法案例辗转相除法辗转相除法更相减损术更相减损术求两个正整数的最大公约数求两个正整数的最大公约数（1）求）求49和和63的最大公约数的最大公约数（2）求）求18和和30的最大公约数的最大公约数问题：求问题：求8251和和6105的最大公约数的最大公约数 76“辗转相除法辗转相除法”又名又名“欧几里得算法欧几里得算法”，是已知的求最大公约，是已知的求最大公约数的最古老的算法，可追溯到数的最古老的算法，可追溯到30003000年。最早出现于年。最早出现于欧几里得的几何原本，而在中国可以追溯到东欧几里得的几何原本，而在中国可以追溯到东汉出现的九章算术。汉出现的九章算术。第一步

2、第一步 用两数中较大的数除以较小的数，求得用两数中较大的数除以较小的数，求得商和余数商和余数 8251=61051+2146问题问题：求：求8251和和6105的最大公约数的最大公约数 被除数被除数除数除数余数余数商商分析：分析：61056105和和21462146的公约数就是的公约数就是82158215和和61056105的公约数，的公约数， 除数除数和和余数余数的公约数就是的公约数就是被除数被除数和和除数除数的公约数。的公约数。因此，求因此，求82518251和和61056105的最大公约数，只需求出的最大公约数，只需求出61056105和和21462146的公约数即可。的公约数即可。第二

3、步第二步 对对6105和和2146重复上述做法重复上述做法 6105=21462+1813第三步第三步 对对2146和和1813重复上述做法重复上述做法 2146=18131+333第四步第四步 1813=3335+148第五步第五步 333=1482+37第六步第六步 148=374 除数除数和和余数余数的公约数就是的公约数就是被除数被除数和和除数除数的公约数的公约数显然，显然，3737是是148148和和3737的最大公约数，的最大公约数，所以，所以，82518251和和61056105的最大公约数是的最大公约数是37.37.第一步第一步8251=61051+2146 辗转相除法（欧几里得

4、算法）辗转相除法（欧几里得算法）最大公约数：最大公约数：余数为余数为0 0的的除数除数+08251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0 例例1 1：用辗转相除法求：用辗转相除法求225225和和135135的最大公约数的最大公约数225=1351+90135=901+4590=452所以，所以，45是是225和和135的的最大公约数最大公约数. 第一步：用大数除以小数第一步：用大数除以小数第二步：除数变成被除数，第二步：除数变成被除数，余数变成除数余数变成除数第三步：重复上述步骤，直到

5、余数为第三步：重复上述步骤，直到余数为0问题：求问题：求82518251和和61056105的的最大公约数最大公约数 所以，所以，37是是8215和和6105的最大公约数的最大公约数. 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0 0停止停止的步骤，这实际上是一个循环结构。的步骤，这实际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0a =b q r用程序框图表示出例用程序框图表示出例1的过程的过程r=a MOD ba = bb = rr

6、=0?是否思考：辗转相除法用哪种逻辑结构书写？思考：辗转相除法用哪种逻辑结构书写？（1）算法步骤）算法步骤第一步：输入两个正整数第一步：输入两个正整数a,b(ab);第二步：把第二步：把a/b的余数赋给的余数赋给r;第三步：如果第三步：如果r 0, 那么把那么把b赋给赋给a,把把r赋给赋给b,转转 到第二步到第二步;否则转到第四步；否则转到第四步；第四步：输出最大公约数第四步：输出最大公约数b.a = b q r（2）程序框图）程序框图（3）程序）程序INPUT “a,b=“;a,bDO r=a MOD b a=b b=rLOOP UNTIL r=0PRINT aEND开始开始输入输入a,b

7、r=a MOD b a=br=0?是是否否 b=r 输出输出a结束结束更相减损术更相减损术 九章算术九章算术算理：算理：可半者半之，不可半者，副置分母、子之数，可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。以少减多，更相减损，求其等也，以等数约之。翻译如下：翻译如下： 第一步：任意给定两个正整数；判断它们是否都是偶第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用数。若是，则用2 2约简；若不是则执行第二步。约简；若不是则执行第二步。 第二步：用较大的数减较小的数，接着把所得的差与第二步：用较大的数减较小的数，接着把所得的差与较小的数比较，再用大数

8、减小数。继续这个操作，直较小的数比较，再用大数减小数。继续这个操作，直到所得的到所得的减数减数和和差差相等相等为止。为止。 则第一步中约掉的则第一步中约掉的若干个若干个2 2与第二步中与第二步中等数等数的乘积就的乘积就是所求的最大公约数。是所求的最大公约数。 例例2：求：求98与与63的最大公约数的最大公约数9863=356335283528728721217141477所以，所以，98和和63的最大公约数是的最大公约数是7. 更相减损术更相减损术算法步骤算法步骤:第四步：第四步：输出最大公约数输出最大公约数b.第三步：第三步：如果如果br, 那么把那么把b赋给赋给a,把把r赋给赋给b;否则把

9、否则把r赋给赋给a，执行第二步；，执行第二步；第二步：第二步：把把a-b的差赋予的差赋予r;第一步：输入两个正整数第一步：输入两个正整数a,b(ab,a,b都不是偶数都不是偶数);a-b=r例例3 3、用更相减损术求、用更相减损术求260260和和104104的最大公约数。的最大公约数。 解：由于解：由于260260和和104104均为偶数，首先用均为偶数，首先用2 2约简得到约简得到130130和和5252，再用，再用2 2约简得到约简得到6565和和2626。 把把6565和和2626辗转相减：辗转相减： 65-26=39 65-26=39 39-26=13 39-26=13 26-13=

10、13 26-13=13 所以，所以，260260与与104104的最大公约数为：的最大公约数为：2 22 213=52. 13=52. 思考：若思考：若a,ba,b都是偶数，如何用更相减损术求最大公都是偶数，如何用更相减损术求最大公约数约数？辗转相除法：辗转相除法：8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0更相减损术：更相减损术：9863=356335283528728721217141477辗转相除法和更相减损法都是用来求两个数的辗转相除法和更相减损法都是用来求两个数的最大公约数的最大公约数的. . 区别：区别：辗转相除法辗转相除法进行的是除法运算，即进行的是除法运算，即辗转相除，辗转相除，直到余数为直到余数为0 0为止；为止；更相减损术更相减损术进行的是减法运算，即进行的是减法运算，即辗转相减，辗转相减，直到减数和差相等为止直到减数和差相等为止. .辗转相除法与更相减损法的比较：辗转相除法与更相减损法的比较：练习：练习：分别用辗转相除法和更相减损术求下面两分别用辗转相除法和更相减损术求下面两组数的最大公约数组数的最大公约数. .（1 1）123 123 和和 48 48（2 2）80 80 和和 36 36