14/04/2008
1
CHIA ĐỂ TRN
CHIA
ĐỂ
TRN
DIVIDE AND CONQUER
Phạm Thế Bảo
Khoa Toán – Tin học
Trường Đại học Khoa học Tự nhiên Tp.HCM
Nội dung
•Kỹthuật quan trọng, đượcápdụng rộng rãi để
thiết
kế
các
giải
thuật
có
hiệu
quả
.
thiết
kế
các
giải
thuật
có
hiệu
quả
.
•Để giải quyếtmột bài toán kích thướcn,tachia
bài toán này thành mộtsốbài toán con có kích
thướcnhỏhơn. Giải các bài toán con này rồitổng
hợpkếtquảlạiđể đượclờigiảibanđầu.
•Những bài toán con này cũng có thểđược chia
thành
các
bài
toán
có
kích
thước
nhỏ
hơn
nữa
để
thành
các
bài
toán
có
kích
thước
nhỏ
hơn
nữa
để
giải quyết. Quá trình này sẽđưađếnnhững bài
toán mà lờigiảilàhiển nhiên hay dễdàng thực
hiện. Ta gọinhững bài toán này là bài toán cơsở.
Phạm Thế Bảo
14/04/2008
2
Mộtsốbài toán tiêu biểu
•MergeSort và QuickSort
ố
•Nhân s
ố
nguyên lớn
•Xếplịch thi đấuthểthao
•Bài toán con cân bằng
•…
Phạm Thế Bảo
MergeSort và QuickSort
•Chia tậpdữliệulàm2tập con, quá trình chia
đế
khi
hỉ
ò
01
hầ
tử
Æ
dừ
(
bài
tá
đế
n
khi
c
hỉ
c
ò
n
01
p
hầ
n
tử
Æ
dừ
ng
(
bài
t
o
á
n
cơsở), tổng hợp2tập con bằng cách trộncó
thứtựÆtậpdữliệuđượcsắpxếp.
•Giống MergeSort nhưng cầnphầntửcầm canh
đứng
giữa
để
chia
thành
2
tập
con
:
một
tập
sẽ
đứng
giữa
để
chia
thành
2
tập
con
:
một
tập
sẽ
có các phầntửcó giá trịnhỏhơn hay bằng, tập
còn lạisẽcó các phầntửcó giá trịlớnhơn.
Phạm Thế Bảo
14/04/2008
3
Bài toán nhân hai sốnguyên lớn
•Trong các ngôn ngữlậptrình,kiểudữliệusố
nguyên
đều
có
miền
giá
trị
hạn
chế
nguyên
đều
có
miền
giá
trị
hạn
chế
,
ví dụ: Pascal, C sốnguyên từ-32768 đến 32767
•Khi gặpứng dụng cầnsốnguyên lớnhơn
(hàng chục hay hàng trămchữsố), chúng ta
phảiđixâydựng cấutrúcdữliệusốnguyên
lớn
Các
thao
tác
đi
kèm
là
:
cộng
trừ
nhân
lớn
.
Các
thao
tác
đi
kèm
là
:
cộng
,
trừ
,
nhân
,…
•Chúng ta xem xét cách nhân 02 sốnguyên lớn
có n chữsốsao cho hiệuquả.
Phạm Thế Bảo
•Nếuchúngtadùngcáchnhânthôngthường,
nghĩalàtừng chữsốnhân với nhau rồicộng lại
thì chi phí là O(n2).
•Á
p
dụ
n
g
k
ỹ
t
h
uật
c
hi
a
để
t
r
ị
.
T
a
c
hi
a
0
2
số
p
dụg
ỹ
tuật
ca
để
tị
.
a
ca
0
số
nguyên X, Y thành các sốnguyên lớncón/2
chữsố:X=A10
n/2+B và Y=C10n/2+D
Ví dụ: A=1234 thì A=12x102+34
Khi đóX.Y=AC10
n+(AD+BC)10n/2+BD.
Giố
h
ê
l i
hi
iế
để
ó
bài
Giố
ng n
hư
tr
ê
nta
l
ạ
i
c
hi
at
iế
ptục
để
c
ó
bài
toán cơsởdễdàng thựchiện.
Phạm Thế Bảo
14/04/2008
4
•Theo cách làm trên thì phảithựchiện4phép
nhân các sốnguyên lớnn/2chữsố(AC, AD,
BC, BD), sau đódùng3phépcộng các số
nguyên lớnnchữsốvà2phépnhanvới10
nvà
ể
ổ
10n/2đ
ể
t
ổ
ng hợp.
•Phép cộng sốnguyên lớncần O(n), phép nhân
10ncó thểthựchiệnđơngiảnbằng cách thêm
nchữsố0Æcũng cần O(n). GọiT(n)làthời
gian
nhân
hai
số
nguyên
lớn
ta
có
phương
gian
nhân
hai
số
nguyên
lớn
,
ta
có
phương
trình đệ quy:
Phạm Thế Bảo
•Giảiphương trình ta có T(n) =
Ækhông cảithiện!
•Viếtlại:
XY AC10
n
+[(A
B)(D
C)+AC+BD]10
n/2
+BD
X
.
Y
=
AC10
n
+[(A
-
B)(D
-
C)+AC+BD]10
n/2
+BD
Công thức này chỉcần tính 3 phép nhân của các
sốnguyên lớnn/2 chữsố: AC,BD và (A-B)(D-
C), 6 phép cộng trừvà 2 phép nhân với10
n.
L
ập
lu
ậ
ntươn
g
t
ự
ta có
p
hươn
g
trình đ
ệ
q
u
y
:
ập
ậ
g
ự
p g
ệ
qy
T(1)=1
T(n)=
Phạm Thế Bảo
Nghiệm?
14/04/2008
5
Nghiệmcủaphương trình T(n)=
Æcảithiệnhơn.
Thuậtgiải thô:
longDigit multi2Integer(longDigit X, longDogit Y, int n){
if( 1) th t X*Y
if(
n=
1)
th
en re
t
urn
X*Y
;
A=left(X,n/2);
B=right(X,n/2);
C=left(Y,n/2);
D=right(Y,n/2);
m1=multi2Integer(A,C,n/2);
2 lti2I t (A
BD
C
/2)
m
2
=mu
lti2I
n
t
eger
(A
-
B
,
D
-
C
,n
/2)
;
m3=multi2Integer(B,D,n/2);
return (m1*10n+(m1+m2+m3)*10n/2 +m3);
}
Phạm Thế Bảo
Xếplịch thi đấuthểthao
•Xét việcxếplịch thi đấu vòng tròn mộtlượt
cho
n
đội
đá
banh
Mỗi
đội
thi
đấu
với
nhau
cho
n
đội
đá
banh
.
Mỗi
đội
thi
đấu
với
nhau
,
mỗiđộichỉđấunhiềunhấtmộttrậnmộtngày.
Làm sao ta xếplịch thi đấuchosốngày ít nhất.
•Ta có tổng sốtrậnđấucủatoàngiảilà
nếunchẵn thì ta có thểsắpn/2cặpthiđấu
ộ
à
Æ
ầ
í
hấ
(
1
)
à
Nế
trong m
ộ
tng
à
y
Æ
c
ầ
n
í
tn
hấ
t
(
n-
1
)
ng
à
y.
Nếu
nlẻthìtacóthểsắp (n-1)/2 cặpthiđấutrong
một ngày Æcầnítnhất n ngày
Phạm Thế Bảo
