Dãy Fibonacci trong Python
0, 1, 1, 2, 3, 5, 8... Tạo dãy số bằng một vòng lặp và hai biến, rồi chạy thử ngay trên trình duyệt.
- Mỗi số Fibonacci được tạo ra thế nào
- Cập nhật hai biến cùng lúc với a, b = b, a + b
- Lấy n số hạng đầu tiên
Mỗi số bằng tổng hai số đứng trước
Vấn đề
Nhiều thứ lớn lên dựa trên những gì có trước: đàn thỏ trong một bài toán cổ, các vòng xoắn trên hoa hướng dương, số cách leo cầu thang mỗi lần một hoặc hai bậc. Dãy Fibonacci là mô hình đơn giản nhất của kiểu tăng trưởng đó, và tính dãy này dạy bạn cách mang giá trị từ vòng lặp này sang vòng lặp sau.
Hình dung đời thường
Hãy hình dung một mẩu giấy ghi hai con số: số hiện tại và số kế tiếp. Mỗi lượt, bạn đọc to số hiện tại. Sau đó số kế tiếp trở thành số hiện tại, còn số kế tiếp mới là tổng của hai số cũ. Bạn không bao giờ phải nhớ nhiều hơn hai số cuối cùng.
a, b = 0, 1📝 Ghi hai số đầu tiêna, b = b, a + b🔄 Số kế tiếp thành số hiện tại, số kế tiếp mới là tổng hai sốfor _ in range(count):🔁 Lặp lại đủ số lượng bạn cầnprint(a, end=" ")📣 Đọc to số hiện tạiDãy Fibonacci bắt đầu bằng 0 và 1, và mỗi số hạng tiếp theo bằng tổng của hai số hạng đứng ngay trước nó.
Những điểm quan trọng
a, b = 0, 1lưu hai số hạng đầu tiên của dãy.print(a, end=" ")in số hạng hiện tại và giữ nguyên trên cùng một dòng.a, b = b, a + btính cả hai giá trị mới từ hai giá trị cũ trước khi gán cho biến nào.for _ in range(count):lặp mười lần;_là tên quen dùng cho biến lặp không dùng tới.
Khi nào nên sử dụng?
- Luyện vòng lặp mang trạng thái từ vòng này sang vòng sau.
- Hiểu các dãy mà mỗi giá trị phụ thuộc vào giá trị trước đó, bước đầu tiên tới quy hoạch động (dynamic programming).
- Bài tập kinh điển trong phỏng vấn và đề thi.
Khi nào chưa cần
- Tính một số hạng rất lớn như số thứ 10.000: có công thức nhanh hơn nhiều so với lặp qua từng số hạng.
- Đệ quy không lưu kết quả:
fib(n - 1) + fib(n - 2)tính đi tính lại cùng một giá trị và trở nên rất chậm.
Code ví dụ
count = 10
a, b = 0, 1
for _ in range(count):
print(a, end=" ")
a, b = b, a + b
Kết quả khi chạy
0 1 1 2 3 5 8 13 21 34
Giải thích code
Hai biến a và b lưu hai số liền kề của dãy. Sau khi in a, câu lệnh a, b = b, a + b cập nhật cả hai biến cùng lúc, nên giá trị cũ của a vẫn được dùng để tính số tiếp theo. Cách làm này chạy trong thời gian O(n) và chỉ cần thêm một lượng bộ nhớ cố định.
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thay đổi dữ liệu đầu vào và đoán trước kết quả rồi mới chạy để kiểm tra.
- Thêm phần kiểm tra cho trường hợp dữ liệu rỗng hoặc không hợp lệ.
- Đưa phần xử lý vào một hàm riêng và thử với nhiều bộ dữ liệu khác nhau.
Lỗi hay gặp
Cập nhật từng biến một
Sau a = b, giá trị cũ của a bị mất, nên b nhận giá trị sai.
a = b
b = a + b
a, b = b, a + b
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
- Số Fibonacci Trả về số Fibonacci thứ n. Dễ
- Tổng các số Fibonacci chẵn Cộng các số Fibonacci chẵn không vượt quá một giới hạn. Dễ