Luyện tập Thiết kế thuật toán: chia để trị, tham lam, quy hoạch động lớp 12

Ví dụ 1. Kĩ thuật thiết kế thuật toán "chia để trị" gồm ba bước cơ bản nào? (có hình minh hoạ)

1. Chia bài toán thành các bài toán con cùng dạng, giải từng bài toán con, rồi kết hợp các kết quả lại
2. Sắp xếp dữ liệu, duyệt một lần, rồi in kết quả
3. Tại mỗi bước chọn phương án có lợi nhất trước mắt
4. Lưu kết quả các bài toán con vào bảng để dùng lại

Đáp án: A. Chia để trị gồm: chia (tách bài toán thành bài toán con nhỏ hơn cùng dạng), trị (giải các bài toán con, thường bằng đệ quy) và kết hợp (gộp kết quả con thành lời giải chung). Phương án 3 mô tả tham lam, phương án 4 mô tả quy hoạch động.

Ví dụ 2. Thuật toán tham lam (greedy) xây dựng lời giải theo cách nào? (có hình minh hoạ)

1. Thử tất cả các khả năng rồi chọn cách tốt nhất
2. Chia bài toán thành nhiều bài toán con rồi gộp lại
3. Lưu bảng kết quả của mọi bài toán con đã giải
4. Tại mỗi bước chọn ngay phương án có lợi nhất trước mắt và không xét lại lựa chọn đã chọn

Đáp án: D. Tham lam đưa ra một dãy lựa chọn, mỗi bước chọn phương án tốt nhất tại thời điểm đó (tối ưu cục bộ) với hi vọng đạt tối ưu toàn cục, và không quay lại sửa lựa chọn trước. Cách này nhanh nhưng không phải lúc nào cũng cho nghiệm tối ưu.

Ví dụ 3. So với đệ quy ngây thơ, điểm khác biệt cốt lõi của quy hoạch động là gì?

1. Không bao giờ sử dụng đệ quy
2. Luôn cho kết quả gần đúng thay vì chính xác
3. Lưu lại (ghi nhớ) kết quả của các bài toán con đã giải để không phải tính lại
4. Chỉ áp dụng được cho bài toán sắp xếp

Đáp án: C. Quy hoạch động giải các bài toán con gối nhau (xuất hiện lặp lại) đúng một lần và lưu kết quả vào bảng. Nhờ vậy tránh được việc tính đi tính lại như đệ quy ngây thơ, giúp giảm mạnh độ phức tạp.