算法案例学案 Word版

年级
高一
科目
数学
必修3
第一章
算法初步
1.3算法案例
班级________学习小组号________
姓名_____________
小组评价____________
教师评价____________
使用日期____________
算法案例
-----辗转相除法与更相减损术
【使用说明即学法指导】
精读课本必修Ⅲ的第34-37页。
限时完成导学案合作探究部分，书写规范。
找出自己的疑惑和需要讨论的问题准备课上讨论质疑。
【教学目标】
1.
理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2．基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。
3．通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献，在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力。
●预习案
一、自主探究
1.
辗转相除法是用于求
的一种方法，这种算法是由欧几里得在公元前300年左右提出，因而又叫
。
2.
所谓辗转相除法，就是对于给定的两个数，用??
除以
，若余数不为零，则将
构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时
就是原来两个数的最大公约数。
3.
更相减损数的基本过程是：对于给定的两个数，用
，接着把所得的
与
比较，并以大数减小数，继续这个操作，直到所得的数
为止，则这个数就是所求的最大公约数。
二、预习思考：
1．小学学过的求两个正整数的最大公约数的方法是什么？
2．求以下几组正整数的最大公约数。
（1）（18，30）
（2）（24，16）
（3）（63，63）
（4）（72，8）
3.
求8251与6105的最大公约数，用上述方法适合吗？通过预习，你知道怎么做吗？
●探究案
合作探究：
一、
辗转相除法（欧几里得算法）
例1、利用辗转相除法求8251和6105的最大公约数。
练习：用辗转相除法求1457和188的最大公约数。
思考1：从上面的两个例子中可以看出计算的规律是什么？辗转相除法直到何时结束？主要运用的是哪种算法结构？
思考2：利用上述规律，对于两个数，你能画出一个用辗转相除法求其最大公约数的程序框图，并且设计一个程序吗？
二、更相减损术
算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。
例2、用更相减损术求98与63的最大公约数。
练习：用更相减损术求下列两数的最大公约数：
（1）（225，135）
（2）（98，196）
（3）（72，168）
（4）（153，119）
更相减损术与辗转相除法相比较,你有什么发现?你能根据更相减损术设计程序并画出程序框图,求两个正整数的最大公约数吗?
●课堂小结
1知识方面
2思想方法
●训练案
1、整数49和91的最大公约数是（
）
A、7
B、9
C、14
D、49
2、若m
MOD3=2，则m的取值可以是（
）
A、2005
B、2006
C
、2007
D、2008
3、下列各组关于最大公约数的说法中不正确的是（
）
A、16和12的最大公约数是4
B、78和36的最大公约数是6
C、85和357的最大公约数是34
D、105和315的最大公约数是105
4、求下列各组数的最大公约数：
（1）36，120；
（2）72，315；
（3）72，
120，
168
5、用辗转相除法编写求63和81的最大公约数的程序。
6、写出利用更相减损术求249和186的最大公约数的程序。
算法案例--辗转相除法与更相减损术
参考答案
预习案
一、自主探究
两个数的最大公约数，欧几里得算法。
较大的数，较小的数，余数和较小的数，较小的数。
较大的数减去较小的数，差，较小的数，相等。
二、预习思考
1.
先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.
2.
（1）
6，（2）8，（3）63，（4）8
3.
不合适，利用辗转相除法。
●探究案
合作探究：
一、
辗转相除法（欧几里得算法）
例1、解：8251＝6105×1＋2146
显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。
6105＝2146×2＋1813
2146＝1813×1＋333
1813＝333×5＋148
333＝148×2＋37
148＝37×4＋0
则37为8251与6105的最大公约数。
练习：47
思考1：规律：（1）用大数除以小数，得到余数;
（2）除数变成被除数，余数变成除数;
（3）重复第一步，直到余数为0，则较小数即为所求最大公约数。
辗转相除法是一个反复执行直到余数等于0才停止的步骤，这实际上是一个循环结构。
思考2：见下页。
二、更相减损术
例2：解：由于63不是偶数，把98和63以大数减小数，并辗转相减
98－63＝35
63－35＝28
35－28＝7
28－7＝21
21－7＝14
14－7＝7
所以，98和63的最大公约数等于7
练习：（1）45,
（2）98,
（3）24,
（4）17
思考：辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。
更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构。
●训练案
1.
A
2.
B
3.
C
4.
12，
9，
24
5.
m=81,n=63
r=m
MOD
n
WHILE
r<>0
m=n
n=r
r=m
MOD
n
WEND
PRINT
n
END
a=249
b=186
WHILE
a<>b
r=a-b
IF
b>r
THEN
a=b
b=r
ELSE
a=r
END
IF
WEND
PRINT
b
END
思考?
INPUT
“
输入
m,n
”
;
m,n
DO
r=m
MOD
n
m=n
n=r
LOOP
UNTIL
r=0
PRINT
“
最大公约数是：
”
；
m
END
INPUT
“
输入
m,n
”
;
m,n
DO
r=m
MOD
n
m=n
n=r
LOOP
UNTIL
r=0
PRINT
“
最大公约数是：
”
；
m
END
开始
输入m,n
r=m
MOD
n
m=n
n=r
r=0?
输出m
是
否
否
是
结
束
输出m
r
=
0
?
n=r
1
PAGE
7