99 Học Python – Tính Số Fibonacci Hai cách tính và so sánh hiệu suất

Bài 99 Học Python – Tính Số Fibonacci Hai cách tính và so sánh hiệu suất mới nhất

Dãy Fibonacci là một dãy số bắt đầu từ 0 và 1, trong đó mỗi số tiếp theo là tổng của hai số trước đó. Cụ thể, công thức tổng quát như sau:

Khuyến mãi đặc biệt thêm danh sách 10 bài tập nâng cao khả năng lập trình Python:

1. Bài: 91 Học Python – Sử dụng hàm tìm số nhỏ nhất trong 2 số để tìm số nhỏ nhất trong 3 số mới nhất
2. Bài 92: Viết hàm cộng, trừ, nhân, chia hai phân số
3. Bài 93 Viết chương trình con tính tổng các phần tử trong một mảng
4. Bài 94: Viết chương trình con tính tổng các phần tử chẵn trong một mảng
5. Bài 95: Đếm số lượng số nguyên tố trong mảng bằng Python
6. Bài 96 : Tính trung bình cộng các số nguyên tố trong mảng bằng Python
7. Bài 97 Tính trung bình cộng các số chính phương trong mảng bằng Python
8. Bài 98: Viết 2 chương trình con tìm Max, Min và vị trí của Max, Min

9. Bài 99 Học Python – Tính Số Fibonacci Hai cách tính và so sánh hiệu suất mới nhất

10. Bài 100: Số Hoàn Hảo Hai Cách Kiểm Tra và So Sánh Hiệu Suất

1. Cách 1: Tính Fibonacci bằng đệ quy

Đây là cách tiếp cận đơn giản và dễ hiểu nhưng không tối ưu về mặt hiệu suất.

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

# Ví dụ sử dụng
print(fibonacci_de_quy(10))  # Kết quả: 55

Ưu điểm:

• Dễ hiểu, phù hợp cho người mới bắt đầu học thuật toán.

Nhược điểm:

• Hiệu suất kém do có nhiều lần tính toán lặp lại (độ phức tạp O(2^n)).
• Khi n lớn, chương trình chạy rất chậm.

2. Cách 2: Tính Fibonacci bằng phương pháp lặp (Dynamic Programming)

Sử dụng cách tiếp cận lập trình động giúp giảm số lần tính toán bằng cách lưu trữ kết quả trung gian.

def fibonacci_lap(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Ví dụ sử dụng
print(fibonacci_lap(10))  # Kết quả: 55

Ưu điểm:

• Hiệu suất cao hơn nhiều so với phương pháp đệ quy (độ phức tạp O(n)).
• Ít tốn tài nguyên hơn, tránh tình trạng lặp lại tính toán không cần thiết.

Nhược điểm:

• Cần sử dụng biến bổ sung để lưu trữ kết quả trung gian.
• Không trực quan bằng phương pháp đệ quy.

3. So sánh hai phương pháp

Phương pháp	Độ phức tạp	Tốc độ thực thi	Bộ nhớ sử dụng
Đệ quy	O(2^n)	Chậm	Cao
Lặp (Dynamic)	O(n)	Nhanh	Thấp

Tóm lại, nếu cần tính Fibonacci cho giá trị nhỏ thì đệ quy có thể là một cách tiếp cận đơn giản. Tuy nhiên, khi làm việc với số lớn, sử dụng phương pháp lặp sẽ giúp tối ưu hiệu suất và tiết kiệm tài nguyên.

Bạn thích phương pháp nào hơn? Hãy thử chạy hai đoạn mã trên và tự kiểm chứng nhé!

 

Nếu bạn thấy hay ! xin bạn 1 phút ! vui lòng đánh giá 5 sao cho trang website của chúng tôi ! để có động lực làm thêm nhiều bài hay nữa ! cảm ơn quý khách nhé !

 

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