1、导学案 1.3.1算法案例1(辗转相除法与更相减损术)学习目标：1、理解辗转相除法与更相减损术的数学原理，会用辗转相除法与更相减损术求最大公约数； 2、基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序.重点：理解辗转相除法与更相减损术求最大公约数的方法.难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言. 一、复习回顾：用小学的方法求下列三组正整数的最大公约数：(1)72和168 (2) 98和63 (3) 8251和6105二、新知探究1、辗转相除法： 用辗转相除法求最大公约数的方法如下：S1：用较_的数m除以较_的数n得到一个_q0
2、和一个_r0；S2：若_，则_为m，n的最大公约数；若_，则用_除以_得到又一个商q1和一个余数r1；S3：若r1=0，则r1为的最大公约数；若r10，则用除数r0除以余数r1得到一个商q2和一个余数r2；依次计算直至rn0， rn-1即为所求的最大公约数例1、求8251和6105的最大公约数82516105121466105214621813214618131333181333351483331482371483740则37为8251与6105的最大公约数以上我们求最大公约数的方法就是辗转相除法也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的思考：你能把辗转相除法编成一个计算机
3、程序吗？辗转相除法程序框图 根据左图写出程序开始INPUT m，nmn?r=m MOD nPRINT结束r=0?思考：你能用当型循环结构构造算法，求两个正整数的最大公约数吗？2、更相减损术例2、 用更相减损术求98与63的最大公约数.S1：给定两个正整数m，n(mn). S2：计算mn所得的差k. S3：若nk，则其中大者用m表示，小者用n表示，返回第二步S4：若n=k，则m，n的最大公约数为n63不是偶数986335633528352872872121714147798与63的最大公约数是7 更相减损术程序框图： 程序输出m开始输入m,nk=m-n否是否是结束m=kn=km=n 注：辗转相除
4、法与更相减损术的区别:（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到；而更相减损术则以减数与差相等而得到。思考：利用辗转相除法是否可以求两数的最大公倍数？三、课堂练习1、用辗转相除法求294和84的最大公约数时，需要做除法的次数是（ ）A、2 B、3 C、4 D、52、用辗转相除法求567和405的最大公约数是 ( ) A、81 B、7 C、 5 D、353、 用更相减损术求587和405的最大公约数，需要做减法的次数是 ( ) A、12 B、13 C、14 D、154、145与232的最大公约数为 ( )A、45 B、19 C、29. D、325、用更相减损术求612与468的最大公约数：6、用辗转相除法求下列两数的的最大公约数，并用更相减损术检验你的结果： 280，124四、课堂小结1、理解辗转相除法与更相减损术求最大公约数的方法。2、辗转相除法与更相减损术求最大公约数的方法的区别。五、学习反思
