GVGD: Trng Phc Hi
Phng pháp chia đ tr
(devide and conquer)
2
Ni dung
1. Phng pháp chia đ tr
3. Bài toán tìm cc tr ca dãy
4. Merge Sort
2. Tìm kim nh phân
5. Quick Sort
3
Phng pháp chia đ tr
 T tng

 Chia nh bài toán ln thành nhng bài toán con d gii
quyt hn

  gii bài toán kích thc N

 Chia bài toán thành các bài toán con có kích thc nh hn.
Có th s dng k thut chia đ tr đ tip tc chia nh bài
toán con

 Gii các bài toán con ri tng hp li đ đc li gii cho
bài toán ban đu



4
Phng pháp chia đ tr
 Mô hình tng quát ca k thut chia đ tr

…
Bài toán c s
(base problem)
problem P
…
p
1
p
2
p
k
5
Phng pháp chia đ tr
 Các bc tip cn phng pháp chia đ tr

 Bc 1: chia (divide) bài toán thành 2 hay nhiu bài toán
con nh hn

 Bc 2: tr (conquer) (gii) các bài toán con theo phng
pháp này mt cách đ quy

 Bc 3: gp (combine) li gii các bài toán con đ to
thành li gii cho bài toán ban đu
6
Phng pháp chia đ tr
 Gii thut tng quát

DAC(P)
If (P đ nh) Then

return LiGii(P)
Else
Chia P thành các th hin p1, p2, pk
Áp dng chia đ tr cho tng th hin pi
Kt Hp (DAC(p1), DAC(p2), , DAC(pk))

End If
Cui DAC
7
Phng pháp chia đ tr
  phc tp ca gii thut

 T(N): thi gian gii bài toán kích thc N
 a: s bài toán con
 N/b: kích thc ca các bài toán con
 D(N): thi gian chia nh bài toán ban đu
 C(N): thi gian kt hp các bài toán con

 Phng trình đ quy
 

 vi  đ nh



   ngc li

8
Ni dung
1. Phng pháp chia đ tr

3. Bài toán tìm cc tr ca dãy
4. Merge Sort
2. Tìm kim nh phân
5. Quick Sort
9
Tìm kim nh phân
 Cho dãy A gm N phn t đc sp th t không
gim. Cho bit phn t x có tn ti trong dãy A hay
không, nu có ch ra v trí xut hin

 Input: A[0…N-1], x

 Output

 index = -1, nu x không tn ti trong A

 index ≥ 0 nu A[index] = x

10
Tìm kim nh phân
 Gii thut chia đ tr cho bài toán

 Chia: chia dãy A thành 2 na dãy con




 Tr: da vào tính cht có th t ca A đ xác đnh nên tìm
x trong na dãy con nào


 Gp: không cn vì tìm ngay trên dãy A
< m > m m
x
11
Tìm kim nh phân
 Gii thut chia đ tr áp dng cho Binary Search

BinSearch(A[], l, r, x)
If (l > r) Then
return -1
Else
m = [(l + r)/2]
If (A[m] = x) Then
return m
Else If (x < A[m]) Then
return BinSearch(A, l, m-1, x)
Else
return BinSearch(A, m+1, r, x)
Cui If
Cui If

Cui BinSearch

12
Tìm kim nh phân
 Cài đt ngôn ng

int BinSearch(int A[], int l, int r, int x)
{


if (l > r)
return -1
else
{
int m = (l + r)/2;

if (A[m] == x)
return m;
else if (x < A[m])
return BinSearch(A, l, m – 1, x);
else return BinSearch(A, m + 1, r, x);
}
}

13
Ni dung
1. Phng pháp chia đ tr
3. Bài toán tìm cc tr ca dãy
4. Merge Sort
2. Tìm kim nh phân
5. Quick Sort
14
Bài toán tìm cc tr ca dãy
 Bài toán

 Cho dãy A gm N phn t, tìm giá tr ln nht ca dãy A

 T tng chia đ tr

 Chia dãy thành 2 dãy con và tìm giá tr ln nht trên tng

dãy con

 So sánh các giá tr ln nht ca mi dãy con đ tìm ra giá
tr ln nht ca dãy ban đu


15
Bài toán tìm cc tr ca dãy
 Minh ha tìm giá tr max ca dãy bng phng
pháp chia đ tr
10, 16, 7, 39, 3, 24, 17, 41
10, 16, 7, 39 3, 24, 17, 41
10, 16 7, 39 3, 24 17, 41
10 16 7 39 3 24 17 41
16
24 41 39
41 39
Max = 41
16
Bài toán tìm cc tr ca dãy
 Chia đ tr cho bài toán tìm max ca dãy

 Chia: chia dãy A[l r] thành 2 dãy con A[l m] và A[m+1 r]
vi m = (l + r) div 2

 Tr: tìm max ca mi dãy con mt cách đ quy. t left là
max ca dãy A[l m], right là max ca dãy A[m+1 r]

 Gp: so sánh giá tr ca left và right đ tìm max cho dãy
ban đu

17
Bài toán tìm cc tr ca dãy
 Gii thut tìm max theo phng pháp chia đ tr


Max(A[], l, r)
If (l = r) Then
return A[l]
Cui If
m = (l + r) div 2
left = Max(A, l, m)
right = Max(A, m + 1, r)
return (left> right)?left:right
Cui Max

18
Bài toán tìm cc tr ca dãy
 Cài đt ngôn ng

int Max(int A[], int l, int r)
{

if (l == r)
return A[l];
int m = (l + r)/2;
int maxL = Max(A, l, m);
int maxR = Max(A, m + 1, r);

return (maxL > maxR)? maxL: maxR;
}


19
Ni dung
1. Phng pháp chia đ tr
3. Bài toán tìm cc tr ca dãy
4. Merge Sort
2. Tìm kim nh phân
5. Quick Sort
20
Merge Sort
 Ý tng phng pháp trn t nhiên

 Tách và phân phi luân phiên các đng chy trên A vào 2
dãy B và C

 Trn ln lt tng cp đng chy trên B và C vào A vi
mc đích gim dn s đng chy trên A

 Dãy đc sp th t nu ch tn ti 1 đng chy


21
Merge Sort
 Ví d minh ha


Cho dãy: 2 2 8 16 4 6 13 15 6 20 3 9
Tách đng chy: 2 2 8 16 4 6 13 15 6 20 3 9



Tách B: 2 2 8 16 6 20
Tách B1: 2 2 8 16
C1: 6 20

Trn B1 và C1 vào B: 2 2 6 8 16 20
Tách C: 4 6 13 15 3 9
Tách B2: 4 6 13 15
C2: 3 9
Trn B2 và C2 vào C: 3 4 6 9 13 15


Trn B và C vào A: 2 2 3 4 6 6 8 9 13 15 16 20
22
Merge Sort
 Cây minh ha quá trình chia đ tr
A
2 2 8 16 4 6 13 15 6 20 3 9
B
2 2 8 16 6 20
C
4 6 13 15 3 9
B1
2 2 8 16
C1
6 20
B2
4 6 13 15
C2
3 9
23

Merge Sort
 T tng chia đ tr ca Merge Sort

 Chia: phân phi các đng chy t dãy A sang 2 dãy con B
và C theo nguyên tc luân phiên

 Tr: áp dng t tng trên đ tip tc phân chia các dãy B
và C mt cách đ quy

 Gp: trn tng cp đng chy trên B và C đ to thành
dãy A mi
24
Merge Sort
 Gii thut trn t nhiên theo p.pháp chia đ tr

TronTuNhien(A[], N)
If (N > 0) Then
PhanPhoi(A, N, B, nB, C, nC) //chia
//Nu s đng chy ca A > 1
If (nB > 0) AND (nC > 0) Then
TronTuNhien(B, nB) //tr
TronTuNhien(C, nC) //tr
Cui If
Tron(B, nB, C, nC, A, N) //gp
Cui If
Cui TronTuNhien

25
Merge Sort
 Cài đt hàm sp xp trn


void MergeSort(int A[], int N)
{

int B[MAX], nB = 0, C[MAX], nC = 0;
if (N > 0)
{
Distribute(A, N, B, nB, C, nC);
if (nB > 0 && nC > 0)
{
MergeSort(B, nB);
MergeSort(C, nC);
}
Merge(B, nB, C, nC, A, N);
}
}