使用 Python 中的给定约束查找最小值和最大值之间的公共分数的程序
假设我们有两个长整数值最大值和最小值。我们必须找到一个公共分数n/d，使得min<=d<=max。和|n/d-pi|是最小的。这里pi=3.14159265...并且如果有多个分数满足此条件，则返回分母最小的分数。
因此，如果输入类似于最小值=1最大值=10，那么输出将为22/7。
示例
让我们看看以下实现以获得更好的理解-
from fractions import Fraction
def solve(minimum, maximum):
P = Fraction(5706674932067741, 1816491048114374) - 3
a, b, c, d = 0, 1, 1, 1
farey = [(a,b),(c,d)]
while True:
f = b + d
if f > maximum - minimum:
break
e = a + c
farey.append((e, f))
if P < Fraction(e, f):
c, d = e, f
else:
a, b = e, f
p_min = int(P * minimum)
while minimum <= maximum:
c, d = 0, 0
for a, b in farey:
if minimum + b > maximum:
break
if abs(Fraction(p_min + a, minimum + b).real - P) < abs(Fraction(p_min, minimum).real - P):
c, d = a, b
break
if d == 0:
break
p_min += c
minimum += d
return ("{}/{}".format(p_min + 3 * minimum, minimum))
minimum = 1
maximum = 10
print(solve(minimum, maximum))输入
4, 27输出结果
22/7