使用 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