पायथन में सबसे लंबे फाइबोनैचि अनुक्रम की लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक अनुक्रम है जैसे X_1, X_2, ..., X_n फाइबोनैकी जैसा है अगर -

• n>=3

• X_i + X_i+1 =X_i+2 सभी के लिए i + 2 <=n

अब मान लीजिए कि एक सख्ती से बढ़ती हुई एरे ए एक अनुक्रम बना रही है, हमें ए के सबसे लंबे फाइबोनैचि-समान अनुक्रम की लंबाई का पता लगाना है। यदि ऐसा कोई अनुक्रम नहीं है, तो 0 पर लौटें।

इसलिए, यदि इनपुट ए =[1,2,3,4,5,6,7,8] जैसा है, तो आउटपुट 5 होगा क्योंकि एक अनुक्रम [1,2,3,5,8] है। लंबाई 5.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एसए:=ए के तत्वों से एक नया सेट

• अंतिम:=A का अंतिम तत्व

• B :=एक नक्शा जिसमें A में मौजूद प्रत्येक तत्व और उनकी आवृत्तियाँ शामिल हैं

• सर्वोत्तम:=0

• मैं के लिए ए के आकार में 0 से नीचे, करो

  • ए:=ए[i]

  • ए के उप-सरणी में प्रत्येक बी के लिए [इंडेक्स i+1 से अंत तक], करें

    • सी:=ए+बी

    • यदि c, एसए में मौजूद है, तो

      • बी[ए,बी] :=1 + बी[बी,सी]

      • सर्वोत्तम :=अधिकतम सर्वोत्तम और B[a,b]+2

    • अन्यथा जब c> अंतिम, तब

      • लूप से बाहर आएं

• सर्वश्रेष्ठ वापसी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

from collections import Counter
def solve(A):
   sA = set(A)
   last = A[-1]
   B = Counter()
   best = 0
   for i in reversed(range(len(A))):
      a = A[i]
      for b in A[i+1:]:
         c = a+b
         if c in sA:
            B[a,b] = 1 + B[b,c]
            best = max(best , B[a,b]+2)
         elif c>last:
            break
   return best

A = [1,2,3,4,5,6,7,8]
print(solve(A))

इनपुट

[1,2,3,4,5,6,7,8]

आउटपुट

5