Chương trình Python tìm số Fibonacci thứ n

Trong bài viết này, chúng ta sẽ tính toán số Fibonacci thứ n.

Số Fibonacci được định nghĩa bởi quan hệ đệ quy dưới đây:

Fn = Fn-1 + Fn-2

Với F₀ = 0 và F₁ = 1.

Một vài số Fibonacci đầu tiên là:

0, 1, 1, 2, 3, 5, 8, 13, ................

Chúng ta có thể tính các số Fibonacci bằng phương pháp đệ quy và quy hoạch động.

Bây giờ hãy xem triển khai dưới dạng script Python:

Cách 1: Phương pháp đệ quy

Ví dụ

# Cách đệ quy
def Fibonacci(n):
    if n < 0:
        print("Không thể tính Fibonacci")
    # Số Fibonacci đầu tiên
    elif n == 1:
        return 0
    # Số Fibonacci thứ hai
    elif n == 2:
        return 1
    else:
        return Fibonacci(n - 1) + Fibonacci(n - 2)

# main
n = 10
print(Fibonacci(n))

Kết quả

34

Phạm vi của tất cả biến được khai báo hiển thị dưới đây.

Cách 2: Phương pháp Quy hoạch động

Ví dụ

# Cách quy hoạch động
Fib_Array = [0, 1]

def fibonacci(n):
    if n < 0:
        print("Không thể tính Fibonacci")
    elif n <= len(Fib_Array):
        return Fib_Array[n - 1]
    else:
        temp = fibonacci(n - 1) + fibonacci(n - 2)
        Fib_Array.append(temp)
        return temp

# Chương trình driver
n = 10
print(fibonacci(n))

Kết quả

34

Phạm vi của tất cả biến được khai báo hiển thị dưới đây.

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về tính toán số Fibonacci thứ n sử dụng cách tiếp cận đệ quy và quy hoạch động.