A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

这个是参考别人的代码编出来的,我不是很明白为什么用碾除法就能得到两个数的最大公约数,有知道的同学分享一下的咩!!???

QQ图片20150908203335.png (116.53 KB, 下载次数: 5)

QQ图片20150908203335.png

1 个回复

倒序浏览
设a和b的最大公约数是x。设a>b。
∵a%x=0,b%x=0
∴(b*n)%x=0
∴(a-b*n)%x=0.//同余具有可加减性。......[1]
设n=[a÷b]//取整除法,
则a-b*n就成为了a÷b的余数。
∴(a%b)%x=0......[2]  //和[1]为相同的式子
于是a和b的最大公约数,同时也是a÷b的余数的最大公约数。
于是求最大公约数的时候,可以选择这3个数中,较小的两个数进行,不影响最大公约数的整除性。
因此使用取余的方法不断缩小a和b的值的时候,最大公约数的整除性仍然传递并且保留下来了。
最后当a%b=0的时候,b就被a整除了。于是在不断取余数的过程中,最大公约数就出现了。//while循环的终止条件是b=0
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马