3986.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-8 辗转相除法与更相减损术

必修3-1-8 辗转相除法与更相减损术_数学_高中教育_教育专区。辗转相除法与更相减损术编号:必修 3-1-8 内容: P34~37 学习目标:理解辗转相除法和更相减损术...


必修3-1-8 辗转相除法与更相减损术

必修3-1-8 辗转相除法与更相减损术_数学_高中教育_教育专区。辗转相除法与更相减损术编号:必修 3-1-8 内容: P34~37 学习目标:理解辗转相除法和更相减损术...


高中数学课时训练(人教版必修三)第一章 1.3.1 辗转相除法与更相减损术(含答案)

高中数学课时训练(人教版必修三)第一章 1.3.1 辗转相除法与更相减损术(含答案)_数学_高中教育_教育专区。高中数学人教A版必修三课时训练(含答案) ...


高中数学必修三更相减损术

求等数的办法是更相减损法,实际上就是辗转相除法。 例 用更相减损术求 98 ...高中数学必修3第一章算法... 14页 免费 2013-2014学年高中数学人... 暂无...


人教A版高中数学必修三第一章算法初步1.3算法案例第一、二课时《辗转相除法与更相减损术》教案

人教A版高中数学必修三第一章算法初步1.3算法案例第一、二课时《辗转相除法与更相减损术》教案_数学_高中教育_教育专区。1.3 算法案例第一、二课时 辗转相除法...


高二数学必修3 辗转相除法与更相减损术1

高二数学必修 3 辗转相除法与更相减损术(1)教学目标 (a)知识与技能 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析。 2.基本能...


高一数学必修3同步练习:1-3-1辗转相除法与更相减损术、秦九韶算法

高一数学必修3同步练习:1-3-1辗转相除法与更相减损术、秦九韶算法_高一数学_数学_高中教育_教育专区。高一数学必修3全册同步1-3-1 辗转相除法与更相减损术、...


人教A版高中数学必修三第一章算法案例(1)第一、二课时辗转相除法与更相减损教案

人教A版高中数学必修三第一章算法案例(1)第一、二课时辗转相除法与更相减损教案_数学_高中教育_教育专区。第一、二课时 辗转相除法与更相减损术 (1)教学目标 ...


高中数学人教A版必修三同步测试 第一章:1.3.1辗转相除法与更相减损术、秦九韶算法(含答案)

高中数学人教A版必修三同步测试 第一章:1.3.1辗转相除法与更相减损术、秦九韶算法(含答案)_数学_高中教育_教育专区。高中数学人教A版必修三同步测试(含答案)...

网站首页 | 网站地图
3986 3986.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com