2019-2020学年人教A版必修三 1.3 算法案例 教案
2019-2020学年人教A版必修三   1.3 算法案例  教案第2页

(3)辗转相除法

辗转相除法求两个数的最大公约数,其算法步骤可以描述如下:

第一步,给定两个正整数m,n.

第二步,求余数r:计算m除以n,将所得余数存放到变量r中.

第三步,更新被除数和余数:m=n,n=r.

第四步,判断余数r是否为0.若余数为0,则输出结果;否则转向第二步继续循环执行.

如此循环,直到得到结果为止. 这种算法是由欧几里得在公元前300年左右首先提出的,因而又叫欧几里得算法.

(4)更相减损术

我国早期也有解决求最大公约数问题的算法,就是更相减损术. 《九章算术》是中国古代的数学专著,其中的"更相减损术"也可以用来求两个数的最大公约数,即"可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之."翻译为现代语言如下:

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

第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.

应用示例

例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的最大公约数.

这就是辗转相除法.由除法的性质可以知道,对于任意两个正整数,上述除法步骤总可以在有限步之后完成,从而总可以用辗转相除法求出两个正整数的最大公约数.

算法分析:从上面的例子可以看出,辗转相除法中包含重复操作的步骤,因此可以用循环结构来构造算法.

算法步骤如下:

第一步,给定两个正整数m,n.

第二步,计算m除以n所得的余数为r.

第三步,m=n,n=r.

第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步.

程序框图如下图: