读书人

求最大公约数的算法(需要考虑测量误差

发布时间: 2012-02-10 21:27:42 作者: rapoo

求最大公约数的算法(需要考虑测量误差)
如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个数,不断求余,直到整除后,最后那个除数就是了。

读书人网 >C++

热点推荐