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

1、高中高中数学人教数学人教A版版必修三必修三第第1章章算法初步算法初步四川省成都市新都一中四川省成都市新都一中肖肖 宏宏No.1 middle school ，my love ！ 在初中在初中,我们学习过求两个正整数的最大公约我们学习过求两个正整数的最大公约数的方法数的方法,你能求出你能求出65与与52的最大公约数吗的最大公约数吗?如果两个正整数的数值比较大如果两个正整数的数值比较大,而且不易观察而且不易观察出来出来,那么我们又怎么快速准确地求出它们的那么我们又怎么快速准确地求出它们的公约数呢公约数呢?例如例如:你有哪些方法可以求出你有哪些方法可以求出2016与与1908的最大公约数呢的最大公约

2、数呢? 可以采用辗转相除法和更相减损术求出两个可以采用辗转相除法和更相减损术求出两个整数的最大公约数整数的最大公约数.No.1 middle school ，my love ！第第8课时课时辗转相除法辗转相除法与与更更相减损术相减损术No.1 middle school ，my love ！ 预学预学1:辗转相除法的定义辗转相除法的定义 辗转相除法辗转相除法:用于求两个数的最大公约数的一用于求两个数的最大公约数的一种方法种方法,这种算法是由欧几里得在公元前这种算法是由欧几里得在公元前300年年左右首先提出的左右首先提出的,因而又叫欧几里得算法因而又叫欧几里得算法.No.1 middle sch

3、ool ，my love ！ 利用利用辗转相除法求最大公约数的步骤如下辗转相除法求最大公约数的步骤如下: 第一步第一步,用较大的数用较大的数m除以较小的数除以较小的数n,得到一个得到一个商商q0和一个余数和一个余数r0. 第二步第二步,若若r00,则则n为为m,n的最大公约数的最大公约数;若若r00,则用除数则用除数n除以余数除以余数r0得到一个商得到一个商q1和一个余和一个余数数r1. 第三步第三步,若若r10,则则r1为为m,n的最大公约数的最大公约数;若若r10,则用除数则用除数r0除以余数除以余数r1得到一个商得到一个商q2和一和一个余数个余数r2. 依次计算直至依次计算直至rn0,此

4、时所得到的此时所得到的rn1即为所即为所求的最大公约数求的最大公约数.No.1 middle school ，my love ！ 想一想想一想:如何利用辗转相除法求解如何利用辗转相除法求解2016与与1908的最大公约数的最大公约数? 【解析】利用辗转相除法求解【解析】利用辗转相除法求解,得到最大公约得到最大公约数为数为36,求解过程如下求解过程如下: 201619081108, 19081081772, 10872136, 72362.No.1 middle school ，my love ！ 预学预学2:更相减损术的定义更相减损术的定义 更相减损术更相减损术:任给两个正整数任给两个正整数(

5、若是偶数若是偶数,先用先用2约简约简),以较大的数减去较小的数以较大的数减去较小的数,接着把所得的接着把所得的差与较小的数比较差与较小的数比较,并以大数减小数并以大数减小数,直到所得直到所得的数相等为止的数相等为止,则这个数则这个数(等数等数)或这个数与约简或这个数与约简的数的乘积就是所求的最大公约数的数的乘积就是所求的最大公约数.No.1 middle school ，my love ！ 利用利用更相减损术求最大公约数的步骤如下更相减损术求最大公约数的步骤如下: 第一步第一步,任意给定两个正整数任意给定两个正整数,判断它们是否都判断它们是否都是偶数是偶数.若是若是,用用2约简约简;若不是若不

6、是,执行第二步执行第二步. 第二步第二步,把较大的数减去较小的数把较大的数减去较小的数,把较小的数把较小的数与所得的差比较与所得的差比较,并以大数减小数并以大数减小数.继续这个操继续这个操作作,直到所得的数相等为止直到所得的数相等为止,则这个数则这个数(等数等数)或或这个数与约简的数的乘积就是所求的最大公约这个数与约简的数的乘积就是所求的最大公约数数. 涉及多个正整数寻求最大公约数时涉及多个正整数寻求最大公约数时,对任意两对任意两个正整数运用辗转相除法或更相减损术求出最个正整数运用辗转相除法或更相减损术求出最大公约数大公约数,再与第三个正整数继续求最大公约再与第三个正整数继续求最大公约数数,直

7、到最后一个正整数直到最后一个正整数.No.1 middle school ，my love ！ 想一想想一想:如何利用更相减损术求出如何利用更相减损术求出2016与与1908的最大公的最大公约数约数?与辗转相除法比较与辗转相除法比较,哪一种方法简单快捷哪一种方法简单快捷? 【解析】先将【解析】先将2016与与1908分别除以分别除以2,得到得到1008和和954,再再除以除以2,得到得到504和和477,再利用更相减损术求解再利用更相减损术求解,得到最大得到最大公约数为公约数为36,求解过程如下求解过程如下: 50447727, 47727450, 45027423, 42327396, 39

8、627369, 36927342, 452718, 27189, 1899, 所以所以504和和477的最大公约数为的最大公约数为9,所以所以2016与与1908的最的最大公约数为大公约数为22936.辗转相除法比较简单快捷辗转相除法比较简单快捷.No.1 middle school ，my love ！ 预预学学3:辗转相除法的程序步骤和程序语言辗转相除法的程序步骤和程序语言 程序程序: INPUTm,n DO rm MOD n mn nr LOOP UNTIL r0 PRINTm ENDNo.1 middle school ，my love ！ 议一议议一议:rm MOD n代表什么含义代

9、表什么含义?为什么需为什么需要进行要进行mn和和nr的赋值的赋值? 【解析】【解析】rm MOD n代表代表r是是mn所得的余所得的余数数,由于需要反复由除数去除余数再取余数由于需要反复由除数去除余数再取余数,相相当于反复运算第一步的过程当于反复运算第一步的过程,所以需要进行赋所以需要进行赋值代换值代换.No.1 middle school ，my love ！ 预学预学4:更相减损术的程序步骤和程序语言更相减损术的程序步骤和程序语言 程序程序: INPUTm,n DO IFmnTHEN mmn ELSE nnm END IF LOOP UNTILmn PRINTm ENDNo.1 middl

10、e school ，my love ！ 想一想想一想:上述程序中包含哪些结构上述程序中包含哪些结构? 【解析】顺序结构、条件结构和循环结构【解析】顺序结构、条件结构和循环结构.No.1 middle school ，my love ！ 1.利用辗转相除法求最大公约数利用辗转相除法求最大公约数 例例1、求求1734,816,1343的最大公约数的最大公约数. 【方法指导】本题可运用辗转相除法求得最【方法指导】本题可运用辗转相除法求得最大公约数大公约数,也可以运用更相减损术进行求解也可以运用更相减损术进行求解,运用辗转相除法求得最大公约数的步骤较少运用辗转相除法求得最大公约数的步骤较少,而更相减损

11、术运算简易而更相减损术运算简易.No.1 middle school ，my love ！ 【解析】【解析】用辗转相除法用辗转相除法. 先求先求1734与与816的最大公约数的最大公约数, 8161028; 所以所以1734与与816的最大公约数为的最大公约数为102. 再求再求102与与1343的最大公约数的最大公约数, 102176. 所以所以1343与与102的最大公约数为的最大公约数为17. 即即1734,816,1343的最大公约数为的最大公约数为17.No.1 middle school ，my love ！ 变变式训练式训练1、

12、数数4557,1953,5115的最大公约数的最大公约数是是(). A.31B.93C.217D.651 【解析】先求【解析】先求4557和和1953的最大公约数的最大公约数: 455719532651,19536513,所以这所以这两个数的最大公约数为两个数的最大公约数为651. 再求再求651和和5115的最大公约数的最大公约数: 51156517558,651558193,558936,所以这两个数的最大公约数为所以这两个数的最大公约数为93. 综上所述综上所述,已知三个数的最大公约数为已知三个数的最大公约数为93. 【答案】【答案】BNo.1 middle school ，my lov

13、e ！ 2.利用更相减损术求最大公约数利用更相减损术求最大公约数 例例2、用用更相减损术求更相减损术求440与与556的最大公约的最大公约数数. 【方法指导】利用更相减损术【方法指导】利用更相减损术,较大的数减较大的数减去较小的数去较小的数,直到差与较小的数相等直到差与较小的数相等. 【解析】【解析】556440116,440116324,324116208,20811692,1169224,922468,682444,442420,24204,20416,16412,1248,844,所以所以440与与556的最大公约数为的最大公约数为4.No.1 middle school ，my lov

14、e ！ 变变式训练式训练2、用用更相减损术求更相减损术求561与与255的最的最大公约数大公约数. 【解析】【解析】561255306,30625551,25551204,20451153,15351102,1025151,所以所以561与与255的最大公约数为的最大公约数为51.No.1 middle school ，my love ！ 3.利用辗转相除法求最大公约数并用更相减利用辗转相除法求最大公约数并用更相减损术检验损术检验 例例3、利用利用辗转相除法求辗转相除法求228与与1995的最大公的最大公约数约数,并用更相减损术检验并用更相减损术检验. 【方法指导】将【方法指导】将1995作为

15、大数作为大数,228作为小数作为小数,执行辗转相除法和更相减损术的步骤即可执行辗转相除法和更相减损术的步骤即可.No.1 middle school ，my love ！ 【解析】【解析】辗转相除法辗转相除法:19952288171,228171157,171573,所以所以228与与1995最大公约数为最大公约数为57. 用更相减损术检验用更相减损术检验:19952281767153922813111083228855,855228627,627228399,399228171,22817157,17157114,1145757,所以所以2

16、28与与1995最大最大公约数为公约数为57.No.1 middle school ，my love ！ 变变式训练式训练3、利用利用辗转相除法求辗转相除法求98与与63的最的最大公约数大公约数,并用更相减损术检验并用更相减损术检验. 【解析】【解析】9863135,6335128,352817,2874,所以所以98与与63的最大公的最大公约数是约数是7. 用更相减损术检验用更相减损术检验:986335,633528,35287,28721,21714,1477,所以所以98与与63的最大公约数是的最大公约数是7.No.1 middle school ，my love ！ 1.利用辗转相除法

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

18、果这样不影响最后结果. 3.当两个整数的差较大时当两个整数的差较大时,利用辗转相除法计算利用辗转相除法计算的次数较少的次数较少. (2015年新课标全国年新课标全国卷卷)下边程序框图的算法下边程序框图的算法思路源于我国古代数学名著九章算术中思路源于我国古代数学名著九章算术中的的“更相减损术更相减损术”.执行该程序框图执行该程序框图,若输入的若输入的a,b分别为分别为14,18,则输出的则输出的a() A.0B.2C.4D.14No.1 middle school ，my love ！ 【解析】【解析】a14,b18. 第一次循环第一次循环:1418且且144,a14410; 第三次循环第三次循环:104且且