文档介绍：算法案例
教学目标:(1) 理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析; (2) 基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序;(3)进一步体会算法的基本思想;
教学重点:理解辗转相除法与更相减损术求最大公约数的方法。
教学难点:把辗转相除法与更相减损术的方法转换成程序框图与程序语言。.
教学用具:投影仪
教学方法:启发式教学
教学过程:
一、新课导入:
提出问题:在小学,我们已经学过求最大公约数的知识,如口算求出12与20的公约数。其方法为:先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来。我们都是利用找公约数的方法来求最大公约数,如果公约数比较大而且根据我们的观察又不能得到一些公约数,我们又应该怎样求它们的最大公约数?比如求8251与6105的最大公约数?这就是我们这一堂课所要探讨的内容。
二、讲授新课:

例1 求两个正数8251和6105的最大公约数。
分析:8251与6105两数都比较大,而且没有明显的公约数,我们可以考虑用两数中较大的数除以较小的数,求得商和余数:
8251=6105×1+2146
显然6105与2146的公约数也必是8251与6105的公约数,反过来,8251与6105的最大公约数也是6105与2146的最大公约数,所以它们的最大公约数相等。
6105=2146×2+1813 2146=1813×1+333
1813=333×5+148 333=148×2+37
148=37×4+0
最后的除数37是148和37的最大公约数, 也就是8251与6105的最大公约数。
以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法,它是由欧几里德在公元前300年左右首先提出的。
利用辗转相除法求最大公约数的步骤如下:
(1).用较大的数m除以较小的数n得到一个商和一个余数;
(2).若=0,则n为m,n的最大公约数;若≠0,则用除数n除以余数得到一个商和一个余数;
(3).若=0,则为m,n的最大公约数;若≠0,则用除数除以余数得到一个商和一个余数;……依次计算直至=0,此时所得到的即为所求的最大公约数。
思考: 你能把辗转相除法编成一个计算机程序吗?
例如,把上面的例子为例.
算法步骤:
第一步,给定两个正整数m,n;
第二步,计算m除以n所得的余数r;
第三步,m=n, n=r.
第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步。
输入m,n
m = n
n = r
r=0?
输出m
开始
结束
求m除以n的余数r
程序框图:
否
是
INPUT m , n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
程序: