Chương trình kiểm tra số có phải số Fibonacci trong Python

Cho số n. Kiểm tra xem n có trong dãy Fibonacci hay không. Dãy Fibonacci: F(0)=0, F(1)=1, F(i)=F(i-1)+F(i-2).

Ví dụ: n = 13 → True (dãy: 0,1,1,2,3,5,8,13,21,34...).

Thuật toán giải quyết (Công thức toán học O(1))

Một số n là số Fibonacci nếu và chỉ nếu 5n²+4 hoặc 5n²-4 là số chính phương. Cách khác dùng hằng số vàng φ = (1+√5)/2:

• phi = 0.5 + 0.5 * √5
• a = phi * n
• n là Fibonacci nếu n == 0 hoặc a gần như nguyên (sai số < 1/n)

Ví dụ minh họa

from math import sqrt

def solve(n):
    phi = 0.5 + 0.5 * 5.0**0.5
    a = phi * n
    return n == 0 or abs(round(a) - a) < 1.0 / n

n = 13
print(solve(n))

Đầu vào

13

Đầu ra

True