找到最小比例因子,从一组双打中得到每个数字在整数的十分之一内

Question

假设我们有一组双打小号,这样的事情:

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尽可能小。

\n\n

这是一个使用已知算法进行充分研究的问题。然而，您应该知道，找到规范另一部分的最佳近似值是NP 困难的。据我所知，这与您的问题无关，因为您有一个固定的并且想要最小的，而不是相反。Q < qqepsilonQ

\n\n

该问题的一种算法是 (Lenstra\xe2\x80\x93Lenstra)\xe2\x80\x93Lov\xc3\xa1sz\ 的晶格缩减算法。我想知道是否可以为您找到任何好的参考资料。 这些课堂笔记提到了问题和算法，但可能没有直接帮助。维基百科有一个关于该算法的相当详细的页面，包括相当大的实现列表。

\n