高中课件-算法案例.pdf

第一章算法初步

1.3算法案例

〖创设情景，揭示课题〗

案例1辗转相除法与更相减损术

[问题1]：在小学，我们已经学过求最大公约数

的知识，你能求出18与30的最大公约数吗？

21830

3915

35

∴18和30的最大公约数是2×36.

先用两个数公有的质因数连续去除,一直除到

所得的商是互质数为止,然后把所有的除数连

乘起来.

〖创设情景，揭示课题〗

[问题2]:我们都是利用找公约数的方法来求

最大公约数，如果两个数比较大而且根据我

们的观察又不能得到一些公约数，我们又应

该怎样求它们的最大公约数？比如求8251与

6105的最大公约数?

〖研探新知〗

1.辗转相除法:

例1求两个正数8251和6105的最大公约数。

分析：8251与6105两数都比较大，而且没

有明显的公约数，如能把它们都变小一点，根

据已有的知识即可求出最大公约数.

解：8251＝6105×1＋2146

显然8251与6105的最大公约数也必是2146

的约数，同样6105与2146的公约数也必是8251

的约数，所以8251与6105的最大公约数也是

6105与2146的最大公约数。

1.辗转相除法:

例1求两个正数8251和6105的最大公约数。

解：8251＝6105×1＋2146;

6105＝2146×2＋1813;

2146＝1813×1＋333;

1813＝333×5＋148;

333＝148×2＋37;

148＝37×4＋0.

则37为8251与6105的最大公约数。

以上我们求最大公约数的方法就是辗转相

除法。也叫欧几里德算法，它是由欧几里德在

公元前300年左右首先提出的。

辗转相除法求最大公约数算法：

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

•第二步,计算m除以n所得到余数r

•第三步,mn,nr

•第四步,若r0,则m,n的最大公约数等于m;

否则返回第二步

思考：需不需要比较m，n的大小

不需要

程序框图开始

输入两个正数m,n

rmMODn

mn

nr

否

r0?

是

输出m

结束

练习1：利用辗转相除法求两数4081与20723

的最大公约数.(53)

207234081×5+318;

4081318×12+265;

318265×1+53;

26553×5+0.

2.更相减损术:

我国早期也有解决求最大公约数问题的算

法，就是更相减损术。

更相减损术求最大公约数的步骤如下：可

半者半之，不可半者，副置分母、子之数，以

少减多，更相减损，求其等也，以等数约之。