Khóa học Python từ Cơ bản đến Nâng cao

Bài 10.1 - Python và bài toán Fibonacci

Fibonacci là một trong những bài toán cổ điển và phổ biến nhất trong lập trình. Dãy số này bắt đầu từ 0 và 1, mỗi số sau là tổng của hai số trước đó:

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

Trong bài này, ta sẽ học cách giải bài toán này bằng nhiều phương pháp khác nhau trong Python.

1. Cách 1: Dùng đệ quy đơn giản

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

print(fibonacci_recursive(6))  # Output: 8

Cách này đơn giản nhưng rất chậm với n lớn do tính lặp lại cao (O(2^n)).

2. Cách 2: Dùng vòng lặp (hiệu quả hơn)

def fibonacci_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fibonacci_loop(6))  # Output: 8

Cách này chạy rất nhanh, độ phức tạp O(n), và không dùng đệ quy.

3. Cách 3: Dùng memoization (ghi nhớ)

memo = {}

def fibonacci_memo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2)
    return memo[n]

print(fibonacci_memo(30))  # Output: 832040

Giải pháp đệ quy + ghi nhớ giúp tiết kiệm thời gian rất nhiều cho n lớn.

4. Cách 4: Dùng công thức Binet (áp dụng khi cần ước lượng nhanh)

import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi ** n) / math.sqrt(5))

print(fibonacci_binet(6))  # Output: 8

Dùng công thức này khi bạn không cần tính tất cả số trước đó.

5. In toàn bộ dãy Fibonacci từ 0 đến n

def fibonacci_series(n):
    a, b = 0, 1
    result = []
    for _ in range(n):
        result.append(a)
        a, b = b, a + b
    return result

print(fibonacci_series(10))  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

6. So sánh nhanh các cách

Tổng kết

• Có nhiều cách để giải bài toán Fibonacci, tuỳ vào mục đích sử dụng bạn có thể chọn:
  • Đệ quy để học thuật toán
  • Vòng lặp cho hiệu suất cao
  • Memoization khi cần tối ưu đệ quy
  • Công thức Binet để tính trực tiếp