小结名师教学设计2

《算法案例——辗转相除法与更相减损术小结》教学设计

永州七中 欧亚鸣

（一）导入新课

复习导入

1、复习上节课内容；条件语句体和循环语句体。

2、从回顾求两数的最大公约数引入新课《算法案例——辗转相除法与更相减损术》

（1）怎样用短除法求最大公约数？

（2）还有其他办法求最大公约数吗？

（3）推介辗转相除法与更相减损术求最大公约数方法

（二）示例讲授

1、

用辗转相除法求8 251与6 105的最大公约数, 解：用两数中较大的数除以较小的数，求得商和余数：8 251=6 105×1+2 146.

由此可得，6 105与2 146的公约数也是8 251与6 105的公约数，反过来，8 251与6 105的公约数也是6 105与2 146的公约数，所以它们的最大公约数相等. 对6 105与2 146重复上述步骤：6 105=2 146×2+1 813.

同理，2 146与1 813的最大公约数也是6 105与2 146的最大公约数.继续重复上述步骤：

2 146=1 813×1+333，

1 813=333×5+148，

333=148×2+37，

148=37×4.

最后的除数37是148和37的最大公约数，也就是8 251与6 105的最大公约数. 这就是辗转相除法.由除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步之后完成，从而总可以用辗转相除法求出两个正整数的最大公约数. 2、写出辗转相除法求最大公约数的算法分析，画出程序框图，写出算法程序. 算法分析：从上面的例子可以看出，辗转相除法中包含重复操作的步骤，因此可以用循环结构来构造算法. 算法步骤如下：

第一步，给定两个正整数m，n. 第二步，计算m除以n所得的余数为r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步. 程序框图如右图：

程序：

INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m

1

END 难点点评：从以往的教学实践看，有些学生不能理解算法中的转化过程，例如：求8 251与6 105的最大公约数,为什么可以转化为求6 105与2 146的公约数.因为8 251=6 105×1+2 146，可以化为8 251-6 105×1=2 164，所以公约数能够整除等式两边的数，即6 105与2 146的公约数也是8 251与6 105的公约数. 3、用更相减损术求98与63的最大公约数. 解：由于63不是偶数，把98和63以大数减小数，并辗转相减，如下图所示. 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以，98和63的最大公约数等于7. 上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？

第一步，给定两个正整数m，n(m>n). 第二步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大者用m表示，小者用n表示. 第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步. 该程序框图对应的程序如何表述？

INPUT m，n WHILE m<>n k=m-n IF n>k THEN m=n n=k ELSE m=k END IF WEND PRINT m END “更相减损术”记录在《九章算术》中，《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”翻译为现代语言如下：

第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用2约简；若不是，执行第二步.

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数. 3、小结；更相减损术与辗转相除法的比较：尽管两种算法分别来源于东、西方古代数学名著，但是二者的算理却是相似的，有异曲同工之妙．主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但是实质都是一个不断的递归过程．

（三）课堂训练

（1）用辗转相除法求123和48的最大公约数.

2

（2）用更相减损术求80和36的最大公约数.

解：（1）辗转相除法求最大公约数的过程如下：

123＝2×48＋27，

48＝1×27＋21，

27＝1×21＋6，

21＝3×6＋3，

6＝2×3+0，

最后6能被3整除，得123和48的最大公约数为3. （2）我们将80作为大数，36作为小数，因为80和36都是偶数，要除公因数2. 80÷2=40，36÷2=18.

40和18都是偶数，要除公因数2. 40÷2=20，18÷2=9.

下面来求20与9的最大公约数，

20－9=11，

11－9=2，9－2=7，7－2=5，5－2=3，3－2=1，2－1=1，

可得80和36的最大公约数为22×1=4.

点评：对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等. 变式训练

分别用辗转相除法和更相减损术求1 734，816的最大公约数．

（四）课堂小结

（1）用辗转相除法求最大公约数. （2）用更相减损术求最大公约数. (3)数学思想方法：递归思想. （五）作业

（1）

分别用辗转相除法和更相减损术求261，319的最大公约数. （2）用当型循环写出辗转相除法的算法

3