1.3算法案例1cankao

《1.3算法案例1cankao》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、除数的公约数。因此，求8251和6105的最大公约数，只需求出6105和2146的公约数即可。第二步对6105和2146重复上述做法6105=2146×2+1813第三步对2146和1813重复上述做法2146=1813×1+333第四步1813=333×5+148第五步333=148×2+37第六步148=37×4除数和余数的公约数就是被除数和除数的公约数显然，37是148和37的最大公约数，所以，8251和6105的最大公约数是37.第一步8251=6105×1+2146辗转相除法（欧几里得算法）最大公约数：余数为0的除数+08251=6105×1+

3、21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例1：用辗转相除法求225和135的最大公约数225=135×1+90135=90×1+4590=45×2所以，45是225和135的最大公约数.第一步：用大数除以小数第二步：除数变成被除数，余数变成除数第三步：重复上述步骤，直到余数为0问题：求8251和6105的最大公约数所以，37是8215和6105的最大公约数.计算规律？辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。8251=61

4、05×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0a=b×q＋r用程序框图表示出例1的过程r=aMODba=bb=rr=0?是否思考：辗转相除法用哪种逻辑结构书写？（1）算法步骤第一步：输入两个正整数a,b(a>b);第二步：把a/b的余数赋给r;第三步：如果r0,那么把b赋给a,把r赋给b,转到第二步;否则转到第四步；第四步：输出最大公约数b.a=b×q＋r（2）程序框图（3）程序INPUT“a,b=“;a,bDOr=aMODba=bb=rLOOPUN

5、TILr=0PRINTaEND开始输入a,br=aMODba=br=0?是否b=r输出a结束更相减损术——《九章算术》算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。翻译如下：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：用较大的数减较小的数，接着把所得的差与较小的数比较，再用大数减小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。例2：求98与63的最大公约数98－63=3563－35＝2835－28

6、＝728－7＝2121－7＝1414－7＝7所以，98和63的最大公约数是7.更相减损术算法步骤:第四步：输出最大公约数b.第三步：如果b>r,那么把b赋给a,把r赋给b;否则把r赋给a，执行第二步；第二步：把a-b的差赋予r;第一步：输入两个正整数a,b(a>b,a,b都不是偶数);a-b=r例3、用更相减损术求260和104的最大公约数。解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。把65和26辗转相减：65-26=3939-26=1326-13=13所以，260与104的最大公约数为：2×2×13=52.思

7、考：若a,b都是偶数，如何用更相减损术求最大公约数？辗转相除法：8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0更相减损术：98－63=3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7区别？辗转相除法和更相减损法都是用来求两个数的最大公约数的.区别：辗转相除法进行的是除法运算，即辗转相除，直到余数为0为止；更相减损术进行的是减法运算，即辗转相减，直到减数和差相等为止.辗转相除法与更相减损法的比较：练习：分别用辗转

8、相除法和更相减损术求下面两组数的最大公约数.（1）123和48（2）80和36