假设我们有一组 double s,如下所示:
1.11, 1.60, 5.30, 4.10, 4.05, 4.90, 4.89
我们现在想要找到最小的正整数比例因子x,s 的任何元素乘以x 在十分之一以内一个整数。
抱歉,如果这不是很清楚,请在需要时要求澄清。
请将答案限制为 C 风格语言或算法伪代码。
谢谢!
最佳答案
您正在寻找一种叫做同时丢番图近似的东西。通常的说法是你得到了实数 a_1, ..., a_n
和一个正实数 epsilon
你想找到整数 P_1, ..., P_n
和 Q
这样|Q*a_j - P_j| < epsilon
, 希望与 Q
尽可能小。
这是一个使用已知算法进行了充分研究的问题。但是,您应该知道用 Q < q
找到最佳近似值是 NP 难的。其中 q
是规范的另一部分。据我所知,这与您的问题无关,因为您有一个固定的 epsilon
想要最小的Q
,而不是相反。
该问题的一种算法是 (Lenstra–Lenstra)–Lovász 的晶格缩减算法。我想知道我是否可以为您找到任何好的引用资料。 These class notes提及问题和算法,但可能没有直接帮助。维基百科有一个 fairly detailed page在算法上,包括相当大的实现列表。
关于algorithm - 从一组 double 中找到最小的比例因子以使每个数字在整数的十分之一以内,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4361635/