教学过程
第1课时案例1辗转相除法与更相减损术
导入新课
思路1 （情境导入）
大家喜欢打乒乓球吧，由于东、西方文化及身体条件的不同，西方人喜欢横握拍打球，东方人喜欢直 握拍打球，对于同一个问题，东、西方人处理问题方式是有所不同的
?在小学，我们学过求两个正整数的
最大公约数的方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的 除数连乘起来?当两个数公有的质因数较大时（如 8 251 与6 105 ），使用上述方法求最大公约数就比 较困难.下面我们介绍两种不同的算法一一辗转相除法与更相减损术
思路2 （直接导入）
前面我们学习了算法步骤、程序框图和算法语句
体会算法的思想? 推进新课 新知探究 提出问题 （1） 怎样用短除法求最大公约数？
（2） 怎样用穷举法（也叫枚举法）求最大公约数？ （3） 怎样用辗转相除法求最大公约数？
（4） 怎样用更相减损术求最大公约数？ 讨论结果： （1） 短除法
求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互 质数为止，然后把所有的除数连乘起来 （2） 穷举法（也叫枚举法）
穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约 数立即中断列举，得到的公约数便是最大公约数 （3） 辗转相除法
辗转相除法求两个数的最大公约数，其算法步骤可以描述如下： 第一步，给定两个正整数 m n.
第二步，求余数r :计算m除以n,将所得余数存放到变量 第三步，更新被除数和余数： m=n, n=r.
第四步，判断余数r是否为0.若余数为0，则输出结果；否则转向第二步继续循环执行
如此循环，直到得到结果为止 ?这种算法是由欧几里得在公元前 300年左右首先提出的，因而又叫欧 几里得算法? （4） 更相减损术
我国早期也有解决求最大公约数问题的算法， 多，更相减损，求其等也
就是更相减损术?《九章算术》是中国古代的数学专著，
其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之 数，以少减
?以等数约之?”翻译为现代语言如下：
2约简；若不是，执行第二步?
? ?
第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用
r中.
?
?今天我们将通过辗转相除法与更相减损术来进一步
，由此可以体会东、西方文化的差异 ?
第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操 作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数 应用示例
例1用辗转相除法求8 251与6 105的最大公约数，写出算法分析，画出程序框图，写出算法程序 解：用两数中较大的数除以较小的数，求得商和余数： 8 25仁6 105 X 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 X 2+1 813.
同理，2 146与1 813的最大公约数也是 6 105与2 146的最大公约数.继续重复上述步骤： 2 146=1 813 X 1+333, 1 813=333 X 5+148,
?
333=148X 2+37, 148=37X 4.
最后的除数37是148和37的最大公约数，也就是
8 251与6 105的最大公约数.
这就是辗转相除法?由除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步之 后完成，从而总可以用辗转相除法求出两个正整数的最大公约数
算法分析：从上面的例子可以看出，辗转相除法中包含重复操作的步骤， 算法步骤如下： 第一步，给定两个正整数 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 END
点评：从教学实践看，有些学生不能理解算法中的转化过程，例如：求 什么可以转化为求 6 105与2 146的公约数.因为8 251=6 105 X 1+2 146, 可以化为8 251- 6 105 X仁2 164，所以公约数能够整除等式两边的数，即 251与6 105的公约数. 变式训练
你能用当型循环结构构造算法，求两个正整数的最大公约数吗？试画出程序框图和程序 解：当型循环结构的程序框图如下图：
6 105与2 146的公约数也是8 8 251与6 105的最大公约数，为
程序： INPUT m , n r=1 WHILE r >0 r=m MOD n m=n n=r WEND PRINT m END
例2用更相减损术求98与63的最大公约数.
解：由于63不是偶数，把98和63以大数减小数，并辗转相减，如下图所示 98-63=3 5 63-35=2 8 35-28=7 28-7=21 21-7=14 14-7=7 所以，98和63的最大公约数等于 7.
点评：更相减损术与辗转相除法的比较：尽管两种算法分别来源于东、西方古代数学名著，但是二者的算 理却是相似的，有异曲同工之妙?主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损 术进行的是减法运算，即辗转相减，但是实质都是一个不断的递归过程. 变式训练
用辗转相除法或者更相减损术求三个数 解：324=243X 1+ 81, 243=81 X 3+ 0,
则324与243的最大公约数为 81. 又 135=81X 1+ 54 , 8仁54X 1+ 27 ,
324,243,135的最大公约数.
.
人教版高中数学必修3全套教案
