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

Trong bài viết này, chúng ta sẽ tìm hiểu về giải pháp cho bài toán dưới đây:

Đề bài

Cho một số n, kiểm tra xem n có phải là số Fibonacci hay không.

Chúng ta đều biết số Fibonacci thứ n là tổng của hai số Fibonacci trước đó. Nhưng chúng cũng cung cấp một mối quan hệ thú vị ngoài quan hệ đệ quy.

Một số mang tính chất Fibonacci nếu và chỉ nếu (5*n² + 4) hoặc (5*n² - 4) là một số chính phương.

Chúng ta sẽ sử dụng tính chất này để kiểm tra xem một số có phải Fibonacci hay không.

Bây giờ hãy xem triển khai script Python:

Ví dụ

import math

# Kiểm tra x có phải số chính phương
def isPerfectSquare(x):
    s = int(math.sqrt(x))
    return s * s == x

# Kiểm tra n có phải số Fibonacci
def isFibonacci(n):
    # Nếu một trong 5*n*n + 4 hoặc 5*n*n - 4 hoặc cả hai là số chính phương
    return isPerfectSquare(5 * n * n + 4) or isPerfectSquare(5 * n * n - 4)

for i in range(1, 11):
    if (isFibonacci(i) == True):
        print(i, "là số Fibonacci")
    else:
        print(i, "không phải số Fibonacci")

Kết quả

1 là số Fibonacci
2 là số Fibonacci
3 là số Fibonacci
4 không phải số Fibonacci
5 là số Fibonacci
6 không phải số Fibonacci
7 không phải số Fibonacci
8 là số Fibonacci
9 không phải số Fibonacci
10 không phải số Fibonacci

Tất cả hàm và biến được khai báo trong khung toàn cục như hình bên dưới:

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu giải pháp xác định số cho trước có phải Fibonacci hay không.