Ba bước của chia để trị
**Chia để trị (Divide and Conquer)** là cách thiết kế thuật toán bằng các bài toán nhỏ hơn:
| Bước | Việc thực hiện |
|---|---|
| Chia (Divide) | Tách bài toán thành các phần nhỏ có thể xử lí riêng. |
| Trị (Conquer) | Giải bài toán nhỏ; nếu còn lớn thì tiếp tục chia. |
| Kết hợp (Combine) | Dùng kết quả các phần để có lời giải của bài toán ban đầu. |
Khi bài toán nhỏ cùng dạng với bài toán gốc, có thể dùng lời gọi đệ quy. Chia để trị mô tả cách tổ chức lời giải; đệ quy là một cách cài đặt. Một thuật toán vẫn có thể giữ ý tưởng chia để trị khi được viết bằng vòng lặp.
Chỉ giữ nhóm còn có thể chứa bi giả
Có năm viên đánh số 1–5; **đúng một viên giả nặng hơn**, bốn viên thật có cùng khối lượng. Cân nhóm {1,2} với nhóm {3,4}, để riêng viên 5.
Nếu cân bằng, bốn viên trên cân đều thật nên viên 5 là giả. Nếu nhóm {1,2} nặng hơn, chỉ cần xét hai viên ấy; cân 1 với 2 để chọn viên nặng. Nhóm {3,4} nặng hơn được xử lí tương tự. Theo cách này, có nhánh dừng sau một lần cân, nhánh dài nhất cần hai lần.
Một lần cân chỉ có ba kết quả: trái nặng, phải nặng hoặc cân bằng. Vì có năm khả năng về viên giả, một lần chưa đủ phân biệt mọi trường hợp. Cách trên cần nhiều nhất hai lần, nên hai là số lần cân tối thiểu để bảo đảm tìm được viên giả.
Điều kiện hai nhóm có cùng số viên và chỉ một viên giả nặng hơn là căn cứ để suy ra nhóm cần giữ.
Giữ đúng danh tính khi bài toán nhỏ trả kết quả
Theo cách chia nhóm trong sách, với chín viên, cân 4 viên với 4 viên và để riêng 1 viên. Nếu cân bằng thì chọn ngay viên để riêng. Nếu lệch, xét 4 viên ở bên nặng; tiếp tục cân 2 với 2 rồi 1 với 1. Nhánh dài nhất của **cách chia 4+4+1 này** cần ba lần cân.
Bước kết hợp là xác định viên tìm được trong nhóm nhỏ chính là viên mang nhãn nào của bộ ban đầu. Không cần cân lại toàn bộ sau khi đã xác định viên giả. Số lần cân đang nêu gắn với cách chia nhóm cụ thể ấy.
Bài luyện
Cân {1,2} với {3,4} trong bài và hai bên cân bằng. Viên nào là giả?
Viên giả nặng hơn chưa được đưa lên cân.
Nếu viên giả ở nhóm này thì nhóm này phải nặng hơn.
Nếu viên giả ở nhóm này thì nhóm này phải nặng hơn.
Đề cho đúng một viên giả.
Lời giải
Hai nhóm có cùng số viên và các viên thật cùng khối lượng. Viên giả nặng hơn sẽ làm cân lệch nếu nó ở một trong hai nhóm. Cân bằng nên viên giả là viên 5 chưa cân.
Bài luyện
Nhóm {1,2} nặng hơn nhóm {3,4}. Bước tiếp theo theo sơ đồ là gì?
Chỉ có đúng một viên giả.
Chỉ còn hai ứng viên; cân từng viên sẽ chọn được viên nặng.
Viên 5 chưa cân nhưng kết quả lệch đã xác định nhóm chứa bi giả.
Lặp lại cùng phép cân chưa phân biệt hai ứng viên.
Lời giải
Vì hai nhóm có cùng số viên và chỉ một viên giả nặng hơn, bi giả nằm trong nhóm {1,2}. Cân 1 với 2 cho biết viên nào nặng hơn và kết thúc bài toán nhỏ.
Bài luyện
Theo cách chia 4+4+1 rồi 2+2 rồi 1+1, nhánh dài nhất của bài toán chín viên cần bao nhiêu lần cân?
Nhánh chọn nhóm 4 còn có thể phải phân biệt hai viên cuối.
Không cần cân lần lượt cả chín viên theo cách đang xét.
Có ba phép cân liên tiếp trên nhánh lệch cần xét tiếp.
Một lần chỉ đủ cho nhánh cân bằng ngay đầu.
Lời giải
Lần đầu chọn nhóm 4 ở bên nặng. Lần thứ hai chọn nhóm 2 ở bên nặng. Lần thứ ba phân biệt hai viên cuối. Đây là số lần nhiều nhất theo cách chia nhóm đã cho.
Bài luyện
Trong ví dụ tìm bi giả, bước kết hợp cần giữ điều gì?
Bài toán cần tìm viên giả, không yêu cầu tổng khối lượng.
Nhóm nặng chỉ chứa một viên giả.
Khi đã xác định viên giả thì không cần phép cân ấy.
Kết quả bài toán nhỏ phải chỉ đúng viên của bài toán gốc.
Lời giải
Bài toán nhỏ trả một viên trong nhóm đã chọn. Giữ nhãn của viên qua quá trình chia giúp đưa kết quả đó về đúng viên của bộ ban đầu.
Đang học