पायथन में दी गई बाधा का उपयोग करके न्यूनतम और अधिकतम के बीच सामान्य अंश खोजने का कार्यक्रम

मान लीजिए कि हमारे पास अधिकतम और न्यूनतम दो लंबे पूर्णांक मान हैं। हमें एक उभयनिष्ठ भिन्न n/d इस प्रकार ज्ञात करना है कि min <=d <=max. और |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
- फेयरी में प्रत्येक जोड़ी (ए, बी) के लिए, करते हैं
  - यदि न्यूनतम + b> अधिकतम, तो
    - लूप से बाहर आएं
  - अगर |(p_min + a)/ (न्यूनतम + b) - P| <|p_min / न्यूनतम - पी|, फिर
    - c :=a, d :=b
    - लूप से बाहर आएं
- यदि d, 0 के समान है, तो
  - लूप से बाहर आएं
- p_min :=p_min + c
- ओ न्यूनतम:=न्यूनतम + घ
- ओ रिटर्न अंश (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