পাইথনে দীর্ঘতম ফিবোনাচি পরবর্তী দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি ক্রম যেমন X_1, X_2, ..., X_n হল ফিবোনাচির মত যদি −

• n>=3

• X_i + X_i+1 =X_i+2 সব i + 2 <=n

এখন ধরুন একটি কঠোরভাবে ক্রমবর্ধমান অ্যারে A একটি ক্রম তৈরি করে, আমাদের A এর দীর্ঘতম ফিবোনাচি-সদৃশ অনুক্রমের দৈর্ঘ্য খুঁজে বের করতে হবে। যদি এই ধরনের কোন ক্রম না থাকে, তাহলে 0 ফেরত দিন।

সুতরাং, যদি ইনপুটটি A =[1,2,3,4,5,6,7,8] এর মত হয়, তাহলে আউটপুট হবে 5 কারণ সেখানে একটি ক্রম রয়েছে [1,2,3,5,8] দৈর্ঘ্য ৫.

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

• sA :=A

  এর উপাদান থেকে একটি নতুন সেট

• last :=A

  এর শেষ উপাদান

• B :=A এ উপস্থিত প্রতিটি উপাদান এবং তাদের ফ্রিকোয়েন্সি ধারণ করে একটি মানচিত্র

• সেরা :=0

• A এর আকার 0 থেকে নিচের জন্য, করুন

  • a :=A[i]

  • A[সূচী i+1 থেকে শেষ পর্যন্ত] এর সাবঅ্যারেতে প্রতিটি b-এর জন্য করুন

    • c :=a+b

    • যদি sA-তে c উপস্থিত থাকে, তাহলে

      • B[a,b] :=1 + B[b,c]

      • সেরা :=সর্বোত্তম এবং 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