Pythonで指定された制約を使用して、最小値と最大値の間の一般的な分数を見つけるプログラム

最大値と最小値の2つの長整数値があるとします。 min <=d<=maxとなるような一般的な分数n/dを見つける必要があります。そして|n/ d --pi |最小です。ここで、pi =3.14159265 ...であり、この条件を保持する分数が複数ある場合は、分母が最小の分数を返します。

したがって、入力が最小=1最大=10のようである場合、出力は22/7になります。

これを解決するには、次の手順に従います-

• P：=分数（5706674932067741 / 1816491048114374）-3
• a：=0、b：=1、c：=1、d：=1
• farey：=ペアの配列で、最初は（a、b）と（c、d）の2つのペアがあります
• 以下を無条件にループします-
  • f：=b + d
  • f> maximum-minimumの場合、
    • ループから抜け出す
  • e：=a + c
  • ファリーの終わりにペア（e、f）を挿入します
  • P <（e / f）の値の場合、
    • c：=eおよびd：=f
  • それ以外の場合、
    • a：=eおよびb：=f
• p_min：=フロア（P *最小）
• 最小<=最大、実行
  • c：=0、d：=0
  • ファリーの各ペア（a、b）について、
    • 最小+b>最大の場合、
      • ループから抜け出す
    • if |（p_min + a）/（最小+ b）-P | <| p_min/最小-P|、次に
      • c：=a、d：=b
      • ループから抜け出す
  • dが0と同じ場合、
    • ループから抜け出す
  • p_min：=p_min + c
  • o最小：=最小+ d
  • oリターンフラクション（p_min + 3 *最小）/最小

例

理解を深めるために、次の実装を見てみましょう-

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