辗转相除法和更相减损术课件

1、1.3.1 辗转相除法和更相减损术临高中学 李吉传 2019年5月8日第1页，共20页。复习1.研究一个实际问题的算法，主要从哪几方面展开？2.在程序框图中算法的基本逻辑结构有哪几种？3.在程序设计中基本的算法语句有哪几种？算法步骤、程序框图和编写程序三方面展开.顺序结构、条件结构、循环结构输入语句、输出语句、赋值语句、条件语句、循环语句第2页，共20页。一、辗转相除法 思考1:18与30的最大公约数是多少？你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数. 第3页，共20页。 思考2:对于8251与6105这两个数，它们的

2、最大公约数是多少？你是怎样得到的？ 由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难.有没有其它的方法可以较简单的找出它们的最大公约数呢？第4页，共20页。 思考3：注意到8251=61051+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？ 我们发现6105=21462+1813，同理，6105与2146的公约数和2146与1813的公约数相等. 思考4：重复上述操作，你能得到8251与6105这两个数的最大公约数吗？2146=18131+333，148=374+0.333=1482+37，1813=3335+148，8251=61051+

3、2146，6105=21462+1813，第5页，共20页。 上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.第一步，给定两个正整数m，n(mn).第二步，计算m除以n所得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步. 思考5:你能把辗转相除法编成一个计算机程序吗？第6页，共20页。程序框图开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND第7页，共20页。 思考6:如果用当型循环结构构造算法，则用辗转相除法

4、求两个正整数m、n的最大公约数的程序框图和程序分别如何表示？第8页，共20页。开始输入m，n求m除以n的余数rm=nr0？否输出m结束是n=rINPUT m，nWHILE r0r=m MOD nm=nn=rWENDPRINT mEND第9页，共20页。二、更相减损术 九章算术是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”意思是： 第一步：任意给定两个正整数，判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把差与较小的数比较，并以大

5、数减小数.继续这个操作，直到所得的数相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数.第10页，共20页。例1：用更相减损术求98与63的最大公约数.98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，因为63不是偶数，所以所以最大公约数是7.第11页，共20页。 例2 分别用辗转相除法和更相减损术求168与93的最大公约数. 168=931+75， 93=751+18， 75=184+3， 18=36.辗转相除法：第12页，共20页。更相减损术: 168-93=75， 93-75=18， 75-18=57， 57-18=39， 3

6、9-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3.第13页，共20页。例3 用更相减损术求80与36的最大公约数.第14页，共20页。 例4 求325，130，270三个数的最大公约数. 因为325=1302+65，130=652，所以325与130的最大公约数是65. 因为270=654+10，65=106+5，10=52，所以65与270最大公约数是5. 故325，130，270三个数的最大公约数是5.第15页，共20页。 练习:用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数m，n(mn). 第二步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大者用m表示，小者用n表示. 第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步. 讨论:该算法的程序框图如何表示？第16页，共20页。开始输入m，nnk？m=n是输出m结束mn？k=m-n是否n=km=k否 讨论:该程序框图对应的程序如何表述？第17页，共20页。INPUT m，nWHILE mnk=m-nIF nk THENm=nn=kELSEm=kEND IFWENDPRINT mEND开始输入m