1.3.1辗转相除法与更相减损术课件.ppt

1、1.3.1算法案例 一、辗转相除法与更相减损术,知识探究（一）:辗转相除法,思考1:18与30的最大公约数是多少？ 你是怎样得到的？,先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数.,思考2:对于8251与6105这两个数， 由于其公有的质因数较大， 利用上述方法求最大公约数就比较困难.,注意到8251=61051+2146， 那么8251与6105这两个数的公约数 和6105与2146的公约数有什么关系？,2146=18131+333，,148=374+0.,333=1482+37，,1813=3335+148，,8251=61051+2

2、146，,6105=21462+1813，,思考3:又6105=21462+1813，同理，6105与2146的公约数和2146与1813的公约数相等. 重复上述操作，你能得到8251与6105这两个数的最大公约数吗？,第一步，给定两个正整数m，n(mn).,第二步，计算m除以n所得的余数r.,第三步，m=n，n=r.,第四步，若r=0，则m，n的最大公约数等 于m；否则，返回第二步.,思考4:上述求两个正整数的最大公约数的方法 称为辗转相除法或欧几里得算法. 一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,思考5:该算法的程序框图如何表

3、示？,思考6:该程序框图对应的程序如何表述？,INPUT m，n,DO,r=m MODn,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,思考7:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？,INPUT m，n,WHILE n0,r=m MODn,m=n,n=r,WEND,PRINT m,END,知识探究（二）:更相减损术,98-63=35，,14-7=7.,21-7=14，,28-7=21，,35-28=7，,63-35=28，,思考1:设两个正整数mn，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等

4、. 反复利用这个原理，可求得98与63的最大公约数为多少？,第一步，给定两个正整数m，n(mn).,第二步，计算m-n所得的差k.,第三步，比较n与k的大小， 其中大者用m表示，小者用n表示.,思考2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？ 其算法步骤如何设计？,第四步，若m=n，则m，n的最大公约数 等于m；否则，返回第二步.,思考3:该算法的程序框图如何表示？,思考4:该程序框图对应的程序如何表述？,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,例1：分别用辗转相除法和更相减损术 求168与93的最大公约数.,辗转相除法：168=931+75， 93=751+18， 75=184+3， 18=36.,所以168与93的最大公约数为3,更相减损术: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.,例2：求325，130，270三个数的最大公约数.,解：因为325=1302+65，130=652， 所以325与130的最大公