20xx人教a版高中数学必修三13算法案例辗转相除法与更相减损术

20xx人教a版高中数学必修三13算法案例辗转相除法与更相减损术内容摘要：

所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数 . （三） 应用示例 例 1 用辗转相除法求 8 251 与 6 105 的最大公约数 ,写出算法分析，画出程序框图，写出算法程序 . 解： 用两数中较大的数除以较小的数，求得商和余数： 8 251=6 1051+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 1462+1 813. 同理， 2 146 与 1 813 的最大公约数也 是 6 105 与 2 146 的最大公约数 .继续重复上述步骤： 2 146=1 8131+333， 1 813=3335+148， 333=1482+37， 148=374. 最后的除数 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 点评： 从教学实践看，有些学生不能理解算法中的转化过程，例如：求 8 251 与 6 105的最 大公约数 ,为什么可以转化为求 6 105 与 2 146 的公约数 .因为 8 251=6 1051+2 146， 可以化为 8 2516 1051=2 164，所以公约数能够整除等式两边的数，即 6 105 与 2 146的公约数也是 8 251 与 6 105 的公约数 . 变式训练 你能用当型循环结构构造算法，求两个正整数的最大公约数吗。 试画出程序框图和程序 . 解： 当型循环结构的程序框图如下图： 程序： INPUT m， n r=1 WHILE r＞ 0 r=m MOD n m=n n=r WEND PRINT m END 例。