Python-এ দিয়ে गये কনস্ট্রেইন্ট ব্যবহার করে min এবং max-এর মাঝপথে কমন ফ্র্যাকশন খুঁজে বের করার প্রোগ্রাম

মান লেট maximum এবং minimum দুটি লং ইন্টিজার মান। আমাদের একটি কমন ফ্র্যাকশন n/d খুঁজে বের করতে হবে যাতে min <= d <= max। এবং |n/d - pi| সবচেয়ে ছোট। এখানে pi = 3.14159265... এবং যদি একাধিক ফ্র্যাকশন এই কন্ডিশন মেনে চলে, তবে সবচেয়ে ছোট হর বিশিষ্ট ফ্র্যাকশনটি রিটার্ন করুন।

তাহলে, যদি ইনপুট হয় minimum = 1 maximum = 10, তবে আউটপুট হবে 22/7।

এটি সমাধান করতে, আমরা নিচের পদক্ষেপগুলো অনুসরণ করব −

• P := একটি ফ্র্যাকশন (5706674932067741 / 1816491048114374) - 3
• a := 0, b := 1, c := 1, d := 1
• farey := জোড়ার একটি অ্যারে, এতে প্রাথমিকভাবে দুটি জোড়া আছে (a, b) এবং (c, d)
• নিচের লুপটি বেনা শর্তে চালান -
  • f := b + d
  • যদি f > maximum - minimum, তবে
    • লুপ থেকে বের হোন
  • e := a + c
  • জোড়া (e, f) farey-র শেষে ইনসার্ট করুন
  • যদি P < (e/f)-এর মান, তবে
    • c := e এবং d := f
  • অন্যথায়,
    • a := e এবং b := f
• p_min := floor of (P * minimum)
• যখন minimum <= maximum, করুন
  • c := 0, d := 0
  • farey-র প্রতিটি জোড়া (a, b) এর জন্য, করুন
    • যদি minimum + b > maximum, তবে
      • লুপ থেকে বের হোন
    • যদি |(p_min + a)/ (minimum + b) - P| < |p_min / minimum - P|, তবে
      • c := a, d := b
      • লুপ থেকে বের হোন
  • যদি d ০-এর সমান হয়, তবে
    • লুপ থেকে বের হোন
  • p_min := p_min + c
  • o minimum := minimum + d
  • o ফ্র্যাকশন (p_min + 3 * minimum) / minimum রিটার্ন করুন

উদাহরণ

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন −

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