Tư tưởng chiến lược của giải pháp chia để trị trong giải
quyết các bài toán tin như sau: Ta phân bài toán cần giải thành các bài toán
con. Các bài toán con lại được tiếp tục phân thành các bài toán con nhỏ hơn, cứ
thế tiếp tục cho tới khi ta nhận được các bài toán con hoặc đã có thuật giải hoặc
là có thể dễ dàng đưa ra thuật giải. Sau đó ta tìm cách kết hợp các nghiệm của
các bài toán con để nhận được nghiệm của bài toán con lớn hơn, để cuối cùng
nhận được nghiệm của bài toán cần giải. Thông thường các bài toán con nhận được
trong quá trình phân chia là cùng dạng với bài toán ban đầu, chỉ có cỡ của
chúng là nhỏ hơn.
Thuật toán chia để trị có thể biểu diễn bằng mô hình đệ
quy như sau:
Trong đó: Solve(A) là thuật giải bài toán A trong trường
hợp A có cỡ đủ nhỏ.
Cụ thể áp dụng giải pháp (kỹ thuật) chia để trị để giải quyết bài toán:
Bài toán 1: Cho số a và một số nguyên dương n, tính
an
Cách 1: Sử dụng thuật
toán lặp, mất n phép nhân để tính an
Cách 2: áp dụng kỹ thuật chia để trị, ta tính an dựa vào ak (trong đó k = n div 2) như sau:
-
Nếu n chẵn: an = ak
x ak
-
Nếu n lẻ: an = ak
x ak x a
Để tính
ak ta lại dựa vào a k div 2, quá trình chia nhỏ cho đến
khi nhận được bài toán a1 thì dừng.
Ví dụ:
tính 1213
-
Bài toán 1213 được tính dựa trên bài toán con 126,
ta có1213= 127 x 126
-
Bài toán 126 được tính dựa trên bài toán con 123,
ta có126= 123 x 123
-
Bài toán 123 được tính dựa trên bài toán con 122,
ta có123= 122 x 121
-
Bài toán 122 được tính dựa trên bài toán con 121,
ta có122= 121 x 121
Thủ tục
đệ quy luythua(a, n, p) thể hiện ý tưởng trên.
hoặc có thể viết dưới dạng hàm sau:
Để đánh
giá thời gian thực hiện thuật toán, ta tính số phép nhân phải sử dụng, gọi T(n) là số phép nhân thực hiện, ta có:
Bài toán 2: Sắp xếp mảng bằng thuật toán trộn
(Merge Sort).
Nội dung
bài toán: Cho mảng số nguyên A[1..n], cần sắp xếp các phần tử của mảng theo thứ
tự tăng dần.
Giải:
Ta chia mảng A[1..n] thành hai mảng con A[1..k] và A[(k+1)..n] trong đó k= n div 2. Giả sử,
hai mảng con A[1..k] và A[(k+1)..n] đã
được sắp xếp tăng dần, ta sẽ trộn hai mảng con để được mảng A[1..n] cũng sắp
xếp tăng dần. Để sắp xếp hai mảng con A[1..k]
và A[(k+1)..n] ta lại tiếp tục chia đôi chúng. Thủ tục đệ quy
MergeSort(i,j) sắp xếp tăng dần mảng con A[i..j] với 1 ≤ i ≤ j ≤ n. Để sắp xếp
cả mảng A[1..n], ta chỉ cần gọi thủ tục này với i=1 và j=n.
Bài toán
3: Tháp Hà Nội.
- Một lần chỉ
được chuyển 1 đĩa
- Trong quá
trình chuyển đĩa, có thể sử dụng cọc 2 làm cọc trung gian và một đĩa chỉ được
đặt lên một đĩa lớn hơn.
Giải
Chia để trị được
thể hiện ở chổ: bài toán chuyển n đĩa được chia thành 2 bài toán nhỏ hơn là
chuyển n-1 đĩa và chuyển 1 đĩa.
Để chuyển n đĩa
từ cọc 1 sang cọc 3 ta thực hiện như sau:
- chuyển (n-1)
đĩa từ cọc 1 sang cọc 2, sử dụng cọc 3 làm cọc trung gian
- chuyển 1 đĩa
từ cọc 1 sang cọc 3
- chuyển (n-1)
đĩa từ cọc 2 sang cọc 3, sử dụng cọc 1 làm cọc trung gian
@ Một số
bài toán khác có thể sử dụng phương pháp chia để trị để giải quyết
J Bài toán: Xếp lịch thi đấu thể
thao
- Xếp
lịch thi đấu vòng tròn 1 lượt cho n đấu thủ (đội)
- Mỗi
đấu thủ đấu tối đa 1 trận/ngày
- Số
ngày thi đấu ngắn nhất.
* Ý
tưởng chia để trị để giải quyết bài toán trên:
- Chia
·
Xếp cho n/2, n/4, n/8 ...
·
Cuối cùng xếp cho 2 đấu thủ
- Tổng
hợp kết quả
J Bài toán: Nhân hai số nguyên lớn
Phương pháp
truyền thống
1234
X
1112
-----------
2468
1234
1234
1234
------------
Kết quả
* Ý
tưởng chia để trị để giải quyết bài toán trên:
- Chia để trị
·
X=A*10n/2
+ B
·
Y=C*10n/2
+ D
·
XY= AC10n
+(AD+BC)10n/2 +BD
- Thực hiện 4 phép nhân AC, AD, BC và BD
- Tính XY từ kết quả 4 phép nhân.
* Chú
ý: Để giải quyết các bài toán tin bằng phương pháp chia để
trị một cách hiệu quả thì các bài toán con phải cân bằng
- Chia
bài toán đã cho thành a bài toán con có kích thước là n/b
- Khi đó 
Không có nhận xét nào:
Đăng nhận xét