c# - 将小数简化为分数的算法

Question

我尝试编写一个算法将小数简化为分数，并意识到它不太简单。

例如将0.333333...写为1/3。

或0.1666667，即1/6。

令人惊讶的是，我上网查看，发现所有代码要么太长，要么在某些情况下无法工作。更烦人的是它们不适用于循环小数。

如何将小数化简为分数？

Answer 1

其他人给你的算法通过计算Continued Fraction得到答案。的号码。这给出了保证非常非常快地收敛的分数序列。但是，它不能保证为您提供实数距离 epsilon 内的最小分数。要发现你必须走Stern-Brocot tree .

为此，您需要减去下限以获得 [0, 1) 范围内的数字，然后您的下限估计为 0，您的上限估计为 1。现在进行二分搜索，直到足够接近。在每次迭代中，如果你的下部是 a/b，上部是 c/d，那么中部是 (a+c)/(b+d)。对照 x 测试你的中间部分，或者使中间部分成为上部、下部，或者返回你的最终答案。

这里有一些非常不惯用的(因此，希望即使你不懂这种语言也能读懂)Python 实现了这个算法。

def float_to_fraction (x, error=0.000001):
    n = int(math.floor(x))
    x -= n
    if x < error:
        return (n, 1)
    elif 1 - error < x:
        return (n+1, 1)

    # The lower fraction is 0/1
    lower_n = 0
    lower_d = 1
    # The upper fraction is 1/1
    upper_n = 1
    upper_d = 1
    while True:
        # The middle fraction is (lower_n + upper_n) / (lower_d + upper_d)
        middle_n = lower_n + upper_n
        middle_d = lower_d + upper_d
        # If x + error < middle
        if middle_d * (x + error) < middle_n:
            # middle is our new upper
            upper_n = middle_n
            upper_d = middle_d
        # Else If middle < x - error
        elif middle_n < (x - error) * middle_d:
            # middle is our new lower
            lower_n = middle_n
            lower_d = middle_d
        # Else middle is our best fraction
        else:
            return (n * middle_d + middle_n, middle_d)