Số Fibonacci thứ n trong Python

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

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

Fn = Fn-1 + Fn-2

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

Các số Fibonacci đầu tiên: 0, 1, 1, 2, 3, 5, 8, 13, ...

Chúng ta có thể tính 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 (Recursion)

Ví dụ

# recursive approach
def Fibonacci(n):
    if n < 0:
        print("Fibonacci can't be computed")
    # 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 khai báo được hiển thị dưới đây:

Cách 2: Phương pháp quy hoạch động (Dynamic Programming)

Ví dụ

# dynamic approach
Fib_Array = [0, 1]
def fibonacci(n):
    if n < 0:
        print("Fibonacci can't be computed")
    elif n <= len(Fib_Array):
        return Fib_Array[n-1]
    else:
        temp = fibonacci(n-1) + fibonacci(n-2)
        Fib_Array.append(temp)
        return temp
# Driver Program
n = 10
print(fibonacci(n))

Kết quả

34

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

Kết luận

Trong bài viết này, chúng ta đã học về tính toán số Fibonacci thứ n sử dụng đệ quy và quy hoạch động.