পাইথনে প্রদত্ত সীমাবদ্ধতা ব্যবহার করে সর্বনিম্ন এবং সর্বোচ্চের মধ্যে সাধারণ ভগ্নাংশ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের সর্বোচ্চ এবং সর্বনিম্ন দুটি দীর্ঘ পূর্ণসংখ্যার মান আছে। আমাদের একটি সাধারণ ভগ্নাংশ n/d খুঁজে বের করতে হবে যাতে min <=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)
• নিঃশর্তভাবে নিচের মাধ্যমে লুপ করুন -
  • f :=b + d
  • যদি f> সর্বোচ্চ - সর্বনিম্ন, তারপর
    • লুপ থেকে বেরিয়ে আসুন
  • 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> সর্বোচ্চ হয়, তাহলে
      • লুপ থেকে বেরিয়ে আসুন
    • যদি |(p_min + a)/ (ন্যূনতম + b) - P| <|p_min / সর্বনিম্ন - P|, তারপর
      • c :=a, d :=b
      • লুপ থেকে বেরিয়ে আসুন
  • যদি d 0 এর সমান হয়, তাহলে
    • লুপ থেকে বেরিয়ে আসুন
  • p_min :=p_min + c
  • o সর্বনিম্ন :=সর্বনিম্ন + d
  • ও রিটার্ন ভগ্নাংশ (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