首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

求最大公约数的算法(需要考虑测量误差)解决方案

2012-02-10 
求最大公约数的算法(需要考虑测量误差)如639, 481〉160 (159,161也可以)假定误差较小为+/-M.[解决办法]辗

求最大公约数的算法(需要考虑测量误差)
如639, 481=〉160 (159,161也可以)
假定误差较小为+/-M.

[解决办法]
辗转扣除,行不行?
[解决办法]
说个比较笨的方法:

如果M的范围不大的话,那么就枚举所有可能。例如M=2,那么允许的两个数的范围就是:
[639-2,639+2] [481-2,481+2]
那么每个数有5种取值,一共有5*5=25种组合。对25种组合分别求GCD,选最大那个。
[解决办法]
不过,楼主你是怎么推出 639, 481 的最大公约数是 160 的?

[解决办法]
辗转相除法。
2个数,不断求余,直到整除后,最后那个除数就是了。

热点排行