辗转相除法与更相减损术、秦九韶算法.ppt

算法案例
第1课时 辗转相除法与更相减损术、秦九韶算法
、秦九韶算法的学****进一步体会算法思想;
,理解掌握辗转相除法与更相减损术、秦九韶算法的含义;(重点)
;(重点)
．(难点)
1. 回顾算法的三种表述：
自然语言
程序框图（三种逻辑结构）
程序语言（五种基本语句）
.
先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.
例如：求两个正整数的最大公约数
（1）求25和35的最大公约数
（2）求49和63的最大公约数
所以，25和35的最大公约数为5.
所以，49和63的最大公约数为7.
除了用这种方法外还有没有其他方法吗？
辗转相除法 （欧几里得算法）
思考：算出8 251和6 105的最大公约数.
第一步,用两数中较大的数除以较小的数，求得商和余数8 251=6 105×1+2 146.
结论：8 251和6 105的公约数就是6 105和2 146的公约数，求8 251和6 105的最大公约数，只要求出6 105和2 146的最大公约数就可以了.
为什么？
第二步,对6 105和2 146重复第一步的做法，6 105=2 146×2+1 813，同理6 105和2 146的最大公约数也是2 146和1 813的最大公约数.
完整的过程:
8 251=6 105×1+2 146
6 105=2 146×2+1 813
2 146=1 813×1+333
1 813=333×5+148
333=148×2+37
148=37×4+0
显然37是148和37的最大公约数，也就是8 251和6 105的最大公约数.
所谓辗转相除法，就是对于给定的两个数，，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数.
（1）辗转相除法
（2）算法步骤
第一步,输入两个正整数m,n(m>n).
第二步,计算m除以n所得的余数r.
第三步,m=n,n=r.
第四步,若r＝0,则m,n的最大公约数等于m；否则转到第二步.
第五步,输出最大公约数m.
（3）程序框图
（4）程序
INPUT m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END