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

辗转相除法与更相减损术
1.解决算法问题需经过哪些步骤？

知问
回顾：
2.循环结构的程序框图和语句？
算法分析
程序框图
程序
语句
结构
____型循环结构
__型循环结构
知问
直到型循环结构
当型循环结构
知问
5
满足条件？
是
循环体
否
满足条件？
否
循环体
是
DO
循环体
LOOP UNTIL 条件
WHILE 条件
循环体
WEND
1.编程解决问题需经过哪些步骤？

知问
回顾：
2.循环结构的程序框图和语句？
短除法：先用两个数的公约数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数。
算法分析、程序框图、程序
3.求两个正整数最大公约数的方法？
18 30
3
18与30的最大公约数为 .
2
例如：求18与30的最大公约数.
知问
3 5
（辗转相除法、更相减损术）
求8251与6105的最大公约数.
可以使用短除法吗？
9 15
问题1.
两数比较大、公约数不易观察。
困难：
知问
思考1：辗转相除法与更相减损术可以用来解决什么问题？
可以解决求两个正整数最大公约数的任何问题。
1.（例1）求8251与6105的最大公约数.
导学
知问
思考1：辗转相除法与更相减损术可以用来解决什么问题？
可以解决求两个正整数最大公约数的任何问题。
思考2：辗转相除法与更相减损术为什么可以用来解决该问题？
第一步：
1.（例1）求8251与6105的最大公约数.
导学
8251 = 6105 ×1 + 2146
结论：8251和6105的最大公约数就是6105和2146的最大公
约数.
问题2：为什么辗转相除法得到的结果是所求最大公约数？
6105 = 2146 ×2 + 1813
第二步：
结论：6105和2146的最大公约数也是2146和1813的最大公
约数.
……
最后一步：
148 = 37 ×4
最终结论：8251和6105的最大公约数也是148和37的最大公约数，即37.
+ 0.
原理：
余数为0
辗转相除法
上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法（Euclidean algorithm）.
欧几里得（公元前330年—公元前275年），古希腊数学家，被称为“几何之父”。
《几何原本》，又称《原本》，是欧几里得所著的一部数学著作，提出了平面几何五大公设，欧几里得几何，是欧洲数学的基础，被广泛认为是历史上最成功的教科书，在西方是仅次于《圣经》而流传最广的书籍。
问题3.辗转相除法求两个正整数m，n的最大公约数，其算法步骤如何设计？
第四步：重复二、三步，
直到余数为0.
第一步，给定两个正整数m，n(m>n).
第二步，计算m除以n所得的余数r.
第三步，m=n，n=r.
第四步，若r=0，则m，n的最大公约
数等于__；否则，返回第二步.
算法分析：
辗转相除法
思考：从例1可以看出辗转相除法计算的规律是什么？蕴含什么思想？
第一步：给定两个正整数；
第二步：用大数除以小数；
第三步：除数变成被除数，
余数变成除数；
算法的思想
m
问题4. 辗转相除法的算法有什么特点？
需要使用哪种基本逻辑结构？
辗转相除法是一个反复执行直到余数等于0停止的步骤，可以使用循环结构来构造算法。

回顾：构造循环结构应确定哪几部分内容？
①初始化变量
②确定循环体
③设定循环控制条件
辗转相除法
第一步，给定两个正整数m，n(m>n).
第二步，计算m除以n所得的余数r.
第三步，m=n，n=r.
第四步，若r=0，则m，n的最大公约
数等于m；否则，返回第二步.
算法分析：
初始化变量
循环体
循环控制条件
①初始化变量
②确定循环体
③设定循环控制条件
辗转相除法
练习：根据“辗转相除法”的算法分析画出程序框图。
第一步，给定两个正整数m，n(m>n).
第二步，计算m除以n所得的余数r.
第三步，m=n，n=r.
第四步，若r=0，则m，n的最大公约
数等于m；否则，返回第二步.
算法分析：
开始
输入m，n
求m除以n的余数r
m=n
n=r
r=0？
是
输出m
结束
否
小组展示
程序框图：
小组合作
小组合作，设计“辗转相除法”的计算机程序，并用例1进行验证。
程序：
INPUT m,n
DO
LOOP UNTIL
r=m MOD n
m=n
n=r
PRINT m
END
r=0
“直到型”
辗转相除法
程序框图：
程序：
INPUT m,n
WHILE
WEND
r=m MOD n
m=n
n=r
PRINT m
END
r>0
求m除以n的余数r
是
开始
输入m，n
m=n
n=r
r>0？
否
输出m
结束
“当型”
求m除以n的余数r
r=m MOD n
辗转相除法
第二步：
98 － 63 = 35
2. 用更相减损术求98与63的最大公约数.
更相减损术
问题5：类比辗转相除法的原理，谈谈为什么更相
减损术得到的结果是所求最大公约数？
第一步：
结论：98和63的最大公约数就是63和35的最大公约数.
结论：63和35的最大公约数也是35和28的最大公约数.
……
最后一步：
最终结论：98和63的最大公约数也是7和7的最大公约数，即7.
原理：
63 － 35 = 28
14 － 7 = 7
减数与差相等
《九章算术》——更相减损术
“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。”
《九章算术》其作者已不可考，现今流传的大多是在三国时期刘徽为《九章》所作的注本。它是中国古代第一部数学专著，系统总结了战国、秦、汉时期的数学成就，收录了246个数学问题及其解法，是当时世界上最简练有效的应用数学，它的出现标志中国古代数学形成了完整的体系。
《九章算术》
刘徽
更相减损术
《九章算术》——更相减损术
“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。”
翻译：
第一步：任意给定两个正整数，判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。
更相减损术
6 － 3 = 3
例2. 用更相减损术求78与36的最大公约数.
解：
78与36都是偶数
39 － 18 = 21
78与36的最大公约数为6.
“可半”
21 － 18 = 3
18 － 3 = 15
36 ÷ 2 = 18
78 ÷ 2 = 39
“可半者半之”
3 × 2 = 6
除完再乘回去
“更相减损”（辗转相减）
15 － 3 = 12
12 － 3 = 9
9 － 3 = 6
减数与差相等
更相减损术
大减小
问题6.根据更相减损术的过程，设计求两个正整数m，n最
大公约数的算法，需要用到什么逻辑结构？为什么？
第一步：任意给定两个正整数，判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。
第一步，给定两个正整数m，n(m>n).
第二步，判断m，n是否都是偶数。
若是，用2约简后两数仍记
为m，n；若不是，执行第
三步.
第三步，d=m－n.
第四步，判断“d=n”是否成立，若是，
则2kd（k是约简整数的2的
个数）为所求的最大公约数，
若不是，则将n，d中较大者
记为m，较小者记为n，返
回第三步.
算法分析：
循环结构
更相减损术
算法的思想
课堂练习
练习：分别用辗转相除法和更相减损术，
求261与319的最大公约数.
答案：261与319的最大公约数为29.
课堂小结
辗转相除法与更相减损术的区别与联系：
算法名称
辗转相除法
更相减损术
区别
计算方式
计算次数
得到结果条件
联系
用途
数学思想
除法为主
减法为主
相对较少
相对较多
余数为零
减数与差相等
适用于求最大公约数的任何问题
算法的思想
作业：
1.思考：
（1）根据更相减损术的算法画出程序框图，并写出程序.
（2）如何求三个正整数的最大公约数？
并完成下题：求4557,1953,5115的最大公约数.
2.教材P45练习1,P48习题1.3A组第1题.
3.全品练习册P15-P16.
4.预习《秦九韶算法》.
课后作业