算法案例 辗转相除法 更相减损术 秦九韶算法 进位制
算法案例 • 辗转相除法 • 更相减损术 • 秦九韶算法 • 进位制
辗转相除法
辗转相除法
求两个正整数的最大公约数 (1)求25和35的最大公约数 (2)求49和63的最大公约数 (1)52535 5 所以,25和35的最大公约数为5 2、求8251和6105的最大公约数
1、求两个正整数的最大公约数 （1）求25和35的最大公约数 （2）求49和63的最大公约数 2、求8251和6105的最大公约数 （1） 5 25 5 35 7 所以，25和35的最大公约数为5
辗转相除法(欧几里得算法) 观察用辗转相除法求8251和6105的最大公约数的过程 第一步用两数中较大的数除以较小的数,求得商和余数 8251=6105×1+2146 结论:8251和6105的公约数就是6105和2146的公约数,求8251和6105 的最大公约数,只要求出6105和2146的公约数就可以了 为什么呢? 第二步对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数
辗转相除法（欧几里得算法） 观察用辗转相除法求8251和6105的最大公约数的过程 第一步用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146 结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105 的最大公约数，只要求出6105和2146的公约数就可以了。 第二步对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数
完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 思考1:从上面的两个例子可以看出计 算的规律是什么? 148=37×4+0 s:用大数除以小数 显然37是148和37的最大公约s2:除数变成被除数,余数变成除数 数,也就是8251和6105的最大 公约数 s3:重复1,直到余数为0
完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 显然37是148和37的最大公约 数，也就是8251和6105的最大 公约数 思考1：从上面的两个例子可以看出计 算的规律是什么？ S1：用大数除以小数 S2：除数变成被除数，余数变成除数 S3：重复S1，直到余数为0