1.3(1)辗转相除法ppt课件

1、12学习目标1.理解辗转相除法与更相减损术求最大公约数的原理。2.能写出两种求最大公约数方法的算法步骤与程序框图。3.会求出两个数的最大公约数，进一步体会算法的基本思想以及算法在解决问题的过程中所体现的特点。3知识探究（一）知识探究（一）: :辗转相除法辗转相除法思考思考1:181:18与与3030的最大公约数是多少？你是怎样得到的？的最大公约数是多少？你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数有的除数连乘起来即为最大公约数. . 4思考思考2:2:

2、对于对于82518251与与61056105这两个数，由于其公有的质因数较大，利用上述方法求最大公约这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难数就比较困难. .注意到注意到8251=61058251=61051+21461+2146，那么，那么82518251与与61056105这两个数的公约数和这两个数的公约数和61056105与与21462146的公约数有什么关系？的公约数有什么关系？ 5思考思考3:3:又又6105=21466105=21462+18132+1813，同理，同理，61056105与与21462146的公约数和的公约数和21462146与与1813

3、1813的公约数相等的公约数相等. .重复上述操作，你能得到重复上述操作，你能得到82518251与与61056105这两个数的最大公约数吗？这两个数的最大公约数吗？2146=18132146=18131+3331+333，148=37148=374+0.4+0.333=148333=1482+372+37，1813=3331813=3335+1485+148，8251=61058251=61051+21461+2146，6105=21466105=21462+18132+1813，6以上的方法就是辗转相除法辗转相除法1.适合两个数适合两个数 公有的质因数较大时。公有的质因数较大时。2.算到什

4、么情况下，就停止计算了？算到什么情况下，就停止计算了？ 余数为零时，停止计算。余数为零时，停止计算。3.最大公约数是最大公约数是 ？除数（较小的数）？除数（较小的数）7理论迁移理论迁移(1) 1515，600(2) 117，182例例1 用辗转相除法求下列各数的最大用辗转相除法求下列各数的最大公约数公约数.8理论迁移理论迁移(1) 1515，600(2) 117，182例例1 用辗转相除法求下列各数的最大用辗转相除法求下列各数的最大公约数公约数.答案答案：(1)15 (2)139 由上述例子可以看出，辗转相除法中包含重复操作的步骤，因此可以用循环由上述例子可以看出，辗转相除法中包含重复操作的步

5、骤，因此可以用循环结构来构造算法。结构来构造算法。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否10思考思考5:5:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法. .一般地，一般地，用辗转相除法求两个正整数用辗转相除法求两个正整数m m，n n的最大公约数，算法步骤如下：的最大公约数，算

6、法步骤如下： 第一步，给定两个正整数第一步，给定两个正整数m m，n (mn (mn).n).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等的最大公约数等 于于m m；否则，返回第二步；否则，返回第二步. . 11思考思考6:6:该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否12思考思考7:7:该程序框图对应的程序如何表述？该程序框图对应的程序如何表

7、述？INPUT mINPUT m，n nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否13思考思考8:8:如果用当型循环结构构造算法，则用辗转相除法求两个正整数如果用当型循环结构构造算法，则用辗转相除法求两个正整数m m，n n的最大公约数的的最大公约数的程序框图和程序分别如何表示？程序框图和程序分别如何表示？14开始开始输入输入m，n求求m除以除以n的余数的余数rm=nr0？否否

8、输出输出m结束结束是是n=rINPUT mINPUT m，n nWHILE rWHILE r0 0r=m MOD nr=m MOD nm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND15练习练习1 1：利用辗转除法求两数：利用辗转除法求两数40814081与与2072320723的最大公约数的最大公约数. . (53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.16更相减损术更相减损术“更相减损术更相减损术”（也是求两个正整数的最大公约数的算法）（也是求两个正整数的最大公约数的算法）步骤：步骤

9、：第一步：任意给定两个正整数；判断他们是否都是偶数。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用若是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个数与约简的数的乘积继续这个操作，直到所得的减数和差相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数。就是所求的最大公约数。17例例1 1、用更相减损术求、用更相减损术求98与与63的最大公约数的最大

10、公约数（自己按照步骤求解）（自己按照步骤求解）解由于解由于63不是偶数，把不是偶数，把98和和63以大数减小数，并辗转相减以大数减小数，并辗转相减。所以，所以，98和和63的最大公约数等于的最大公约数等于7。98-63=35 63-35=2835-28=728-7=2121-7=1414-7=718更相减损是一个反复执行直到减数等于差时更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构停止的步骤，这实际也是一个循环结构 。思考九：更相减损直到何时结束？运用的是思考九：更相减损直到何时结束？运用的是哪种算法结构？哪种算法结构？辗转相除法与更相减损术辗转相除法与更相减损术 进

11、行到哪一步停止运算？进行到哪一步停止运算？1920 例例2 2 分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求168168与与9393的最大公约数的最大公约数. . 辗转相除法：辗转相除法：168=93168=931+751+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.21更相减损术更相减损术:168-93=75:168-93=75， 93-75=1893-75=18， 75-18=5775-18=57， 57-18=3957-18=39， 39-18=2139-18=21， 21-18=321-18=3， 18-3

12、=1518-3=15， 15-3=1215-3=12， 12-3=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3.22例例3 . 用两种方法求用两种方法求612与与468的最大公约数？的最大公约数？ 方法一：辗转相除法方法一：辗转相除法 612=4681+144， 468=1441+36， 144=364+0.23方法二：更相减损术方法二：更相减损术612与与468都是偶数，所以两次用都是偶数，所以两次用2约分化简约分化简612=1534 468=1174153-117=36 117-36=81 81-36=45 45-36=9 36-9=27 27-9=18 18-9=99

13、是153与117的最大公约数。94=36是是612与与468的最大公约数。的最大公约数。24比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。别较大时计算次数的区别较明显。（2 2）通过辗转相除和更相减损术来求两个数的最大公约数的案例分析，感受）通过辗转相除和更相减损术来求两个数的最大公约数的案例分析，感受其中所蕴含的算法基本思想，重点培养学生利用算法思想的逻辑思维能力。其中所蕴含的算法基本思想，重点培养学生利用算法思想的逻辑思维能力。25作业：写出更相减损术的算法。作业：写出更相减损术的算法。26程序：INPUT “a,b”;a,bi=0WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b