algorithm - 从一组 double 中找到最小的比例因子以使每个数字在整数的十分之一以内

Question

假设我们有一组 double s，如下所示:

1.11, 1.60, 5.30, 4.10, 4.05, 4.90, 4.89

我们现在想要找到最小的正整数比例因子x，s 的任何元素乘以x 在十分之一以内一个整数。

抱歉，如果这不是很清楚，请在需要时要求澄清。

请将答案限制为 C 风格语言或算法伪代码。

谢谢!

Answer 1

您正在寻找一种叫做同时丢番图近似的东西。通常的说法是你得到了实数 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在算法上，包括相当大的实现列表。