如何在不使用标准函数的情况下合理化分数？

Question

那么，如何在不使用标准功能模块的情况下编写一个找到有理数的python代码，该代码接近于f的分数？

例如，3.14=22/7

分子和分母也有限制，如：

• 分子不能大于p
• 分母不能大于q。

我的工作：

# calculates i/j upto a precision of 0.001 closer to f.
while( abs((i/j)-f)> 0.001 and i<p, j<q):
    j=j-1
    i =?, 

现在我很困惑，我应该如何修改我的i和j才能使它工作？我可以用任何方式使用Newton Raphson算法吗？

Answer 1

考虑一下这个数组[1，.. q]

然后将每个元素乘以给定的分数f，然后检查最近的元素到p。我认为该算法将在O（q）中执行。好吧，你可以改进算法来检查p或q是否更小然后做同样的事情

import math
def foo(f,p,q):
    m=9999

    for i in range(1,q+1):
        reqp=round(f*i)

        if(  abs((float(reqp)/i) -f ) <m and reqp>0 and reqp <=p ):
            m=abs(float(reqp)/i-f)
            values = [reqp,i]
    return values

print(foo(3.14,30,30))            

OUTPUT

[22.0, 7]

Answer 2

Pythons标准库有一个模块：

print(fractions.Fraction.from_float(math.pi).limit_denominator(30))

输出

22/7

蛮力方法：

import math

def approx(number, p):
    best = None
    best_dist = number
    for d in range(1, p + 1):
        n0 = int(d / number)
        for n in (n0 -1, n0, n0 + 1):
            if n <= 0:
                continue
            dist = abs(number - d / n)
            if dist < best_dist:
                best_dist = dist
                best = (d, n)
    return best


print(approx(math.pi, 30))

输出

(22, 7)

然后还有第三种选择：https://www.johndcook.com/blog/2010/10/20/best-rational-approximation/