Bài liên quan:
- Cách trình bày mô tả một thuật toán chia để trị
- Trình bày cách tính độ phức tạp của một đoạn chương trình
- Các bài tập chuyên đề chia để trị cơ bản
Để hiểu thuật toán chia để trị một cách cụ thể và rõ ràng, các bạn cần phải tốn khá nhiều thời gian đọc sách, cũng như lập trình. Ở bài viết này, mình không đi sâu vào những vấn đề đó, các bạn có thể vào kho tài liệu học tập, chọn môn giải thuật và tải sách của Thầy Lê Minh Hoàng về đọc phần lý thuyết này. Theo mình đó là một quyển sách đầy đủ và hay.
Mình chỉ nói ngắn gọn, một thuật toán chia để trị thường gồm 3 phần: phần bài toán cơ sở, phần bài toán con, phần chia-trị và tổng hợp kết quả. Tùy theo bài mà phần tổng hợp kết quả có khi có, khi không. Nhưng để tiện cho việc trình bày thì mình cứ để nó là "Chia-trị và tổng hợp kết quả".
Tóm lại, khi mô tả thuật toán chia để trị cũng cần mô tả được 3 phần như đã nói ở trên.
Ví dụ: đề xuất thuật toán chia để trị để tìm số nhỏ nhất trong dãy có n số nguyên.
Ta có thể nói như sau:
Với n là số lượng phần tử của dãy số nguyên
- Bài toán con: tìm số nhỏ nhất trong dãy có n-1 số nguyên
- Bài toán cơ sở: tìm số nhỏ nhất trong dãy có 1 số nguyên. (không cần viết thêm nữa, vì có lẽ ai cũng đã hiểu, dãy có 1 số nguyên thì số nhỏ nhất cũng là chính nó, nên ta chỉ cần viết ngắn gọn "tìm số nhỏ nhất trong dãy có 1 số nguyên" là đủ)
- Chia-trị và tổng hợp kết quả: min (giá trị phần tử n, tìm số nhỏ nhất trong dãy có (n-1) số nguyên đã loại bỏ phần tử thứ n)
Ví dụ: đề xuất thuật toán chia để trị để đảo ngược một mảng có n phần tử
Gọi i và j là đại diện cho chỉ số đầu và chỉ số cuối của các phần tử trong mảng có n phần tử. Với j-i+1 = n là số lượng phần tử hiện có trong mảng
- Bài toán con: đảo ngược mảng có n-2 phần tử
- Bài toán cơ sở: đảo ngược mảng có 2 phần tử (đổi chỗ 2 phần tử đó)
- Chia-trị và tổng hợp kết quả: đổi chỗ 2 phần tử đầu-cuối mảng, sau đó thực hiện đảo ngược mảng có n-2 phần tử