- Đang điền
- Được đọc
- Đáp án
Fibonacci với quy hoạch động
Dãy Fibonacci là ví dụ mở đầu kinh điển của quy hoạch động. Đệ quy thuần tính đi tính lại cùng những số hạng, nhưng với một bảng ghi nhớ từng số hạng, khối lượng công việc chỉ tăng theo n. Hãy chọn một số hạng, chọn từ dưới lên hoặc từ trên xuống, rồi đi từng bước để thấy mỗi ô chỉ được điền một lần. Nhấn Phát để xem bảng được điền dần, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Chọn n, số hạng cần tính, và phương pháp: từ dưới lên điền bảng bắt đầu từ bên trái, còn từ trên xuống giữ nguyên đệ quy nhưng tra bảng trước, khi đó hàng dưới bảng là ngăn xếp các lời gọi chưa kết thúc. Ví dụ mới chọn một n khác. Khi bảng đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Nhập n, số hạng cần tính, vào ô Số hạng n, rồi chọn Từ dưới lên hoặc Từ trên xuống.
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu.
- Quan sát mỗi ô đọc hai ô đứng trước nó. Với từ trên xuống, hàng dưới bảng là ngăn xếp các lời gọi chưa kết thúc.
Từ dưới lên và từ trên xuống
Từ dưới lên, còn gọi là lập bảng (tabulation), bắt đầu với F(0) = 0 và F(1) = 1 rồi điền bảng từ trái sang phải: mỗi ô mới bằng tổng hai ô đứng trước nó. Từ trên xuống, còn gọi là ghi nhớ (memoization), giữ nguyên định nghĩa đệ quy: muốn tìm F(n) thì gọi F(n − 1) và F(n − 2). Khác với đệ quy thuần, mỗi lời gọi đều tra bảng trước và chỉ tính một số hạng khi ô của nó vẫn còn trống. Cả hai cách đều điền mỗi ô một lần và dùng n − 1 phép cộng.
Vì sao đệ quy thuần lại chậm đến vậy
Khi không có bảng, F(n) gọi F(n − 1) và F(n − 2), cả hai lời gọi này đều gọi F(n − 3), và cứ thế tiếp tục: các lời gọi tạo thành một cây, trong đó cùng những số hạng xuất hiện lặp đi lặp lại. Số lời gọi là 2·F(n + 1) − 1, tăng nhanh như chính các số Fibonacci: 177 lời gọi cho F(10), 21.891 cho F(20) và hơn 331 triệu cho F(40). Những bài toán con gối nhau như thế chính là thứ quy hoạch động sinh ra để giải quyết.
Câu hỏi thường gặp
Quy hoạch động là gì?
Là cách giải một bài toán bằng cách chia nó thành các bài toán nhỏ hơn gối lên nhau, giải mỗi bài toán nhỏ một lần và lưu đáp án vào bảng. Dãy Fibonacci là ví dụ đơn giản nhất: mỗi số hạng được tạo từ hai số hạng đứng trước nó.
Ghi nhớ và lập bảng khác nhau thế nào?
Ghi nhớ giữ nguyên mã đệ quy và lưu mỗi đáp án vào lần đầu tính được, để các lời gọi sau chỉ cần đọc lại. Lập bảng điền bảng theo một thứ tự bảo đảm mọi đáp án mà một ô cần đều đã có sẵn. Cả hai làm cùng những phép cộng; lập bảng không cần ngăn xếp lời gọi, còn ghi nhớ chỉ tính những ô thực sự cần đến.
F(n) cần bao nhiêu phép cộng?
n − 1 nếu có bảng: mỗi số hạng từ F(2) đến F(n) một phép cộng. Chỉ hai số hạng cuối cùng được đọc, nên chương trình cũng có thể chỉ giữ hai số thay vì cả bảng.
Vì sao ứng dụng chỉ dừng ở n = 40?
F(40) = 102.334.155 vẫn hiển thị vừa vặn trên màn hình, trong khi đệ quy thuần đã cần đến 331.160.281 lời gọi để tính nó. Các số hạng lớn hơn tăng rất nhanh: F(78) là số hạng lớn nhất mà một số JavaScript lưu được chính xác.
Có dữ liệu nào được gửi đi đâu không?
Không. Mọi thứ đều được tính trong trình duyệt của bạn, và các thiết lập gần nhất được giữ trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa