1.3-1辗转相除法和更相减损术.pptVIP

1.3 算法案例 ;问题提出;辗转相除法与;知识探究（一）:辗转相除法;思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？ ;思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？; 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。;思考5:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ ;思考5:该算法的程序框图如何表示？;思考6:该程序框图对应的程序如何表述？;思考7:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？;开始;练习1：利用辗转相除法求两数4081与20723的最大公约数. ;知识探究（二）:更相减损术 ;思考2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？;思考3:该算法的程序框图如何表示？;思考4:该程序框图对应的程序如何表述？;“更相减损术”在中国古代数学专著《九章算术》中记述为： 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之. ;INPUT “m,n=“;m,n IF mn THEN a=m m=n n=a END IF K=0 WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1 WEND d=m- n ;理论迁移;更相减损术:168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3.; 例2 求325，130，270三个数的最大公约数. ; 1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽??止，这时的较小的数即为原来两个数的最大公约数. ;比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到;作业： P45练习：1. P48习题1.3A组：1.