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, 0 के समान है, तो
    • लूप से बाहर आएं
  • 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