โปรแกรมค้นหาความยาวของลำดับย่อย Fibonacci ที่ยาวที่สุดจากรายการที่กำหนดใน Python

สมมติว่าเรามีรายการจำนวนบวกที่เพิ่มขึ้นอย่างเคร่งครัดที่เรียกว่า nums เราต้องหาความยาวของลำดับย่อยที่ยาวที่สุด A (ความยาวขั้นต่ำ 3) เช่นนั้น A[i] =A[i - 1] + A[i - 2] สำหรับ i> 1 ทั้งหมด

ดังนั้น ถ้าอินพุตเป็น nums =[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] ผลลัพธ์จะเป็น 6 ตามที่เราเลือกได้ [1, 2, 3, 5, 8, 13].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• A :=nums
• n :=ขนาดของ A
• maxLen :=0
• S :=ชุดใหม่จาก A
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • สำหรับ j ในช่วง i + 1 ถึง n ทำ
    • x :=A[j]
    • y :=A[i] + A[j]
    • ความยาว :=2
    • ในขณะที่ y มีอยู่ใน S ให้ทำ
      • z :=x + y
      • x :=y
      • y :=z
      • ยาว :=ยาว + 1
      • maxLen :=สูงสุดของ maxLen ความยาว
• ถ้า maxLen> 2 แล้ว
  • คืน maxLen
• มิฉะนั้น
  • คืน 0

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, nums):
      A = nums
      n = len(A)
      maxLen = 0
      S = set(A)
      for i in range(0, n):
         for j in range(i + 1, n):
            x = A[j]
            y = A[i] + A[j]
            length = 2
            while y in S:
               z = x + y
               x = y
               y = z
               length += 1
               maxLen = max(maxLen, length)
      if maxLen > 2:
         return maxLen
      else:
         return 0
ob = Solution()
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
print(ob.solve(nums))

อินพุต

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

ผลลัพธ์

6