5

以下问题的好算法是什么？

给定一个严格在 0 和 1 之间的有理数a / b ，找到一个自然的n最小化 | a / b - 1 / n |。

我能想到的最简单的算法是比较a / b和 1 / m对于m = b , b - 1, ...，当a / b ≤ 1 / m时停止，然后比较 | a / b - 1 / m | 和 | a / b - 1 / (m + 1) |。那是O ( b )。你可以做的更好吗？

4

3 回答 3

7

令 k = floor(b/a)，然后 n 必须等于 k ​​或 k+1。尝试 2 位候选人，看看哪一位获胜。这是 O(1)。

这是因为 1/(k+1) <= a/b <= 1/k 的事实，这反过来又来自不等式 k <= b/a <= k+1。

于 2011-08-21T18:39:41.803 回答
1

我相信你可以通过使用连分数在 O(1) 中做到这一点。(0, 1] 范围内的任何有理数都可以写成

1 / (a0 + 1 / (a1 + 1 / (a2 + 1 / (... an))))

此外，这种表示具有一些显着的特性。对于初学者来说，如果你在任何时候截断表示，你会得到一个非常好的有理数近似值。特别是，如果您只是在

1 / a0

那么分数 a/b 将介于 1/a0 和 1/(a0+1) 之间。因此，如果我们可以得到 a0 的值，那么您只需检查上述两个数字，看看哪个更接近。

第二个重要属性是获得 a0 值的好方法：它由 b/a 的商给出。换句话说，您可以找到最接近的分数，如下所示：

  1. 使用整数除法计算 x = b / a。
  2. 检查 1/x 或 1/(x+1) 是否更接近 a/b 并输出该结果。

如果 a 和 b 适合机器字，则运行时间为 O(1)。

于 2011-08-21T18:41:34.057 回答
0

正如评论中所建议的，您最好的选择是使用天花板和地板功能。

a / b如果给出了你的理性，0 <= x <= 1那么你可以简单地这样做：

int Rationalize(double x)
{
    int n1 = floor(1 / x);
    int n2 = ceiling(1 / x);

    double e1 = abs(x - 1.0 / n1);
    double e2 = abs(x - 1.0 / n2);

    if (e1 < e2) return n1;
    else return n2;
}

（假设腹肌、地板和天花板是预定义的）

于 2011-08-21T18:41:34.250 回答