将小数化简为分数的算法 [英] Algorithm for simplifying decimal to fractions

问题描述

我尝试编写一个算法将小数化简为分数，结果发现这并不太简单.

例如将 0.333333... 写成 1/3.

或0.1666667，即1/6.

令人惊讶的是，我在网上查看了所有我发现的代码，要么太长，要么在某些情况下不起作用.更令人讨厌的是，它们不适用于循环小数.然而，我想知道这里是否会有数学家/程序员了解将小数简化为分数的所有相关过程.有人吗?

解决方案

其他人给你的算法通过计算 连续分数.这给出了保证非常非常快速地收敛的分数序列.然而，不能保证给你在实数的距离 epsilon 内的最小分数.要找到您必须走Stern-Brocot 树.>

要做到这一点，您需要减去地板以获得 [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如果 x <错误:返回 (n, 1)elif 1 - 错误 <X:返回 (n+1, 1)# 较低的分数是 0/1下_n = 0下_d = 1# 上面的分数是1/1上_n = 1上_d = 1而真:# 中间分数是 (lower_n + upper_n)/(lower_d + upper_d)middle_n = lower_n + upper_nmiddle_d = lower_d + upper_d# 如果 x + 错误 <中间如果 middle_d * (x + error) <中间_n:# middle 是我们的新鞋面upper_n = middle_nupper_d = middle_d# Else If 中间 <x - 错误elif middle_n <(x - 错误) * middle_d:# middle 是我们的新下层下_n = 中_nlower_d = middle_d# Else中间是我们最好的分数别的:返回 (n * middle_d + middle_n, middle_d)

I tried writing an algorithm to simplify a decimal to a fraction and realized it wasn't too simple.

Write 0.333333... as 1/3 for example.

Or 0.1666667, which is 1/6.

Surprisingly I looked online and all the codes I found where either too long, or wouldn't work in some cases. What was even more annoying was that they didn't work for recurring decimals. I was wondering however whether there would be a mathematician/programmer here who understands all the involved processes in simplifying a decimal to a fraction. Anyone?

解决方案

The algorithm that the other people have given you gets the answer by calculating the Continued Fraction of the number. This gives a fractional sequence which is guaranteed to converge very, very rapidly. However it is not guaranteed to give you the smallest fraction that is within a distance epsilon of a real number. To find that you have to walk the Stern-Brocot tree.

To do that you subtract off the floor to get the number in the range [0, 1), then your lower estimate is 0, and your upper estimate is 1. Now do a binary search until you are close enough. At each iteration if your lower is a/b and your upper is c/d your middle is (a+c)/(b+d). Test your middle against x, and either make the middle the upper, the lower, or return your final answer.

Here is some very non-idiomatic (and hence, hopefully, readable even if you don't know the language) Python that implements this algorithm.

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)

这篇关于将小数化简为分数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！