人教A版高中数学必修3第一章1.3 算法案例课件 (6)（14张PPT）

第一章 算法初步
1.3 算法案例
3 5
9 15
[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？
〖创设情景，揭示课题〗
18 30
2
3
∴18和30的最大公约数是2×3=6.
先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.
案例1 辗转相除法与更相减损术
〖创设情景，揭示课题〗
[问题2]:我们都是利用找公约数的方法来求
最大公约数，如果两个数比较大而且根据我
们的观察又不能得到一些公约数，我们又应
该怎样求它们的最大公约数？比如求8251与
6105的最大公约数?
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年左右首先提出的。
求18与30的最大公约数
解∵30=18×1+12
18=12×1+6
12=6×2
∴18与30的最大公约数是6
练习
用辗转相除法求下列两个正整数的最大公约数
①225 135 ②98 196 ③72 168 ④153 119
答案：45 98 24 17
总结辗转相除法方法
用大数除以小数得到商和余数，接着用除数除以余数得到商和余数，依次计算下去，直到余数为零，最后式子的除数是所求的最大公约数。
2.更相减损术:
我国早期也有解决求最大公约数问题的算法，就是更相减损术。
更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。
翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。
例题
用更相减损术求两个正整数的最大公约数
18与30
解 ∵18÷2=9 30÷2=15
15－9=6
9－6=3
6－3=3
∴18与30的最大公约数是3×2=6
例2 用更相减损术求98与63的最大公约数.
解：由于63不是偶数，把98和63以大数减小数，并辗转相减，
即：98－63＝35;
63－35＝28;
35－28＝7;
28－7＝21;
21－7＝14;
14－7＝7.
所以，98与63的最大公约数是7。
练习2：用更相减损术求两个正数84与72的最大公约数。
(12)
练习
用更相减损术法求下列两个正整数的最大公约数
①225 135 ②98 196 ③72 168 ④153 119
第一步,给定两个正整数m,n(m＞n)
第二步,计算m除以n所得到余数r
第三步,m=n,n=r
第四步,若r=0,则m,n的最大公约数等于m;否则返回第二步
辗转相除法求最大公约数算法步骤：
否
开始
输入两个正数m,n
r=m MOD n
r=0?
输出m
结束
m=n
n=r
是
程序框图
小结
1、辗转相除法方法
2、更相减损术的步骤：
第一步 任意给定两个正整数，判断它们是不是偶数，若是用2约简，若不是执行第二步，
第二步 以较大的数减去较小的数，接着把所得差与较小的数比较，并以大数减小数，继续这个操作，直到所得数相等为止，则这个数或者这个数与约简的数的乘积就是所求的最大公约数。