IT源码网

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

third_qq_23965379c3878727 2025年01月19日 程序员 10 0

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

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

0.1666667,即1/6

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

如何将小数化简为分数?

请您参考如下方法:

其他人给你的算法通过计算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) 


评论关闭
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!