Chương trình tìm phân số chung giữa tối thiểu và tối đa bằng cách sử dụng ràng buộc đã cho trong Python

Giả sử chúng ta có hai giá trị nguyên dài lớn nhất và nhỏ nhất. Chúng ta phải tìm một phân số chung n / d sao cho min <=d <=max. Và | n / d - pi | là nhỏ nhất. Ở đây pi =3,14159265 ... và nếu có nhiều hơn một phân số giữ điều kiện này, thì trả về phân số có mẫu số nhỏ nhất.

Vì vậy, nếu đầu vào giống như tối thiểu =1 tối đa =10, thì đầu ra sẽ là 22/7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• P:=a fraction (5706674932067741/1816491048114374) - 3
• a:=0, b:=1, c:=1, d:=1
• ethery:=một mảng các cặp, ban đầu nó có hai cặp (a, b) và (c, d)
• Lặp lại những điều sau đây một cách vô điều kiện -
  • f:=b + d
  • nếu f> tối đa - tối thiểu, thì
    • ra khỏi vòng lặp
  • e:=a + c
  • chèn cặp (e, f) vào cuối dấu ngoặc kép
  • nếu P
  • c:=e và d:=f
• theo chiều dọc,
  • a:=e và b:=f

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

4, 27

Đầu ra

22/7