辗转相除法与更相减损术.doc

课 题
辗转相除法与更相减损术
编 号
07
学时
1
年级备课组
高一数学组
主备人
岳杨勇
审核人
高一数学组
时间

重点难点
 学习重点：理解辗转相除法与更相减损术求最大公约数的方法
学习难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言
学习目标

1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析
2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序
知识链接

自主学习

熟读文本

【自主学习】认真自学课本34-37.
1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.
2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.
合作探究（一）:辗转相除法
思考 1:18与30的最大公约数是多少？你是怎样得到的？
思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？

思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？

思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？

学习指导

自主学习

理解文本

思考5:该算法的程序框图如何表示？该程序框图对应的程序如何表述？

合作探究（二）:更相减损术
思考1:设两个正整数m>n，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约数为多少？

思考2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？

学习指导

合作学习

质疑文本
思考3:该算法的程序框图如何表示？该程序框图对应的程序如何表述？

合作探究（三）:辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以 为主，更相减损术以 为主，计算次数上辗转相除法计算次数相对 ，特别当两个数字大小区别较大时计算次数的区别较明显
（2）从结果体现形式来看，辗转相除法体现结果是 则得到，而更相减损术则以 相等而得到
【自我检测】
1．分别用辗转相除法和更相减损术求168与93的最大公约数.
辗转相除法：

更相减损术:

学习指导

巩固提升
2．用辗转相除法求840与1785的最大公约数.

3．用更相减损术求612与468的最大公约数

自我感悟
【本节思维导图】

我的疑问：

我的收获：