Chương trình tìm độ dài của dãy con fibonacci dài nhất trong Python

Giả sử chúng ta có một chuỗi như X_1, X_2, ..., X_n giống fibonacci nếu -

• n> =3

• X_i + X_i + 1 =X_i + 2 cho mọi i + 2 <=n

Bây giờ, giả sử một dãy A tăng dần lên tạo thành một dãy, chúng ta phải tìm độ dài của dãy con giống fibonacci dài nhất của A. Nếu không có dãy nào như vậy, thì trả về 0.

Vì vậy, nếu đầu vào là A =[1,2,3,4,5,6,7,8], thì đầu ra sẽ là 5 vì có một chuỗi [1,2,3,5,8] là chiều dài 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sA:=một tập hợp mới từ các phần tử của A

• last:=phần tử cuối cùng của A

• B:=một bản đồ chứa từng phần tử có trong A và tần số của chúng

• tốt nhất:=0

• đối với tôi ở kích thước từ A xuống 0, hãy làm

  • a:=A [i]

  • đối với mỗi b trong mảng con của A [từ chỉ mục i + 1 đến cuối], thực hiện

    • c:=a + b

    • nếu c có trong sA thì

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

      • tốt nhất:=tối đa trong tổng số tốt nhất và B [a, b] +2

    • ngược lại khi c> cuối cùng thì

      • đi ra từ vòng lặp

• trở lại tốt nhất

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

5