人教A版数学必修3第一章 算法初步1.3 算法案例 （课件19张PPT）

(共19张PPT)
1.3　算法案例

第1课时　辗转相除法与更相减损术
2019.11
课程标准 学习要求 数学素养
通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献 1.了解算法的含义，体会算法的思想
2.在分析案例的基础上了解算法的基本特征
3.理解辗转相除法与更相减损术的含义，了解其执行过程.
数学抽象

数学运算

逻辑推理
在小学，我们已经学习过求最大公约数的知识，你能求出18与30 的最大公约数吗？先用两个数公有的质因数连续去除，一直除到所得商是互质数为止，然后把所有的除数连乘起来。

18和30的最大公约数是2×3=6.如果公约数
比较大而根据我们的观察有不能得到一些公
约数，我们又应该怎样求它们的最大公约数？
比如求8251与6105的最大公约数？

问题提出
探究一：求两个数的最大公约数的算法
课堂探究
思考1　注意到8 251＝6 105×1＋2 146，那么8 251与6 105这两个数的公约数和6 105与2 146的公约数有什么关系？
又8 251-6 105=2 146？
答案　显然8 251与6 105的公约数也必是2 146的约数，同样6 105与2 146的公约数也必是8 251的约数，所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数.
探究一：求两个数的最大公约数的算法
课堂探究
思考2 求两个数的最大公约数的方法有那些？
(1)辗转相除法：又叫欧几里得算法．
(2)更相减损术：我国古代数学专著《九章算术》中介绍的一种算法。
这两种算法都是求两个正整数的____________的算法．
最大公约数
阅读课本P34~36页
1．辗转相除法
(1)辗转相除法是用于求__________________________的一种古老而有效地算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫______________.
(2)所谓辗转相除法，就是对于给定的两个正整数，用__________除以__________.若余数不为零，则将__________________构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时__________就是原来两个数的最大公约数．
两个正整数的最大公约数
欧几里得算法
较大的数
较小的数
余数和较小的数
较小的数
(3)算法步骤：
第一步，给定两个正整数m，n(m>n).
第二步，计算m除以n所得的余数r.
第三步，m＝n，n＝r.
第四步，若r＝_______，则m，n的最大公约数等于m；否则，返回第______步．
(4)程序框图．
0
二
该程序框图对应的程序如何表述？
INPUT m，n
DO
r=m MODn
m=n
n=r
LOOP UNTIL r=0
PRINT m
END



开始


输入m，n


求m除以n的余数r


m=n


n=r

r=0？

是

输出m


结束
否





开始


输入m，n


求m除以n的余数r


m=n

n>0？
否


输出m


结束
是



n=r


INPUT m，n
WHILE n>0
r=m MODn
m=n
n=r
WEND
PRINT m
END

如果用当型循环结构构造该算法？
例：用辗转相除法求两个正整数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
所以8251和6105的最大公约数为37.

例 求325，130，270三个数的最大公约数.
因为325=130×2+65，130=65×2，所以325与130的最大公约数是65.
因为270=65×4+10，65=10×6+5，10=5×2，所以65与270最大公约数是5.
故325，130，270三个数的最大公约数是5.
2．更相减损术
(1)更相减损术是我国古代数学专著____________中介绍的一种求两数最大公约数的方法．
(2)更相减损术的基本过程是：
第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用____约简；若不是，执行第二步．
第二步，以较大的数__________较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数__________为止，则这个数或这个数与约简的数的__________就是所求的最大公约数．
《九章算术》
相等
乘积
2
减去
2．更相减损术算法步骤：
第一步，输入两个正整数a，b（假设a,b不
同时为偶数，且a>b）
第二步，求a-b的差r．
第三步，如果b>r，则把b赋予a，把r赋予
b；否则把r赋予a.
第四步，若a=b，则输出a,b的最大公约数
a， 否则，返回第二步。


开始
a=r



输入a，b


r=a-b


a=b,b=r

b>r？

是

输出a


结束
否




a=b？


否
该算法的程序框图如何表示？


开始
a=r



输入a，b


r=a-b


a=b,b=r

b>r？

是

输出b


结束
否




a=b？


否
INPUT a,b
DO
r=a-b
IF b>r THEN
a=b
b=r
ELSE
a=r
END IF
LOOP UNTIL a=b
PRINT a
END
INPUT “m,n=“;m,n
IF m a=m
m=n
n=a
END IF
K=0
WHILE m MOD 2=0 AND n MOD 2=0
m=m/2
n=n/2
k=k+1
WEND
d=m- n

While d<>n
IF d>n then
m=d
ELSE
m=n
n=d
End if
d=m-n
Wend
d=2^k*d
PRINT d
End
例：用更相减损法求两个正整数的最大公约数
（1）8251和6105 （2）72与168
（1）解：8251 -6105=2146 6105 -2146=3959
3959 -2146=1813 2146 -1813=333
1813 -333 =1480 1480 -333 =1147
1147 -333 =814 814 -333 =481
481 -333 =148 333 -148 =185
185 -148 =37 148 -37 =111
111 -37 =74 74 -37 =37
所以8251和6105的最大公约数为37.

（2）解：72÷2÷2÷2=9, 168÷2÷2÷2=21
21 -9=12 12 -9=3
9 -3=6 6 -3=3
所以72和168的最大公约数为23×3=24.

1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.
归纳小结
2. 更相减损术，就是对于给定的两个正整数，首先判断这两个数是否都是偶数．若是，用2约简，也可以不除以2，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时减数或差即为原来两个数的最大公约数.
比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到
小结
作业：
P45练习：1.
P48习题1.3 A组：1.