9512.net
甜梦文库
当前位置:首页 >> 数学 >>

高中数学必修三第一章08辗转相除法与更相减损术



No.1 middle school ,my love !

高中数学人教A版 必修三· 第1章 算法初步
四川省成都市新都一中 肖 宏

No.1 middle school ,my love !

第8课时 辗转相除法与 更相减损术
? 在初中,我们学习过求两个正整数的最大公约 数的方法,你能求

出65与52的最大公约数吗?如 果两个正整数的数值比较大,而且不易观察出 来,那么我们又怎么快速准确地求出它们的公 约数呢?例如:你有哪些方法可以求出2016与 1908的最大公约数呢? ? 可以采用辗转相除法和更相减损术求出两个 整数的最大公约数.

No.1 middle school ,my love !

? 预学1:辗转相除法的定义 ? 辗转相除法:用于求两个数的最大公约数的一 种方法,这种算法是由欧几里得在公元前300年 左右首先提出的,因而又叫欧几里得算法.

? 利用辗转相除法求最大公约数的步骤如下: ? 第一步,用较大的数m除以较小的数n,得到一个 商q0和一个余数r0. ? 第二步,若r0=0,则n为m,n的最大公约数;若r0≠0, 则用除数n除以余数r0得到一个商q1和一个余 数 r1 . ? 第三步,若r1=0,则r1为m,n的最大公约数;若 r1≠0,则用除数r0除以余数r1得到一个商q2和一 个余数r2. ? …… ? 依次计算直至rn=0,此时所得到的rn-1即为所 求的最大公约数.

No.1 middle school ,my love !

? 想一想:如何利用辗转相除法求解2016与1908 的最大公约数? ? 【解析】利用辗转相除法求解,得到最大公约 数为36,求解过程如下: ? 2016=1908×1+108, ? 1908=108×17+72, ? 108=72×1+36, ? 72=36×2.

No.1 middle school ,my love !

No.1 middle school ,my love !

? 预学2:更相减损术的定义 ? 更相减损术:任给两个正整数(若是偶数,先用2

约简),以较大的数减去较小的数,接着把所得的
差与较小的数比较,并以大数减小数,直到所得

的数相等为止,则这个数(等数)或这个数与约简
的数的乘积就是所求的最大公约数.

? 利用更相减损术求最大公约数的步骤如下: ? 第一步,任意给定两个正整数,判断它们是否都 是偶数.若是,用2约简;若不是,执行第二步. ? 第二步,把较大的数减去较小的数,把较小的数 与所得的差比较,并以大数减小数.继续这个操 作,直到所得的数相等为止,则这个数(等数)或 这个数与约简的数的乘积就是所求的最大公约 数. ? 涉及多个正整数寻求最大公约数时,对任意两 个正整数运用辗转相除法或更相减损术求出最 大公约数,再与第三个正整数继续求最大公约 数,……直到最后一个正整数.

No.1 middle school ,my love !

? 想一想:如何利用更相减损术求出2016与1908的最大公 约数?与辗转相除法比较,哪一种方法简单快捷? ? 【解析】先将2016与1908分别除以2,得到1008和954,再 除以2,得到504和477,再利用更相减损术求解,得到最大 公约数为36,求解过程如下: ? 504-477=27,

No.1 middle school ,my love !

? 477-27=450, 450-27=423, 423-27=396,
? 396-27=369, 369-27=342, …

? 45-27=18,

27-18=9,

18-9=9,

? 所以504和477的最大公约数为9,所以2016与1908的最 大公约数为2×2×9=36.辗转相除法比较简单快捷.

? ? ? ? ? ? ? ? ? ?

预学3:辗转相除法的程序步骤和程序语言 程序: INPUT m,n DO r=m MOD n m= n n=r LOOP UNTIL r=0 PRINT m END

No.1 middle school ,my love !

No.1 middle school ,my love !

? 议一议:r=m MOD n代表什么含义?为什么需
要进行m=n和n=r的赋值?

? 【解析】r=m MOD n代表r是m÷n所得的余
数,由于需要反复由除数去除余数再取余数,相 当于反复运算第一步的过程,所以需要进行赋 值代换.

? ? ? ? ? ? ? ? ? ? ? ?

预学4:更相减损术的程序步骤和程序语言 程序: INPUT m,n DO IF m>n THEN m=m-n ELSE n=n-m END IF LOOP UNTIL m=n PRINT m END

No.1 middle school ,my love !

No.1 middle school ,my love !

? 想一想:上述程序中包含哪些结构? ? 【解析】顺序结构、条件结构和循环结构.

No.1 middle school ,my love !

? 1.利用辗转相除法求最大公约数 ? 例1、求1734,816,1343的最大公约数. ? 【方法指导】本题可运用辗转相除法求得最 大公约数,也可以运用更相减损术进行求解, 运用辗转相除法求得最大公约数的步骤较少, 而更相减损术运算简易.

No.1 middle school ,my love !

? ? ? ? ? ? ? ? ? ?

【解析】用辗转相除法. 先求1734与816的最大公约数, 1734=816×2+102; 816=102×8; 所以1734与816的最大公约数为102. 再求102与1343的最大公约数, 1343=102×13+17; 102=17×6. 所以1343与102的最大公约数为17. 即1734,816,1343的最大公约数为17.

No.1 middle school ,my love !

? 变式训练1、数4557,1953,5115的最大公约数 是( ). ? A.31 B.93 C.217 D.651 ? 【解析】先求4557和1953的最大公约数: ? 4557=1953×2+651,1953=651×3,所以这 两个数的最大公约数为651. ? 再求651和5115的最大公约数: ? 5115=651×7+558,651=558×1+93,558= 93×6,所以这两个数的最大公约数为93. ? 综上所述,已知三个数的最大公约数为93. ? 【答案】B

No.1 middle school ,my love !

? 2.利用更相减损术求最大公约数 ? 例2、用更相减损术求440与556的最大公约 数. ? 【方法指导】利用更相减损术,较大的数减 去较小的数,直到差与较小的数相等. ? 【解析】556-440=116,440-116=324,324 -116=208,208-116=92,116-92=24,92- 24=68,68-24=44,44-24=20,24-20= 4,20-4=16,16-4=12,12-4=8,8-4=4, 所以440与556的最大公约数为4.

No.1 middle school ,my love !

? 变式训练2、用更相减损术求561与255的最
大公约数.

? 【解析】561-255=306,306-255=51,255
-51=204,204-51=153,153-51=102,102 -51=51,所以561与255的最大公约数为51.

No.1 middle school ,my love !

? 3.利用辗转相除法求最大公约数并用更相减
损术检验

? 例3、利用辗转相除法求228与1995的最大公
约数,并用更相减损术检验. ? 【方法指导】将1995作为大数,228作为小数, 执行辗转相除法和更相减损术的步骤即可.

No.1 middle school ,my love !

? 【解析】辗转相除法:1995=228×8+ 171,228=171×1+57,171=57×3,所以228 与1995最大公约数为57. ? 用更相减损术检验:1995-228=1767,1767- 228=1539,1539-228=1311,1311-228= 1083,1083-228=855,855-228=627,627- 228=399,399-228=171,228-171=57,171 -57=114,114-57=57,所以228与1995最大 公约数为57.

No.1 middle school ,my love !

? 变式训练3、利用辗转相除法求98与63的最
大公约数,并用更相减损术检验.

? 【解析】98=63×1+35,63=35×1+28,35
=28×1+7,28=7×4,所以98与63的最大公 约数是7. ? 用更相减损术检验:98-63=35,63-35= 28,35-28=7,28-7=21,21-7=14,14-7=

7,所以98与63的最大公约数是7.

No.1 middle school ,my love !

? 1.利用辗转相除法求给定的两个数的最大公约 数,即用数对中较大的数除以较小的数,若余数 不为零,则将余数和较小的数构成新的数对,再 重复上述步骤,直至大数被小数除尽,则此时所 得较小数就是原来两个数的最大公约数. ? 2.利用更相减损术求两个正整数的最大公约数 时,若两个正整数都是偶数,则用2约简;也可以不 除以2,直接求最大公约数,这样不影响最后结果. ? 3.当两个整数的差较大时,利用辗转相除法计算 的次数较少.

No.1 middle school ,my love !

? (2015年新课标全国Ⅱ卷)下边程序框图的算法
思路源于我国古代数学名著《九章算术》中

的“更相减损术”.执行该程序框图,若输入的a,b
分别为14,18,则输出的a=( )

? A.0

B.2

C.4

D.14

No.1 middle school ,my love !

? ? ? ? ? ? ?

【解析】a=14,b=18. 第一次循环:14≠18且14<18,b=18-14=4; 第二次循环:14≠4且14>4,a=14-4=10; 第三次循环:10≠4且10>4,a=10-4=6; 第四次循环:6≠4且6>4,a=6-4=2; 第五次循环:2≠4且2<4,b=4-2=2; 第六次循环:a=b=2,跳出循环,输出a=2,故选 B. ? 【答案】B

No.1 middle school ,my love !

No.1 middle school ,my love !

第8课时 辗转相除法与 更相减损术

作业:见固学案

No.1 middle school ,my love !

Thanks
2016年12月3日



更多相关文章:
高二数学必修3第一章算法初步知识点:辗转相除法与更相减损术
高二数学对于知识点的掌握的要求是比较高的。小编准备了高二数学必修 3 第一章算法初步 知识点,希望能帮助到大家。1.3.1 辗转相除法与更相减损术 1、辗转相...
高一数学必修3同步练习:1-3-1辗转相除法与更相减损术、秦九韶算法
高一数学必修3同步练习:1-3-1辗转相除法与更相减损术、秦九韶算法_高一数学_数学_高中教育_教育专区。高一数学必修3全册同步1-3-1 辗转相除法与更相减损术、...
2015-2016学年高中数学 1.3.1辗转相除法与更相减损术、秦九韶算法课后作业 新人教A版必修3
2015-2016学年高中数学 1.3.1辗转相除法与更相减损术、秦九韶算法课后作业 新人教A版必修3_数学_高中教育_教育专区。第一课时 1.3 算法案例 辗转相除法与更...
辗转相除法和更相减损术
辗转相除法和更相减损术_其它课程_高中教育_教育专区。说课稿 课题:辗转相除法和更相减损术 尊敬的各位老师,你们好! 今天我说课的内容是人教版必修三第一章《算...
人教A版数学必修三教案:§1.3算法案例(辗转相除法与更相减损术)
人教A版数学必修三教案:§1.3算法案例(辗转相除法与更相减损术)_数学_高中教育_教育专区。备课大师:免费备课第一站! §1.3 算法案例一、教材分析在学生学习了...
人教版高中数学必修3案例辗转相除法、更相减损术和秦九韶算法(第1课时)教案
人教版高中数学必修3案例辗转相除法更相减损术和秦九韶算法(第1课时)教案_数学_高中教育_教育专区。1.3 算法案例:辗转相除法更相减损术和秦九韶算法 (第...
高中数学必修3第一章知识点总结及练习
高中数学必修3第一章知识点总结及练习_数学_高中教育_教育专区。高中数学必修3第...是当条件不满足时执行循 环 1.3.1 辗转相除法与更相减损术 1、辗转相除法...
2013-2014学年高一人教A版数学必修三配套练习 1.3.1 辗转相除法与更相减损术、秦九韶算法 Word版含解析]
2013-2014学年高一人教A版数学必修三配套练习 1.3.1 辗转相除法与更相减损术、秦九韶算法 Word版含解析]_高中教育_教育专区。2013-2014学年高一人教A版数学必...
高一数学必修三第一章
高一数学必修三第一章_数学_高中教育_教育专区。算法初步知识点 1.1.1 算法...是当条件不满足时执行循 环 1.3.1 辗转相除法与更相减损术 1、辗转相除法...
【2014-2015学年高中数学(人教A版,必修三)第一章 算法初步 §1.3 课时作业
【2014-2015学年高中数学(人教A版,必修三)第一章 算法初步 §1.3 课时作业...1.辗转相除法与更相减损术的区别和联系 (1)都是求最大公约数的方法. (2)...
更多相关标签:
高一化学必修一第一章    生物必修三第一章    高二生物必修三第一章    高一物理必修1第一章    高一数学必修1第一章    地理必修一第一章    高一地理必修一第一章    数学必修二第一章    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图