Website: Email : Tel : 0918.775.368
MỤC LỤC
MỤC LỤC................................................................................................................................1
THUẬT TOÁN CHIA ĐỂ TRỊ...............................................................................................2
(Divide to Conquer)..................................................................................................................2
1) Khái niệm:........................................................................................................................2
2) Sơ đồ chung:....................................................................................................................2
3) Thuật toán β:....................................................................................................................2
4) Sơ đồ thuật toán chia để trị:.............................................................................................3
5) Một số ví dụ.....................................................................................................................4
5.1) Bài toán tháp Hà Nội................................................................................................4
5.6) Giải và cài đặt bài toán Mảng con lớn nhất.............................................................7
5.6.1) Thuật toán chia để trị tìm mảng con lớn nhất gồm các thao tác:......................7
5.6.2) Thuật toán chia để trị tìm mảng con lớn nhất .................................................7
5.6.3) Thuật toán MaxVector(a, i, j):...........................................................................8
5.6.4) Cài đặt chương trình.......................................................................................8
5.6.5) Phân tích hiệu quả của thuật toán:...................................................................12
THUẬT TOÁN CHIA ĐỂ TRỊ
(Divide to Conquer)
Có lẽ thuật toán được sử dụng nhiều nhất, quan trọng nhất là kỹ thuật ″Chia để
Trị″. Kỹ thuật này sẽ chia bài toán hiện thời thành N bài toán nhỏ hơn, thực hiện lời
giải cho từng bài toán nhỏ này và từ đó xây dựng thuật toán cho bài toán lớn tổng
hợp. Ví dụ cho các thuật toán này là Sắp xếp Trộn
(1)
hoặc Tìm kiếm Nhị phân
(2)
.
1) Khái niệm:
Chia để trị là một trong những phương pháp thiết kế giải thuật cơ bản bao gồm
các thao tác:
Chia: Chia bài toán cần giải thành một loạt các bài toán con độc

.
.
Ta có:
T α(n) = cn2 (theo giả thuyết)
T β(n) = 3.T α(n/2) + dn = ¾.cn2 + dn
.
.
Nếu:
dn < c.n2/4 hay n > 4. d/c thì thuật toán β nhanh hơn thuật toán α.
Do 4.d/c là hằng số nên với n đủ lớn ta luôn có n > 4. d/c.
Điều đó cho thấy việc sử dụng thuật toán β để giải bài toán đặt ra bằng cách chia
nó thành các bài toán con có kích thước càng ngày càng nhỏ đến khi thu được
bài toán con kích thước n0 < 4.d/c sẽ thu được hiệu quả cao.
4) Sơ đồ thuật toán chia để trị:
procedure Divide_and_Conquer(n);
begin
if n ≤ n0 then
Giải bài toán một cách trực tiếp;
else
begin
Chia bài toán thành r bài toán con có kích thước n/k;
for (mỗi bài toán trong r bài toán con) do
Divide_and_Conquer(n/k);
Tổng hợp lời giải của r bài toán con để thu được lời giải của bài toán;
end;
end;
3
5) Một số ví dụ
5.1) Bài toán tháp Hà Nội
Để minh họa rõ hơn cho kỹ thuật này chúng ta hãy xét một ví dụ quen thuộc đó

(3)
. Bây giờ
chúng ta sẽ xét lại bài toán này với kỹ thuật Chia để Trị. Ta phân tách mỗi số X, Y
thành 2 phần, mỗi phần n/2 bit. Để cho đơn giản ta sẽ luôn xét n là lũy thừa của 2.
X, Y sẽ được phân tích thành 2 phần n/2-bit như sau:
X = A | B (X = A2
n/2
+ B)

Y = C | D
(Y = C2
n/2
+ D)
Khi đó tích XY sẽ có dạng:
XY = AC2
n
+ (AD+BC)2
n/2
+ BD (1)
Dựa trên công thức (1) ta có thể suy luận đơn giản như sau cho việc tính tích
XY: chúng ta sẽ tính 4 phép nhân với các số n/2-bit là AC, AD, BC và BD, sau đó
thực hiện 3 phép cộng với các số 2n-bit, cuối cùng là 2 phép chuyển chữ số (2 phép
nhân với lũy thừa của 2) Các phép cộng và phép chuyển chữ số đều được thực hiện
với thời gian O(n), do đó ta thu được công thức tính độ phức tạp của phép toán trên
T(n) là:
T(1) = 1
T(n) = 4T(n/2) + C.n (C-const)
(2) Công thức (2) cho ta T(n) = O(n
2
) và như vậy ta chưa thu được kết quả gì