Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 33 - CHƯƠN PG 2 : HƯƠNG PHÁP CHIA ĐỂ TRỊ
(Divide - and - conquer)
I. Mở đầu
1. Ý tưởng
Có lẽ q äng rãi nhất là kỹ thuật thiết kế “Chia để trò” .
Nó phân rã bài toán kích thước n thành các bài toán con nhỏ hơn mà việc tìm lời
giải cu là cùn ài toán đã cho được xây dựng từ lời
giải cu
hính của phương pháp này là : chia dữ liệu
thành từng miền đủ nhỏ, giải bài toán trên các miền đã chia rồi tổng hợp kết quả
lại.
2. Mô hình
uan trọng và áp dụng ro
ûa chúng g một cách. Lời giải của b
các bûa ài toán con này .
Ta có thể nói vắn tắt ý tưởng c

D& (ℜ) - là miền dữ liệu - là hàm thể hiện cách giải bài
toán th o phươ g pha chia
void D&C(
ℜ)
ℜ
i

kết quả 0.
oán tìm Giải bằng thuật t
2. Ý tưởng
Chia đôi mảng , mỗi lần so sánh phần tử giữa với x, nếu phần tử x nhỏ hơn
lấy nửa trái, ngược lại thì lấy nửa phải.
3. Mô tả thuật toán
thì

Input : a[1 n]
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 34 - Output :
⎨
⎧
∈ ax;1

⎩
∉ ax;0
Mô tả :
Tknp(a, x, Đầu, Cuối)
≡
If (Đầu > Cuối)

Ta có : T
tốt
(n) = O(1)
b
Thật vậy, Nếu gọi T(n
T 1 + T[n/2] ; n
Cài đặt
int tknp(int a[max],int x,int l, int r)
{

( l > )
eturn
}

int mid;
if r
r 0;
m l+id = ( r)/2;
if ( x == a[mid] )
return 1;
if ( x > a[mid] )
r tknp(a,x,mid+1,r); eturn
return tknp(a,x,l,mid-1);
Trần Tuấn Minh Khoa Toán-Tin

Tìm giá trò
MinMax(a,l,r,Min,M
MinMax(a,2,7,Min,Max)

Input : a[l r], ( l ≤ r )
Output Mi
Mô tả :
MinMa
r)
{
MinMax(a,l, (l+r) / 2, Min1, Max1);
MinMax(a,(l+r) /2 + 1, r , Min2, Max2);
in2)
Max = Max1
Else
;

: n = Min (a[l], ,a[r]),
Max = Max (a[l], ,a[r]).

x(a,l, r, Min, Max)
≡
if (l ==
{
Min = a[l];
Max = a[l];
}
Else

If (Min1 < M

⎨
== 2;1)( nnT
Với n = 2
k
, thì :
∑
−
+==++=+=
1
1222
2)2(2)2/(222)2/(22)(
i
ik
TnTnTnT L

−
=

2
2
1=i
Vậy T(n) ∈ O(n).
5. Cài đặt
3
22222
11
−=−−=−
−+
n
kkki


else
Min = Min2;

Max = Ma
lse e
Max = Ma
}
}
IV u án uickSort
D hu án Quiùng t ật to ckSort (QS) để sắp xếp các giá trò trong một mảng các
heo ột th tự, ch ạn tăng dần.
hương áp QuickSort (hay còn gọi là phân đoạn) là một cải tiến của
ương áp sắp xếp đổi chỗ trực tiếp, do C.A.R. Hoare đề xuất.
số t m ứ ẳng h
P ph
ph ph
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 37 - 1. Ý tưởng
Chọn ngẫu nhiên một phần tử x.
từ bên trái ( theo chỉ số i ) trong khi còn a

a
k
a
m
x
Tiếp tục phân hoạch cho phần trái (dãy con thấp nhỏ hơn x), cho phần phải (
lớn hơn x) . . . cho đến khi các phân hoạch chỉ còn lại một phần tử, là sắp xếp xong.
Thuật toán thể hiện ý tưởng đệ qui và cách thiết kế chia để trò.
2. Mô tả thuật toán
- Thuật toán QuickSort
uickSort (a,n)
≡
QS(a,1,n) ;
Mô tả :
i = l;
a[(l+r)/2]; // Chọn phần tử giữa
while (a[i] < x )
while (a[j] > x)
j ;
if (i <= j)
{
đổichỗ a[i] và a[j];
i++;
Input : a[1 n]
Output : a[1 n] không giảm.
Mô tả thuật toán :
Q
- Thuật toán phân hoạch
Input : a[1 n],l,r;
Output : a[l r] tăng dần

Độ phức tạp của thuật toán
• Điều tốt nhất có thể xảy ra trong QuickSort là mỗi giai đoạn phân hoạch
phân chia mảng thành 2 nửa. Điều này khiến cho số lần so sánh cần thiết của
QuickSort thỏa mãn công thúc truy hồi “chia để trò “ sau đây : nTT
nn
+
=
2
2 ≅ nLg n.
2
2
n
T : P
n : Ph
chia sẽ chia n phần tử thành n-1 phần tử trái và 1 phần tử phải. Kết quả
ø cần tới n phép chia ( thay cho lgn), và như thế độ phức tạp sẽ là T(n) = O(n
2
).
uật toán QuickSort
không có hiệu
• Trong trường hợp trung bình :

hí tổn sắp xếp 2 mảng con.
í tổn kiểm tra mỗi phần tử.

• Trường hợp xấu nhất ứng cho việc chọn phần tử x lại có giá trò lớn nhất
hoặc nhỏ nhất trong dãy. Giả sử phần tử lớn nhất được chọn ( phần tử x ), khi đó

nk
ao hàm chi phí so sánh phần
mang ý nghóa là mỗi phần tử
1
k
và sau đó còn lại các mảng con có kích thước k-1 và n-k.

∑
−
++=
kn
TnT
1
1
=

ép toán sau cho cả 2 vế : Nhân cho n và trừ cho
(n-1)C
n-1
:
n
2
k
n
1
Thực hiện liên tiếp các ph
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:


1
1
1
1
1
1
22)1()1(
]
1
2
)[1(2)1
)1(
2
)
n
k
n
k
n
k
k
n
n
n
k
k
TTnnnn
T
n
nnT

−−
nn
nnnnTnnT
+
Suy ra :
nTnnT
nn
2)1(
1
+
+=
−

Chia cả 2 vế cho n(n+1) :
−−
++=+=
21
222
nnn
TTT

∑∑
+
+=+=
1
1
2
121
nn
== 32 kk

∑

n
n
1
1
3
xkn
k
+
=
Như vậy, Độ phức tạp trung bình là O(nlnn)
ma trận

V. Thuật toán nhân Strassen nhân 2
1. Bài toán
Cho 2 ma trận vuông a, b cấp n, n là luỹ thừa 2.
rận vuông cấp n. Dùng thuật toán Strassen nhân 2 ma t
2. Mô tả
Ứng dụng thiết kế chia để trò, mỗi ma trận A, B, C ta chia thành 4 ma trận
ma trận con đó :
⎢
⎡
⎥
⎤
⎢
⎡
⎥
⎤
⎢

⎢
⎣
=
⎥
⎥
⎦
⎢
⎢
⎣
222122212221
BBAACC
Trong đó :
C
11
= A
11
B
11
+ A
12
B
21
C
12
= A
11
B
12
+ A
12

trận và
θ(n
2
) phép c
T(n) = 7T(n
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 40 -
và 18 phép cộng (trừ) các sô. Để tính :
⎦
⎢
⎣
⎥
⎦
222122
bba
Đầu tiên tính 7 tích :
m
2
= (a
11
+ a

Cụ thể, để nhân 2 ma trận vuông cấp 2 , theo Strassen chỉ cần 7 phép nhân
⎥
⎥
⎥
⎤
⎢
⎢
⎡
⎥
⎥
⎤
⎢
⎢
⎢
⎣
⎡
=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
1211
21
1211

)
m
4
= (a
11
+ a
12
) b
22

m
5
= a
11
(b
12
–
m
6
= a
22
(b
21
– b
11
)
m
7
= (a
21
Thuật toán có thể viết như sau :
strass(a, b, c, n)
≡

nhan2(a,b,c);

{
tach(a,a11,a12,a21,a22,n)
tach(b,b11,b12,b21,b22,n)
tach(c,c11,c

strass(a11,b11,d
strass(a12,b21,d2,n/2);
cong(d1,d2,c11,n/2);

strass(a11,b12,d1,n/2);
strass(a12,b22,d2,n/2);
cong(d1,d2,c12,n/2);

strass(a21,b11,d
strass(a22,b21,d2,n/2);
cong(d1,d2,c

Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vn

, 5,
)
)
N
Nếu m = 5, thì kết quả là : ( 6, 7, 8, 1, 2, 3, 4, 5)
là : ( , 6, 7, 8, 1, 2, 3, 4) Nếu m = 4, thì kết quả 5
2. Ý tưởng
* Nếu m = n – : H ùn đổi c phần của 2 mảng ù độ da ằng n :
Nếu m
≠ n – m :
-
- Nếu m < n – m : hoán đổi m phần tử đầu với m phân tử cuối của phần còn
lại. Sau đó trong mảng a[1 n-m] ta chỉ cần hoán đổi m phần tử đầu với
phần còn lại.
- Nếu m > n – m : hoán đổi n-m phần tử đầu tiên với n-m phần tử của phần
n] ta hoán đổi n-m phần tử cuối mảng
với các phần tử của phần đầu.
Như vậy, bằng cách áp dụng phương pháp chia để trò, ta chia bài toán thành
bài to ùn con
- Bài toán thứ nhất là hoán đổi hai mảng con có độ dài bằng nhau, cụ thể là
tử đầu và cuối của mảng cho nhau bằng cách đổi chỗ
từng cặp phần tử tương ứng.
- Bài toán thứ hai cùng dạng với bài toán đã cho nhưng kích thước nhỏ hơn,
nên có thể gọi thuật toán đệ qui để giải và quá trình gọi đệ qui sẽ dừng khi
đạt tới sự hoán đổi 2 phần có độ dài bằng nhau
ậy m chốt ủa thu ïc hiện thao tác hoán đổi 2 nhóm phần tử,
ng khi số lượng phần tử của 2 nhóm cong khác nhau. Nên ta
õ thay thuật toán đệ qui bằng thuật toán lặp.
3. Thuật toán
m oa ác tử nửa co øi b hau

Transpose(a,n,m)
≡
i = m; j = n-m; m = m+1;
Khi ( i
Exchange(a,m-i,m,j);
i = i – j;
Ngược lại
{
j = j – i;
Exchange(a,m-i,m+j,i);
}
ge(a,m-i,m,i); ≠ j)
Nếu ( i > j)
{

} Exchan
* Thuật toán exchange :

input a,
i,j, //vò trí
m á ử cần ho; // So phần t án đổi

Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 43 - - ange(a,1,4,2) Exch4 5 8 6 7 1 2 3
1 2 3
Hoán đổi
- Exchange(a,3,5,1)

4 5 7 6 8 Hoán đổi
4 5 6 7 8 1 2 3
- Exchange(a,3,4,1) - Kết thúc thuật toán.
4. Độ phức tạp thuật toán
Kí hiệu : T(i, j) là số phần tử cần đổi chỗ để hoán đổi dãy i phần tử và dãy j


⇒
i,j) là g lớn i, j.

ët
void Transpose(day a,int n,int m)
{
int i, j;
i = m;
j = n-m;
m = m+1;
while ( i != j )
j)
Exchan
i = i - j;
}
if(i >
{
ge(a,m-i,m,j); Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:


2.
Sắp tăng dần dãy các số bằng thuật toán trộn hai đường trực tiếp.
Ý tưởng

ước la
giai đoạn :
phần tử từ dãy F vào các dãy trung gian F1, F2
)
ộ p phần tử trong dãy F1 với p phần tử trong F2, kết quả trộn
ược đ hi chưa hết dãy F1 và chưa hết dãy F2.
òn được thực hiện trong khi p còn
≤ số các phần tử của F .
g bằng 1.
phân bố và trộn ), số phần tử p sẽ khởi động
là dãy dùng sắp thứ tự , F có nội dung như sau :
2 3 1 1
Thuật toán sắp xếp kiểu trộn hai đường trực tiếp được thực hiện theo nhiều
ëp : b
* Mỗi bước lặp bao gồm hai
Giai đoạn 1 :( Phân bố)
Phân bố luân phiên từng p
trong khi chưa hết dãy F.
Giai đoạn 2 :( Trộn
Trộn từng b
đ ưa vào F, trong k
ớc lặp c * Các bư
Bước đầu tiên p được khởi độn
ột lần Mỗi bước lặp sau( sau m
ïi là : = p * la p 2 .

1 1-3 F 2-90 5-8 6-9 6-7
F2 1-1 1-2 4-7 2-21 1

F 1-1 –2-90 1-2-5-8 4-6-7-9 2-6-7-21 1-1-3

•
Sang lần thứ 3 :
F1 1-1 –2-90 4-6-7-9 1-1-3
F2 1-2-5-8 2-6-7-21

F 1-1-1-2-2-5-8 -90 2-4-6-6-7-7-9-21 1-1-3

•
Sang lần thứ 4 :
F1 1-1-1-2-2-5-8-90 1-1-3
F2 2-4-6-6-7-7-9-21

F 1-1-1-2-2-2-4-5-6-6-7-7-8-9-21-90 1-1-3
•
Sa

ng
1-1-1-2-2-2-4-5-6-6-7-7-8-9-21-90
lần thứ 5 :
F1
F2 1-1-3

F 1-1-1-1-1-2-2-2-3-4-5-6-6-7-7-8-9-21-90

Khi đó F được sắp thứ tự .

- Khởi động lại p : p = p*2;
ể viết thành hàm :
F,n,F1 F2 là n toàn cục
trên 2 thao tác :
ân phiên p phần tử từ dãy F vào các dãy trung gian
àn tử trong F1, và p phần tử trong F2, kết quả lưu
a hết dãy F1 và chưa hết dãy F2;

hiên p phần tử từ dãy F vào các dãy trung gian F1, F2 cho
án hết
Input F
Output
iện

Đọc từng p phần tử trong F và chép luân phiên vào F1, F2;
tự động việc chép luân phiên vào F1 và F2.
a thực
phần tử của F vào F1 trước.
au mo
}
Mô tả trên có th
// , các biế
void mergesort ()
{
p = 1;
while ( p <= n )
{
distribution (p);
merge(p);
p = p * 2;

Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 47 - Đọc p phần tử của F chép vào F1 như thế nào ? Ta đọc từng phần tử của F
và chép phần tử đó vào F1; Việc đọc chép từng phần tử này còn được thực hiện
trong khi chưa đủ p phần tử và chưa hết dãy F.
Vậy thao tác phân bố có thể mô tả chi tiết như sau :
do
{
i = 1;
while ( i <= p && chưa hết dãy F ) chép vào F1;
chép vào F2;
}
ile ( chưa hết dãy F);
Thao tác phân bố cài đặt thành một hàm như sau :
oàn cục.
t p)

while( i<=p &&
{
if(k==1)
{
h1++;
F1
}
else
{
h2++;
F2[h2] = F[l];
}
i++;
l+

Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version -
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 48 - }
p phần tử trong F1 và p phần tử trong F2.
Trộn từng
}
Trong khi (chưa hết
chép các phần t
Trong khi (chưa hết
ch

- Ta cần c
hoạt động như thế nào ? Đo
- Đ øng phần tử tron
nhỏ hơn thì chép phần tử t
phần tử của F1; n
- :Thao
va
; Và khi đó ta cần xử lý các trường hợp
sau :
Trong trường hợp chưa hết dãy F1 và chưa hết dãy F2 :
Nếu chưa đủ p phần tử trong F1, thì đọc và chép các phần tử của F1
vào F cho đủ p; Tương tự như vậy cho F2.
a2) Cài đặt :
/* F,F1,F2,n,h
1
,h
2
là các biến toàn cục.
Ta dùng các biến :
- r
1