有关辗转相除法和更相减损术的问题.ppt
有关辗转相除法和更相减损术的问题,探究一,辗转相除法,思考1:在小学中我们是如何求出两个正整数的最大公约数的呢?,算法案例之求最大公约数,求以下几组正整数的最大公约数。(注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示m和n的最大公约数。)（1）（18，30）（2）（24，16）（3）（63，63）（4）（72，8）（5）（301，133）,例、求18与24的最大公约数：,6；,8；,63；,8；,7；,短除法,想一想，如何求8251与6105的最大公约数？,思考2:对于8251与6105这两个数，它们的最大公约数是多少？你是怎样得到的？,由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难.有没有其它的方法可以较简单的找出它们的最大公约数呢？,思考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+2146，,6105=21462+1813，,定义:所谓的辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,继续上面的除法,直到大数被小数除尽,则这是较小的数就是原来两个数的最大公约数,辗转相除法求两个数的最大公约数，其算法可以描述如下：,辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构,思考4：辗转相除直到何时结束？主要运用的是哪种算法结构？,如此循环，直到得到结果。,输入两个正整数m和n；,求余数r：计算m除以n，将所得余数存放到变量r中；,更新被除数和余数：m=n，n=r。,判断余数r是否为0：若余数为0则输出结果，否则转向第步继续循环执行。,第一步，给定两个正整数m，n(mn).,第二步，计算m除以n所得的余数r.,第三步，m=n，n=r.,第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.,思考5:你能把辗转相除法编成一个计算机程序吗？,程序框图,INPUT m，n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,思考6:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m、n的最大公约数的程序框图和程序分别如何表示？,INPUT m，n,WHILE r0,r=m MOD n,m=n,n=r,WEND,PRINT m,END,练习：用辗转相除法求下列两数的最大公约数：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）,45,98,24,17,二、更相减损术,九章算术是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”,意思是：,第一步：任意给定两个正整数，判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.,第二步：以较大的数减去较小的数，接着把差与较小的数比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数.,例1：用更相减损术求98与63的最大公约数.,98-63=35，,14-7=7.,21-7=14，,28-7=21，,35-28=7，,63-35=28，,因为63不是偶数，所以,所以最大公约数是7.,例2 分别用辗转相除法和更相减损术求168与93的最大公约数.,168=931+75，93=751+18，75=184+3，18=36.,辗转相除法：,更相减损术:,168-93=75，93-75=18，75-18=57，57-18=39，39-18=21，21-18=3，18-3=15，15-3=12，12-3=9，9-3=6，6-3=3.,例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.,练习:用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，给定两个正整数m，n(mn).,第二步，计算m-n所得的差k.,第三步，比较n与k的大小，其中大者用m表示，小者用n表示.,第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.,讨论:该算法的程序框图如何表示？,讨论:该程序框图对应的程序如何表述？,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,
