Chương trình Python số Fibonacci

Trong bài viết này, chúng ta sẽ học về giải pháp và phương pháp giải quyết bài toán cho trước.

Đề bài – Nhiệm vụ của chúng ta là tính số Fibonacci thứ n.

Dãy Fn của các số Fibonacci được cho bởi quan hệ đệ quy dưới đây:

Fn = Fn-1 + Fn-2

với giá trị hạt giống (seed values) chuẩn:

F0 = 0 và F1 = 1.

Chúng ta có hai giải pháp có thể cho bài toán:

• Cách tiếp cận đệ quy (Recursive)
• Cách tiếp cận động (Dynamic)

Cách 1 – Cách tiếp cận đệ quy

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

Tất cả biến được khai báo trong phạm vi toàn cục như hình dưới đây:

Cách 2 – Cách tiếp cận động

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

Tất cả biến được khai báo trong phạm vi toàn cục như hình dưới đây:

Kết luận

Trong bài viết này, chúng ta đã học về cách tính số Fibonacci.