将 (0, 1) 中的有理数舍入到最接近的单位分数

发布于 2024-11-30 13:45:32 字数 465 浏览 1 评论 0原文

对于以下问题有什么好的算法？

给定严格介于 0 和 1 之间的有理 a / b，找到一个自然的 n 来最小化 |a > / b - 1 / n|.

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

夜未央樱花落 2024-12-07 13:45:32

设 k = Floor(b/a)，则 n 必须等于 k 或 k+1。尝试 2 个候选者，看看哪一个获胜。这是 O(1)。

这是正确的，因为 1/(k+1) <= a/b <= 1/k 这一事实又由不等式 k <= b/a <= k+1 得出。

回复收藏 0 原文

故乡的云 2024-12-07 13:45:32

我相信您可以通过使用连分数在 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 的商给出。换句话说，您可以按如下方式找到最接近的分数：

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

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

I believe that you can do this in O(1) by using continued fractions. Any rational number in the range (0, 1] can be written in the form

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

Moreover, this representation has some remarkable properties. For starters, if you truncate the representation at any point, you get an extremely good approximation to the rational number. In particular, if you just truncate this representation at

1 / a0

Then the fraction a/b will be between 1/a0 and 1/(a0+1). Consequently, if we can get the value of a0, then you can just check the above two numbers to see which is closer.

The second important property is that there is a great way of obtaining the value of a0: it's given by the quotient of b/a. In other words, you can find the closest fraction as follows:

Compute x = b / a using integer division.
Check whether 1/x or 1/(x+1) is closer to a/b and output that result.

If a and b fit into machine words, this runs in O(1) time.

回复收藏 0 原文

人海汹涌 2024-12-07 13:45:32

正如评论中所建议的，最好的选择是使用 Ceiling 和 Floor 函数。

如果您的理性 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;
}

假设abs、下限和上限为预定义）

As suggested in the comments, your best bet is to use Ceiling and Floor functions.

If your rational a / b is given as 0 <= x <= 1 then you can simply do this:

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;
}

(Where it's assumed abs, floor, and ceiling are predefined)

回复收藏 0 原文

~没有更多了~