1.3辗转相除法与更相减损术学案-新课标人教版必修3

《1.3辗转相除法与更相减损术学案-新课标人教版必修3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学习重点：理解辗转相除法与更相减损术求最大公约数的方法。学习难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。一.辗转相除法(1)辗转相除法:该算法又称欧几里得算法,就是对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成一对新数,继续上面的除法,直到余数为零,此时处暑就是所求两正整数的最大公约数.(2)算法步骤:以求正整数的最大公约数为例.第一步,输入两个正整数.第二步,判断的大小,让表示较大的数,表示较小的数.第三步,计算除以的余数.第四步,让.第五步,如果,则的最

2、大公约数等于;否则返回第三步.例1（辗转相除法）求80和36的最大公约数跟踪练习1求两个正数8251和6105的最大公约数。（分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）跟踪练习2求288与123的最大公约数。二.更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术。更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母·子之数，以少减多，更相减损，求其等也，以等数约之。翻译出来为：第一步：任意给出两个正数；判断它们是

3、否都是偶数。若是，用2约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。例2（用更相减损术）求98与63的最大公约数.跟踪练习3：（用更相减损术）求两个正数84与72的最大公约数。跟踪练习4求57与93的最大公约数。总结：1比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字

4、大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到2辗转相除法与更相减损术计算的程序框图及程序利用辗转相除法与更相减损术的计算算法，我们可以设计出程序框图以及BSAIC程序来在计算机上实现辗转相除法与更相减损术求最大公约数，下面由同学们设计相应框图并相互之间检查框图与程序的正确性，并在计算机上验证自己的结果。