来源:学生作业帮 编辑:搜搜考试网作业帮 分类:数学作业 时间:2024/08/17 13:20:06
关于求最大公约数算法的问题
书上是说:1.输入m、n(m为被除数,n为除数)2.m/n得余数r.3.判断r=0?是的话n为最大公约数.4.否则讲n赋给m,r赋给n,循环2.我想问为什么能这么做?(为什么能用除数除以余数一直循环?)
辗转相除法:如:求(45,72)
72/45 = 1 余 27 不等于0,再除
45 /27= 1 余 18 不等于0,再除
27/18= 1 余 9 不等于0,再除
18/9 = 2 余 0 等于0,结束.
所以 (45,72)=9