Cấu trúc dữ liệu và giải thuật Học viện bưu chính viễn thông
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.18 MB, 144 trang )
HC VIN CÔNG NGH BU CHÍNH VIN THÔNG
CU TRÚC D LIU VÀ GII THUT
(Dùng cho sinh viên h đào to đi hc t xa)
Lu hành ni b
HÀ NI - 2007
LI NÓI U
Cu trúc d liu và gii thut là mt trong nhng môn hc c bn ca sinh viên ngành Công
ngh thông tin. Các cu trúc d liu và các gii thut đc xem nh là 2 yu t quan trng nht
trong lp trình, đúng nh câu nói ni ting ca Niklaus Wirth: Chng trình = Cu trúc d liu +
Gii thut (Programs = Data Structures + Algorithms). Nm vng các cu trúc d liu và các gii
thut là c s đ sinh viên tip cn vi vi
c thit k và xây dng phn mm cng nh s dng các
công c lp trình hin đi.
Cu trúc d liu có th đc xem nh là 1 phng pháp lu tr d liu trong máy tính
nhm s dng mt cách có hiu qu các d liu này. Và đ s dng các d liu mt cách hiu qu
thì cn phi có các thut toán áp dng trên các d liu đó. Do v
y, cu trúc d liu và gii thut là
2 yu t không th tách ri và có nhng liên quan cht ch vi nhau. Vic la chn mt cu trúc
d liu có th s nh hng ln ti vic la chn áp dng gii thut nào.
Tài liu “Cu trúc d liu và gii thut” bao gm 7 chng, trình bày v các cu trúc d liu
và các gii thut c bn nh
t trong tin hc.
Chng 1 trình bày v phân tích và thit k thut toán. u tiên là cách phân tích 1 vn đ,
t thc tin cho ti chng trình, cách thit k mt gii pháp cho vn đ theo cách gii quyt bng
máy tính. Tip theo, các phng pháp phân tích, đánh giá đ phc tp và thi gian thc hin gii
thut cng đc xem xét trong chng. Chng 2 trình bày v đ qui, mt khái nim rt c bn
trong toán hc và khoa hc máy tính. Vi
c s dng đ qui có th xây dng đc nhng chng
trình gii quyt đc các vn đ rt phc tp ch bng mt s ít câu lnh, đc bit là các vn đ
mang bn cht đ qui.
Chng 3, 4, 5, 6 trình bày v các cu trúc d liu đc s dng rt thông dng nh mng
và danh sách liên kt, ngn xp và hàng đi, cây, đ th. ó là các c
u trúc d liu cng rt gn
gi vi các cu trúc trong thc tin. Chng 7 trình bày v các thut toán sp xp và tìm kim.
Các thut toán này cùng vi các k thut đc s dng trong đó đc coi là các k thut c s
cho lp trình máy tính. Các thut toán đc xem xét bao gm các lp thut toán đn gin và c
các thut toán cài đt phc tp nhng có thi gian thc hin ti u.
Cui mi phn đu có các câu hi và bài tp đ sinh viên ôn luyn và t kim tra kin thc
ca mình. Cui tài liu có các ph lc hng dn tr li câu hi, mã ngun tham kho và tài liu
tham kho.
V nguyên tc, các cu trúc d liu và các gii thut có th đc biu din và cài đt bng
bt c ngôn ng lp trình hin đi nào. Tuy nhiên, đ có đc các phân tích sâu sc h
n và có kt
qu thc t hn, tác gi đã s dng ngôn ng lp trình C đ minh ho cho các cu trúc d liu và
thut toán. Do vy, ngoài các kin thc c bn v tin hc, ngi đc cn có kin thc v ngôn ng
lp trình C.
Cui cùng, mc dù đã ht sc c gng nhng chc chn không tránh khi các thiu sót. Tác
gi rt mong nhn
đc s góp ý ca bn đc và đng nghip đ tài liu đc hoàn thin hn.
Hà Ni, tháng 10/2007
3
CHNG 1
PHÂN TÍCH VÀ THIT K GII THUT
Chng 1 trình bày các khái nim v gii thut và phng pháp tinh chnh tng bc
chng trình đc th hin qua ngôn ng din đt gii thut. Chng này cng nêu phng pháp
phân tích và đánh giá mt thut toán, các khái nim liên quan đn vic tính toán thi gian thc
hin chng trình.
Trong mi phn đu có các minh ho c th. Phn đu đa ra ví d v bài toán nút giao
thông và phng pháp gii quyt bài toán t phân tích v
n đ cho đn thit k gii thut, tinh
chnh tng bc cho ti mc c th hn. Phn 2 đa ra mt ví d v phân tích và tính toán thi
gian thc hin gii thut sp xp ni bt.
hc tt chng này, sinh viên cn nm vng phn lý thuyt và tìm các ví d tng t đ
thc hành phân tích, thit k, và đánh giá gii thut.
1.1 GII THUT VÀ NGÔN NG DIN T GII THUT
1.1.1 Gii thut
Trong thc t, khi gp phi mt vn đ cn phi gii quyt, ta cn phi đa ra 1 phng
pháp đ gii quyt vn đ đó. Khi mun gii quyt vn đ bng cách s dng máy tính, ta cn
phi đa ra 1 gii pháp phù hp vi vic thc thi bng các ch
ng trình máy tính. Thut ng
“thut toán” đc dùng đ ch các gii pháp nh vy.
Thut toán có th đc đnh ngha nh sau:
Thut toán là mt chui hu hn các lnh. Mi lnh có mt ng ngha rõ ràng và có th
đc thc hin vi mt lng hu hn tài nguyên trong mt khong hu hn thi gian.
Chng hn lnh x = y + z là mt lnh có các tính cht trên.
Trong mt thu
t toán, mt lnh có th lp đi lp li nhiu ln, tuy nhiên đi vi bt k b d
liu đu vào nào, thut toán phi kt thúc sau khi thc thi mt s hu hn lnh.
Nh đã nói trên, mi lnh trong thut toán phi có ng ngha rõ ràng và có th đc thc
thi trong mt khong thi gian hu hn. Tuy nhiên, đôi khi mt lnh có ng ngha rõ ràng
đi vi
ngi này nhng li không rõ ràng đi vi ngi khác. Ngoài ra, thng rt khó đ chng minh
mt lnh có th đc thc hin trong 1 khong hu hn thi gian. Thm chí, k c khi bit rõ ng
ngha ca các lnh, cng khó đ có th chng minh là vi bt k b d liu đu vào nào, thut
toán s dng.
Tip theo, chúng ta s xem xét mt ví d v
xây dng thut toán cho bài toán đèn giao
thông:
Gi s ngi ta cn thit k mt h thng đèn cho mt nút giao thông có nhiu đng giao
nhau phc tp. xây dng tp các trng thái ca các đèn giao thông, ta cn phi xây dng mt
chng trình có đu vào là tp các ngã r đc phép ti nút giao thông (li đi thng cng đc
xem nh là 1 ngã r) và chia tp này thành 1 s ít nht các nhóm, sao cho tt c các ngã r trong
nhóm có th đc đi cùng lúc mà không xy ra tranh chp. Sau đó, chúng ta s gn trng thái ca
các đèn giao thông vi mi nhóm va đc phân chia. Vi cách phân chia có s nhóm ít nht, ta
s xây dng đc 1 h thng đèn giao thông có ít trng thái nht.
4
Chng hn, ta xem xét bài toán trên vi nút giao thông đc cho nh trong hình 1.1
di. Trong nút giao thông trên, C và E là các đng 1 chiu, các đng còn li là 2 chiu. Có tt
c 13 ngã r ti nút giao thông này. Mt s ngã r có th đc đi đng thi, chng hn các ngã r
AB (t A r sang B) và EC. Mt s ngã r thì không đc đi đng thi (gây ra các tuyn giao
thông xung đt nhau), chng hn AD và EB. H thng đèn ti nút giao thông phi hot đ
ng sao
cho các ngã r xung đt (chng hn AD và EB) không đc cho phép đi ti cùng mt thi đim,
trong khi các ngã r không xung đt thì có th đc đi ti cng 1 thi đim.
Hình 1.1 Nút giao thông
Chúng ta có th mô hình hóa vn đ này bng mt cu trúc toán hc gi là đ th (s đc
trình bày chi tit chng 5). th là mt cu trúc bao gm 1 t
p các đim gi là đnh và mt
tp các đng ni các đim, gi là các cnh. Vn đ nút giao thông có th đc mô hình hóa bng
mt đ th, trong đó các ngã r là các đnh, và có mt cnh ni 2 đnh biu th rng 2 ngã r đó
không th đi đng thi. Khi đó, đ th ca nút giao thông hình 1.1 có th đc biu din nh
hình 1.2.
Hình 1.2 th ngã r
A
B
C
D
E
ACAB AD
BCBA BD
DBDA DC
EBEA EC
ED
5
Ngoài cách biu din trên, đ th còn có th đc biu din thông qua 1 bng, trong đó phn
t hàng i, ct j có giá tr 1 khi và ch khi có 1 cnh ni đnh i và đnh j.
AB AC AD BA BC BD DA DB DC EA EB EC ED
AB 1 1 1 1
AC 1 1 1 1 1
AD 1 1 1
BA
BC 1 1 1
BD 1 1 1 1 1
DA 1 1 1 1 1
DB 1 1 1
DC
EA 1 1 1
EB 1 1 1 1 1
EC 1 1 1 1
ED
Bng 1.1 Biu din đ th ngã r bng bng
Ta có th s dng đ th trên đ gii quyt vn đ thit k h thng đèn cho nút giao thông
nh đã nói.
Vic tô màu mt đ th là vic gán cho mi đnh ca đ th mt màu sao cho không có hai
đnh đc ni bi 1 cnh nào đó li có cùng mt màu. D thy rng v
n đ nút giao thông có th
đc chuyn thành bài toán tô màu đ th các ngã r trên sao cho phi s dng s màu ít nht.
Bài toàn tô màu đ th là bài toán đã xut hin và đc nghiên cu t rt lâu. Tuy nhiên, đ
tô màu mt đ th bt k vi s màu ít nht là bài toán rt phc tp. gii bài toán này, ngi ta
thng s dng phng pháp “vét cn” đ th tt c các kh nng có th
. Có ngha, đu tiên th
tin hành tô màu đ th bng 1 màu, tip theo dùng 2 màu, 3 màu, v.v. cho ti khi tìm ra phng
pháp tô màu tho mãn yêu cu.
Phng pháp vét cn có v thích hp vi các đ th nh, tuy nhiên đi vi các đ th phc
tp thì s tiêu tn rt nhiu thi gian thc hin cng nh tài nguyên h thng. Ta có th tip cn
vn đ theo hng c gng tìm ra mt gii pháp
đ tt, không nht thit phi là gii pháp ti u.
Chng hn, ta s c gng tìm mt gii pháp tô màu cho đ th ngã r trên vi mt s màu khá ít,
gn vi s màu ít nht, và thi gian thc hin vic tìm gii pháp là khá nhanh. Gii thut tìm các
gii pháp đ tt nhng cha phi ti u nh vy gi là các gii thut tìm theo “cm tính”.
i vi bài toán tô màu
đ th, mt thut toán cm tính thng đc s dng là thut toán
“tham n” (greedy). Theo thut toán này, đu tiên ta s dng mt màu đ tô nhiu nht s đnh có
th, tho mãn yêu cu bài toán. Tip theo, s dng màu th 2 đ tô các đnh cha đc tô trong
bc 1, ri s dng đn màu th 3 đ tô các đnh cha đc tô trong bc 2, v.v.
6
tô màu các đnh vi màu mi, chúng ta thc hin các bc:
- La chn 1 đnh cha đc tô màu và tô nó bng màu mi.
- Duyt qua các đnh cha đc tô màu. Vi mi đnh dng này, kim tra xem có cnh
nào ni nó vi mt đnh va đc tô bi màu mi hay không. Nu không có cnh nào
thì ta tô màu đnh này bng màu mi.
Thut toán này đc gi là “tham n” vì ti mi bc nó tô màu t
t c các đnh có th mà
không cn phi xem xét xem vic tô màu đó có đ li nhng đim bt li cho các bc sau hay
không. Trong nhiu trng hp, chúng ta có th tô màu đc nhiu đnh hn bng 1 màu nu
chúng ta bt “tham n” và b qua mt s đnh có th tô màu đc trong bc trc.
Ví d, xem xét đ th hình 1.3, trong đó đnh 1 đã đc tô màu đ. Ta thy rng hoàn toàn
có th tô c
2 đnh 3 và 4 là màu đ, vi điu kin ta không tô đnh s 2 màu đ. Tuy nhiên, nu ta
áp dng thut toán tham n theo th t các đnh ln dn thì đnh 1 và đnh 2 s là màu đ, và khi
đó đnh 3, 4 s không đc tô màu đ.
Hình 1.3 th
Bây gi ta s xem xét thut toán tham n đc áp dng trên đ th các ngã r hình 1.2 nh
th nào. Gi s ta bt đu t đnh AB và tô cho đnh này màu xanh. Khi đó, ta có th tô cho đnh
AC màu xanh vì không có cnh ni đnh này vi AB. AD cng có th tô màu xanh vì không có
cnh ni AD vi AB, AC. nh BA không có cnh ni ti AB, AC, AD nên cng có th đc tô
màu xanh. Tuy nhiên, đnh BC không tô đc màu xanh vì tn ti cnh ni BC và AB. Tng t
nh vy, BD, DA, DB không th tô màu xanh vì tn ti cnh ni chúng ti mt trong các đnh đã
tô màu xanh. Cnh DC thì có th
tô màu xanh. Cui cùng, cnh EA, EB, EC cng không th tô
màu xanh trong khi ED có th đc tô màu xanh.
1 5
3
4
2
a) th ban đu
1 5
3
4
2
b) Tô màu theo thut toán tham n
1 5
3
4
2
c) Mt cách tô màu tt hn
7
Hình 1.4 Tô màu xanh cho các đnh ca đ th ngã r
Tip theo, ta s dng màu đ đ tô các đnh cha đc tô màu bc trc. u tiên là
BC. BD cng có th tô màu đ, tuy nhiên do tn ti cnh ni DA vi BD nên DA không đc tô
màu đ. Tng t nh vy, DB không tô đc màu đ còn EA có th tô màu đ. Các đnh cha
đc tô màu còn li đ
u có cnh ni ti các đnh đã tô màu đ nên cng không đc tô màu.
Hình 1.5 Tô màu đ trong bc 2
Bc 3, các đnh cha đc tô màu còn li là DA, DB, EB, EC. Nu ta tô màu đnh DA là
màu lc thì DB cng có th tô màu lc. Khi đó, EB, EC không th tô màu lc và ta chn 1 màu
th t là màu vàng cho 2 đnh này.
ACAB AD
BCBA BD
DBDA DC
EBEA EC
ED
ACAB AD
BCBA BD
DBDA DC
EBEA EC
ED
8
Hình 1.6 Tô màu lc và màu vàng cho các đnh còn li
Nh vy, ta có th dùng 4 màu xanh, đ, lc, vàng đ tô màu cho đ th ngã r hình 1.2
theo yêu cu nh đã nói trên. Bng tng hp màu đc mô t nh sau:
Màu Ngã r
Xanh AB, AC, AD, BA, DC, ED
BC, BD, EA
Lc DA, DB
Vàng EB, EC
Bng 1.2 Bng tng hp màu
Thut toán tham n không đm bo cho ra kt qu ti u là s màu ít nht đc dùng. Tuy
nhiên, ngi ta có th dùng mt s tính cht ca đ th đ đánh giá kt qu thu đc.
Tr li vi vn đ nút giao thông, t kt qu tô màu trên, ta có th thit k h thng đèn
giao thông theo bng tng hp màu trên, trong đó m
i trng thái ca h thng đèn tng ng vi
1 màu. Ti mi trng thái, các ngã r nm ti hàng tng ng vi màu đó đc cho phép đi, các
ngã r còn li b cm.
1.1.2 Ngôn ng din đt gii thut và k thut tinh chnh tng bc
Sau khi đã xây dng đc mô hình toán hc cho vn đ cn gii quyt, tip theo, ta có th
hình thành mt thu
t toán cho mô hình đó. Phiên bn đu tiên ca thut toán thng đc din t
di dng các phát biu tng đi tng quát, và sau đó s đc tinh chnh dn tng bc thành
chui các lnh c th, rõ ràng hn. Ví d trong thut toán tham n trên, ta mô t bc thc hin
mc tng quát là “La chn 1 đnh cha đc tô màu”. Vi phát biu nh vy, ta hy vng rng
ngi đc có th nm đc ý tng thc hin thao tác. Tuy nhiên, đ chuyn các phát biu đó
ACAB AD
BCBA BD
DBDA DC
EBEA EC
ED
9
thành chng trình máy tính, cn phi qua 1 s bc tinh chnh cho ti khi đt đn mc các phát
biu đu có th đc chuyn đi trc tip sang các lnh ca ngôn ng lp trình.
Tr li ví d v bài toán tô màu đ th bng thut toán tham n. Ta s xem xét vic mô t
thut toán t mc tng quát cho ti mt s mc c th hn. Ti bc nào đó, gi s ta có đ th G
có 1 s đnh đã đc tô màu theo quy tc đã nói trên. Th tc Tham_an di đây s xác đnh 1
tp các đnh cha đc tô màu thuc G mà có th cùng đc tô bi 1 màu mi. Th tc này s
đc gi đi gi li nhiu ln cho ti khi tt c các đnh ca G đã đc tô màu. mc tng quát,
th t
c đc mô t nh sau:
void Tham_an(GRAPH: G, SET: Mau_moi)
{
Mau_moi = Tp rng;
For mi đnh v cha đc tô màu thuc G
If v không đc ni ti đnh nào trong tp Mau_moi
{
Tô màu mi cho đnh v;
a v vào tp Mau_moi;
}
}
Trong th tc trên, ta s dng mt ngôn ng din đt gii thut ta nh ngôn ng lp trình
C. Trong ngôn ng này, các lnh đc mô t di dng ngôn ng t nhiên nhng vn tuân theo cú
pháp ca ngôn ng lp trình.
Ta nhn thy rng các phát biu trong th tc trên còn rt tng quát, và cha tng ng vi
các lnh trong ngôn ng lp trình, chng hn các điu kin ki
m tra trong câu lnh For và If
mc mô t hin ti là không thc hin đc trong C. th tc có th thc thi đc, ta cn phi
tinh chnh mt s bc đ có th chuyn đi v chng trình trong ngôn ng lp trình C thông
thng.
u tiên, ta xem xét lnh If trên. kim tra xem đnh v có ni ti mt đnh nào đó trong
tp Mau_moi hay không, ta xem xét tng đnh w trong Mau_moi và s dng đ th G
đ kim tra
xem có tn ti cnh ni v à w không. lu gi kt qu kim tra, ta s dng mt bin ton_tai.
Khi đó, th tc đc tinh chnh nh sau:
void Tham_an(GRAPH: G, SET: Mau_moi)
{
int ton_tai;
Mau_moi = Tp rng;
For mi đnh v cha đc tô màu thuc G
{
ton_tai = 0;
For mi đnh w thuc Mau_moi
If tn ti cnh ni v và w trong G
ton_tai = 1;
If ton_tai = = 1
{
10
Tô màu mi cho đnh v;
a v vào tp Mau_moi;
}
}
}
Nh vy, ta có th thy rng điu kin kim tra trong phát biu If đã đc mô t c th hn
bng các phát nh hn,và các phát biu này có th d dàng chuyn thành các lnh c th trong C.
Tip theo, ta s tinh chnh các vòng lp For đ duyt qua các đnh thuc G và thuc Mau_moi.
làm điu này, tt nht là ta thay For bng mt vòng lp While, bin v ban đu đc gán là phn t
đu tiên cha tô màu trong tp G, và ti mi bc lp, bin v s đc thay bng phn t cha tô
màu tip theo trong G. Vòng lp F bên trong có th thc hin tng t.
Void Tham_an(GRAPH: G, SET: Mau_moi)
{
int ton_tai;
int v, w
Mau_moi = Tp rng;
v = đnh cha tô màu đu tiên trong G ;
While v != NULL
{
ton_tai = 0;
w = đnh đu tiên trong Mau_moi;
While w != NULL{
If tn ti cnh ni v và w trong G
ton_tai = 1;
w = đnh tip theo trong Mau_moi ;
}
If ton_tai = = 1
{
Tô màu mi cho đnh v;
a v vào tp Mau_moi;
}
v = đnh cha tô màu tip theo trong G;
}
}
Nh vy, ta thy các phát biu trong th tc đã khá c th, tuy nhiên, đ chuyn đi thành
chng trình trong ngôn ng C thì cn ti vài bc tinh chnh na. Bn đc hãy xem nh đó là
bài tp và t gii đ hiu rõ v ngôn ng din đt gii thut cng nh k thut tinh chnh tng
bc.
1.2 PHÂN TÍCH THUT TOÁN
Vi mi vn đ c
n gii quyt, ta có th tìm ra nhiu thut toán khác nhau. Có nhng thut
toán thit k đn gin, d hiu, d lp trình và sa li, tuy nhiên thi gian thc hin ln và tiêu tn
11
nhiu tài nguyên máy tính. Ngc li, có nhng thut toán thit k và lp trình rt phc tp,
nhng cho thi gian chy nhanh hn, s dng tài nguyên máy tính hiu qu hn. Khi đó, câu hi
đt ra là ta nên la chn gii thut nào đ thc hin?
i vi nhng chng trình ch đc thc hin mt vài ln thì thi gian chy không phi là
tiêu chí quan trng nht. i vi bài toán ki
u này, thi gian đ lp trình viên xây dng và hoàn
thin thut toán đáng giá hn thi gian chy ca chng trình và nh vy nhng gii thut đn
gin v mt thit k và xây dng nên đc la chn.
i vi nhng chng trình đc thc hin nhiu ln thì thi gian chy ca chng trình
đáng giá hn rt nhiu so vi thi gian đc s dng
đ thit k và xây dng nó. Khi đó, la chn
mt gii thut có thi gian chy nhanh hn (cho dù vic thit k và xây dng phc tp hn) là mt
la chn cn thit. Trong thc t, trong giai đon đu ca vic gii quyt vn đ, mt gii thut
đn gin thng đc thc hin trc nh là 1 nguyên mu (prototype), sau đó nó s
đc phân
tích, đánh giá, và ci tin thành các phiên bn tt hn.
1.2.1 c lng thi gian thc hin chng trình
Thi gian chy ca 1 chng trình ph thuc vào các yu t sau:
- D liu đu vào
- Cht lng ca mã máy đc to ra bi chng trình dch
- Tc đ thc thi lnh ca máy
- phc tp v thi gian c
a thut toán
Thông thng, thi gian chy ca chng trình không ph thuc vào giá tr d liu đu vào
mà ph thuc vào kích thc ca d liu đu vào. Do vy thi gian chy ca chng trình nên
đc đnh ngha nh là mt hàm có tham s là kích thc d liu đu vào. Gi s T là hàm c
lng thi gian chy ca chng trình, khi đó vi d liu đu vào có kích thc n thì th
i gian
chy ca chng trình là T(n). Ví d, đi vi mt s chng trình thì thi gian chy là an hoc
an
2
,
trong đó a là hng s. n v ca hàm T(n) là không xác đnh, tuy nhiên ta có th xem nh
T(n) là tng s lnh đc thc hin trên 1 máy tính lý tng.
Trong nhiu chng trình, thi gian thc hin không ch ph thuc vào kích thc d liu
vào mà còn ph thuc vào tính cht ca nó. Khi tính cht d liu vào tho mãn mt s đc đim
nào đó thì thi gian thc hin chng trình có th là ln nht ho
c nh nht. Khi đó, ta đnh ngha
thi gian thc hin chng trình T(n) trong trng hp xu nht hoc tt nht. ó là thi gian
thc hin ln nht hoc nh nht trong tt c các b d liu vào có kích thc n. Ta cng đnh
ngha thi gian thc hin trung bình ca chng trình trên mi b d liu vào kích thc n. Trong
thc t, c l
ng thi gian thc hin trung bình khó hn nhiu so vi thi gian thc hin trong
trng hp xu nht hoc tt nht, bi vì vic phân tích thut toán trong trng hp trung bình
khó hn v mt toán hc, đng thi khái nim “trung bình” không có ý ngha thc s rõ ràng.
Yu t cht lng ca mã máy đc to bi chng trình dch và tc đ thc thi lnh ca
máy cng nh h
ng ti thi gian thc hin chng trình cho thy chúng ta không th th hin
thi gian thc hin chung trình di đn v thi gian chun, chng hn phút hoc giây. Thay vào
đó, ta có th phát biu thi gian thc hin chng trình t l vi n hoc n
2
v.v. H s ca t l là 1
hng s cha xác đnh, ph thuc vào máy tính, chng trình dch, và các nhân t khác.
Ký hiu O(n)
biu th cp đ tng ca hàm, ta s dng ký hiu O(n). Ví d, ta nói thi gian thc hin
T(n) ca chng trình là O(n
2
), có ngha là tn ti các hng s dung c và n
0
sao cho T(n) ≤ cn
2
vi n ≥ n
0
.
12
Ví d, xét hàm T(n) = (n+1)
2
.
Ta có th thy T(n) là O(n
2
) vi n
0
= 1 và c = 4, vì ta có T(n)
= (n+1)
2
< 4n
2
vi mi n ≥ 1. Trong ví d này, ta cng có th nói rng T(n) là O(n
3
), tuy nhiên,
phát biu này “yu” hn phát biu T(n) là O(n
2
).
Nhìn chung, ta nói T(n) là O(f(n)) nu tn ti các hng s dng c và n
0
sao cho T(n) <
c.f(n) vi n ≥ n
0
. Mt chng trình có thi gian thc hin là O(f(n)) thì đc xem là có cp đ
tng f(n).
Vic đánh giá các chng trình có th đc thc hin qua vic đánh giá các hàm thi gian
chy ca chng trình,b qua các hng s t l. Vi gi thit này, mt chng trình vi thi gian
thc hin là O(n
2
) s tt hn chng trình vi thi gian chy O(n
3
). Bên cnh các yu t hng s
xut phát t chng trình dch và máy, còn có thêm hng s t bn thân chung trình. Ví d, trên
cùng mt chng trình dch và cùng 1 máy, chng trình đu tiên có thi gian thc hin là 100n
2
,
trong khi chung trình th 2 có thi gian thc hin là 5n
3
. Vi n nh, có th 5n
3
nh hn 100n
2
,
tuy nhiên vi n đ ln thì 5n
3
s ln hn 100n
2
đáng k.
Mt lý do na đ xem xét cp đ tng v thi gian thc hin ca chng trình là nó cho
phép ta xác đnh đ ln ca bài toán mà ta có th gii quyt. Mc dù máy tính có tc đ ngày càng
cao, tuy nhiên, vi nhng chng trình có thi gian thc hin có cp đ tng ln (t n
2
tr lên),
thì vic tng tc đ ca máy tính to ra s khác bit không đáng k v kích thc bài toán có th
x lý bi máy tính trong mt khong thi gian c đnh.
1.2.2 Tính toán thi gian thc hin chng trình
tính toán đc thi gian thc hin chng trình, ta cn chú ý mt s nguyên tc cng và
nhân cp đ tng ca hàm nh sau :
Gi s T
1
(n) và T
2
(n) là thi gian chy ca 2 đon chng trình P
1
và P
2
, trong đó T
1
(n) là
O(f(n)) và T
2
(n) là O(g(n)). Khi đó, thi gian thc hin ca 2 đon chng trình trình ni tip P
1
,
P
2
là O(max(f(n), g(n))).
Nguyên tc cng trên có th s dng đ tính thi gian thc hin ca chng trình bao gm
1 s tun t các bc, mi bc có th là 1 đon chng trình bao gm 1 s vòng lp và r nhánh.
Ví d, gi s ta có 3 bc thc hin chng trình ln lt có thi gian chy là O(n
2
), O(n
3
),
O(nlog n). Khi đó, thi gian chy ca 2 đon chng trình đu là O(max(n
2
, n
3
)) = O(n
3
), còn thi
gian chy ca c 3 đon chng trình là O(max(n
3
, nlog n)) = O(n
3
).
Nguyên tc nhân cp đ tng ca hàm nh sau: Vi gi thit v T
1
(n) và T
2
(n) nh trên, nu
2 đon chng trình P
1
và P
2
không đc thc hin tun t mà lng nhau thì thi gian chy tng
th s là T
1
(n).T
2
(n) = O(f(n).(g(n)).
minh ho cho vic phân tích và tính toán thi gian thc hin ca 1 chng trình, ta s
xem xét mt thut toán đn gian đ sp xp các phn t ca mt tp hp, đó là thut toán sp xp
ni bt (bubble sort).
Thut toán nh sau :
void buble (int a[n]){
int i, j, temp;
1. for (i = 0; i < n-1; i++)
2. for (j = n-1; j>= i+1; j )
3. if (a[j-1] > a[j]{
// i ch cho a[j] và a[j-1]
4. temp = a[j-1];
5. a[j-1] = a[j];
13
6. a[j] = temp;
}
}
Trong thut toán này, mi ln duyt ca vòng lp trong (bin duyt j) s làm “ni” lên trên
phn t nh nht trong các phn t đc duyt.
D thy rng kích thc d liu vào chính là s phn t đc sp, n. Mi lnh gán s có
thi gian thc hin c đnh, không ph thuc vào n, do vy, các lnh 4, 5, 6 s có thi gian thc
hin là O(1), tc thi gian thc hi
n là hng s. Theo quy tc cng cp đ tng thì tng thi gian
thc hin c 3 lnh là O(max(1, 1, 1)) = O(1).
Tip theo ta s xem xét thi gian thc hin ca các lnh lp và r nhánh. Lnh If kim tra
điu kin đ thc hin nhóm lnh gán 4, 5, 6. Vic kim tra điu kin s có thi gian thc hin là
O(1). Ngoài ra, chúng ta cha bit đc là điu kin có tho mãn hay không, tc là không bi
t
đc nhóm lnh gán có đc thc hin hay không. Do vy, ta gi thit trng hp xu nht là tt
c các ln kim tra điu kin đu tho mãn, và các lnh gán đc thc hin. Nh vy, toàn b lnh
If s có thi gian thc hin là O(1).
Tip tc xét t trong ra ngoài, ta xét đn vòng lp trong (bin duyt j). Trong vòng lp này,
ti mi bc lp ta cn thc hi
n các thao tác nh kim tra đã gp điu kin dng cha và tng
bin duyt lên 1 nu cha dng. Nh vy, mi bc lp có thi gian thc hin là O(1). S bc
lp là n-i, do đó theo quy tc nhân cp đ tng thì tng thi gian thc hin ca vòng lp này là
O((n-i)x1) = O(n-i).
Cui cùng, ta xét vòng lp ngoài cùng (bin duyt i). Vòng lp này đc thc hin (n-1) ln,
do đó, t
ng thi gian thc hin ca chng trình là:
∑ (n-i) = n(n-1)/2 = n
2
/2- n/2 = O(n
2
)
Nh vy, thi gian thc hin gii thut sp xp ni bt là t l vi n
2
.
Mt s quy tc chung trong vic phân tích và tính toán thi gian thc hin chng trình
- Thi gian thc hin các lnh gán, đc, ghi .v.v, luôn là O(1).
- Thi gian thc hin chui tun t các lnh đc xác đnh theo quy tc cng cp đ tng.
Có ngha là thi gian thc hin ca c nhóm lnh tun t đc tính là thi gian thc
hin ca lnh ln nht.
- Th
i gian thc hin lnh r nhánh If đc tính bng thi gian thc hin các lnh khi
điu kin kim tra đc tho mãn và thi gian thc hin vic kim tra điu kin. Thi
gian thc hin vic kim tra điu kin luôn là O(1).
- Thi gian thc hin 1 vòng lp đc tính là tng thi gian thc hin các lnh thân
vòng lp qua tt c các bc l
p và thi gian đ kim tra điu kin dng (thng là
O(1)). Thi gian thc hin này thng đc tính theo quy tc nhân cp đ tng s ln
thc hin bc lp và thi gian thc hin các lnh thân vòng lp. Các vòng lp phi
đc tính thi gian thc hin mt cách riêng r.
1.3 TÓM TT CHNG 1
Các kin thc cn nh trong chng 1:
- Thut toán là mt chui hu hn các lnh. Mi lnh có mt ng ngha rõ ràng và có th
đc thc hin vi mt lng hu hn tài nguyên trong mt khong hu hn thi gian.
14
- Thut toán thng đc mô t bng các ngôn ng din đt gii thut gn vi ngôn ng
t nhiên. Các mô t này s đc tnh chnh dn dn đ đt ti mc ngôn ng lp trình.
- Thi gian thc hin thut toán thng đc coi nh là 1 hàm ca kích thc d liu đu
vào.
- Thi gian thc hin thut toán th
ng đc tính trong các trng hp tt nht, xu nht,
hoc trung bình.
- biu th cp đ tng ca hàm, ta s dng ký hiu O(n). Ví d, ta nói thi gian thc
hin T(n) ca chng trình là O(n
2
), có ngha là tn ti các hng s dung c và n
0
sao
cho T(n) ≤ cn
2
vi n ≥ n
0
.
- Cp đ tng v thi gian thc hin ca chng trình cho phép ta xác đnh đ ln ca bài
toán mà ta có th gii quyt.
- Quy tc cng cp đ tng: Gi s T
1
(n) và T
2
(n) là thi gian chy ca 2 đon chng
trình P
1
và P
2
, trong đó T
1
(n) là O(f(n)) và T
2
(n) là O(g(n)). Khi đó, thi gian thc hin
ca 2 đon chng trình trình ni tip P
1
, P
2
là O(max(f(n), g(n))).
- Quy tc nhân cp đ tng: Vi gi thit v T
1
(n) và T
2
(n) nh trên, nu 2 đon chng
trình P
1
và P
2
không đc thc hin tun t mà lng nhau thì thi gian chy tng th s
là T
1
(n).T
2
(n) = O(f(n).(g(n)).
1.4 CÂU HI VÀ BÀI TP
1. Trình bày khái nim thut toán? Các đc đim ca thut toán?
2. Trong mt gii vô đch bóng đá có 6 đi bóng đá vòng tròn. Các đi là A, B, C, D, E, F.
i A đã đá vi B và C. i B đã đá vi D và F. i E đã đá vi C và F. Mi đi đá
mi tun 1 trn. Hãy lp 1 lch cho các đi bóng sao cho tt c các đi đu đá đ s trn
quy đnh trong 1 s tun va phi. Thc hin phân tích, thit k thut toán. Biu din
thut toán bng ngôn ng din đt gii thut, sau đó tinh chnh v dng ngôn ng lp
trình C.
3. Thi gian thc hin mt chng trình thng ph thuc vào các yu t nào? Phân tích
c th tng yu t.
4. Nói thi gian thc hin chng trình là T(n) = O(f(n)) có ngha là gì? Cho ví d minh
ho.
5. Nêu quy tc cng và nhân cp đ tng ca hàm. Có ví d minh ho.
6. Nêu các quy tc chung trong vic phân tích và đánh giá thi gian thc hin chng
trình.
15
CHNG 2
QUI
Chng 2 trình bày các khái nim v đnh ngha đ qui, chng trình đ qui. Ngoài vic
trình bày các u đim ca chng trình đ qui, các tình hung không nên s dng đ qui cng
đc đ cp cùng vi các ví d minh ho.
Chng này cng đ cp và phân tích mt s thut toán đ qui tiêu biu và kinh đin nh
bài toán tháp Hà ni, các thut toán quay lui .v.v
hc tt chng này, sinh viên cn nm vng ph
n lý thuyt. Sau đó, nghiên cu k các
phân tích thut toán và thc hin chy th chng trình. Có th thay đi mt s đim trong
chng trình và chy th đ nm k hn v thut toán. Ngoài ra, sinh viên cng có th tìm các bài
toán tng t đ phân tích và gii quyt bng chng trình.
2.1 KHÁI NIM
qui là mt khái nim c bn trong toán hc và khoa hc máy tính. Mt đi tng đc
g
i là đ qui nu nó hoc mt phn ca nó đc đnh ngha thông qua khái nim v chính nó. Mt
s ví d đin hình v vic đnh ngha bng đ qui là:
1- nh ngha s t nhiên:
- 0 là s t nhiên.
- Nu k là s t nhiên thì k+1 cng là s t nhiên.
Nh vy, bt đu t phát biu “0 là s t nhiên”, ta suy ra 0+1=1 là s t nhiên. Ti
p
theo 1+1=2 là s t nhiên, v.v.
2- nh ngha xâu ký t bng đ qui:
- Xâu rng là 1 xâu ký t.
- Mt ch cái bt k ghép vi 1 xâu s to thành 1 xâu mi.
T phát biu “Xâu rng là 1 xâu ký t”, ta ghép bt k 1 ch cái nào vi xâu rng đu
to thành xâu ký t. Nh vy, ch cái bt k có th coi là xâu ký t. Tip tc ghép 1 ch
cái bt k vi 1 ch cái bt k
cng to thành 1 xâu ký t, v.v.
3- nh ngha hàm giai tha, n!.
- Khi n=0, đnh ngha 0!=1
- Khi n>0, đnh ngha n!=(n-1)! x n
Nh vy, khi n=1, ta có 1!=0!x1 = 1x1=1. Khi n=2, ta có 2!=1!x2=1x2=2, v.v.
Trong lnh vc lp trình, mt chng trình máy tính gi là đ qui nu trong chng trình có
li gi chính nó. iu này, thot tiên, nghe có v hi vô lý. Mt chng trình không th gi mãi
chính nó, vì nh vy s to ra mt vòng lp vô hn. Trên thc t, mt chng trình đ
qui trc
khi gi chính nó bao gi cng có mt thao tác kim tra điu kin dng. Nu điu kin dng tha
mãn, chng trình s không gi chính nó na, và quá trình đ qui chm dt. Trong các ví d
trên, ta đu thy có các đim dng. Chng hn, trong ví d th nht, nu k = 0 thì có th suy ngay
k là s t nhiên, không cn tham chiu xem k-1 có là s t nhiên hay không.
Nhìn chung, các chng trình đ qui đu có các đc đ
im sau:
16
- Chng trình này có th gi chính nó.
- Khi chng trình gi chính nó, mc đích là đ gii quyt 1 vn đ tng t, nhng nh
hn.
- Vn đ nh hn này, cho ti 1 lúc nào đó, s đn gin ti mc chng trình có th t
gii quyt đc mà không cn gi ti chính nó na.
Khi chng trình gi ti chính nó, các tham s, hoc kho
ng tham s, thng tr nên nh
hn, đ phn ánh 1 thc t là vn đ đã tr nên nh hn, d hn. Khi tham s gim ti mc cc
tiu, mt điu kin so sánh đc kim tra và chng trình kt thúc, chm dt vic gi ti chính
nó.
u đim ca chng trình đ qui cng nh đnh ngha bng đ qui là có th
thc hin mt
s lng ln các thao tác tính toán thông qua 1 đon chng trình ngn gn (thm chí không có
vòng lp, hoc không tng minh đ có th thc hin bng các vòng lp) hay có th đnh ngha
mt tp hp vô hn các đi tng thông qua mt s hu hn li phát biu. Thông thng, mt
chng trình đc vit di dng đ qui khi vn đ cn x
lý có th đc gii quyt bng đ qui.
Tc là vn đ cn gii quyt có th đa đc v vn đ tng t, nhng đn gin hn. Vn đ này
li đc đa v vn đ tng t nhng đn gin hn na .v.v, cho đn khi đn gin ti mc có
th trc tip gii quy
t đc ngay mà không cn đa v vn đ đn gin hn na.
2.1.1 iu kin đ có th vit mt chng trình đ qui
Nh đã nói trên, đ chng trình có th vit di dng đ qui thì vn đ cn x lý phi
đc gii quyt 1 cách đ qui. Ngoài ra, ngôn ng dùng đ vit chng trình phi h tr đ qui.
có th vi
t chng trình đ qui ch cn s dng ngôn ng lp trình có h tr hàm hoc th tc,
nh đó mt th tc hoc hàm có th có li gi đn chính th tc hoc hàm đó. Các ngôn ng lp
trình thông dng hin nay đu h tr k thut này, do vy vn đ công c đ to các chng trình
đ qui không phi là vn đ cn phi xem xét. Tuy nhiên, c
ng nên lu ý rng khi mt th tc đ
qui gi đn chính nó, mt bn sao ca tp các đi tng đc s dng trong th tc này nh các
bin, hng, các th tc con, .v.v. cng đc to ra. Do vy, nên hn ch vic khai báo và s dng
các đi tng này trong th tc đ qui nu không cn thit nhm tránh lãng phí b nh, đc bit
đi vi các l
i gi đ qui đc gi đi gi li nhiu ln. Các đi tng cc b ca 1 th tc đ qui
khi đc to ra nhiu ln, mc dù có cùng tên, nhng do khác phm vi nên không nh hng gì
đn chng trình. Các đi tng đó s đc gii phóng khi th tc cha nó kt thúc.
Nu trong mt th tc có li gi đn chính nó thì ta gi đó là đ qui tr
c tip. Còn trong
trng hp mt th tc có mt li gi th tc khác, th tc này li gi đn th tc ban đu thì
đc gi là đ qui gián tip. Nh vy, trong chng trình khi nhìn vào có th không thy ngay s
đ qui, nhng khi xem xét k hn thì s nhn ra.
2.1.2 Khi nào không nên s dng đ qui
Trong nhiu trng hp, mt chng trình có th vit di dng đ
qui. Tuy nhiên, đ qui
không hn đã là gii pháp tt nht cho vn đ. Nhìn chung, khi chng trình có th vit di dng
lp hoc các cu trúc lnh khác thì không nên s dng đ qui.
Lý do th nht là, nh đã nói trên, khi mt th tc đ qui gi chính nó, tp các đi tng
đc s dng trong th tc này nh các bin, hng, cu trúc .v.v s đc to ra. Ngoài ra, vic
chuyn giao đi
u khin t các th tc cng cn lu tr các thông s dùng cho vic tr li điu
khin cho th tc ban đu.
Lý do th hai là vic s dng đ qui đôi khi to ra các tính toán tha, không cn thit do
tính cht t đng gi thc hin th tc khi cha gp điu kin dng ca đ qui. minh ha cho
17
điu này, chúng ta s xem xét mt ví d, trong đó c đ qui và lp đu có th đc s dng. Tuy
nhiên, ta s phân tích đ thy s dng đ qui trong trng hp này gây lãng phí b nh và các tính
toán không cn thit nh th nào.
Xét bài toán tính các phn t ca dãy Fibonaci. Dãy Fibonaci đuc đnh ngha nh sau:
- F(0) = 0
- F(1) =1
- Vi n >1 thì F(n) = F(n-1) + F(n-2)
Rõ ràng là nhìn vào mt đnh ngha đ qui nh trên, ch
ng trình tính phn t ca dãy
Fibonaci có v nh rt phù hp vi thut toán đ qui. Phng thc đ qui đ tính dãy này có th
đc vit nh sau:
int Fibonaci(int i){
if (i==0) return 0;
if (i==1) return 1;
return Fibonaci(i-1) + Fibonaci (i-2)
}
Kt qu thc hin chng trình không có gì sai. Tuy nhiên, chú ý rng mt li gi đ qui
Fibonaci (n) s dn ti 2 li gi đ qui khác ng vi n-1 và n-2. Hai li gi này li gây ra 4 li gi
na .v.v, c nh vy s li gi đ qui s tng theo cp s m. iu này rõ ràng là không hiu qu
vì trong s các li gi đ qui đó có rt nhiu li g
i trùng nhau. Ví d li gi đ qui Fibonaci (6)
s dn đn 2 li gi Fibonaci (5) và Fibonaci (4). Li gi Fibonaci (5) s gi Fibonaci (4) và
Fibonaci (3). Ngay ch này, ta đã thy có 2 li gi Fibonaci (4) đc thc hin. Hình 2.1 cho thy
s các li gi đc thc hin khi gi th tc Fibonaci (6).
Hình 2.1 Các li gi đ qui đc thc hin khi gi th tc Fibonaci (6)
Trong hình v trên, ta th
y đ tính đc phn t th 6 thì cn có ti 25 li gi ! Sau đây, ta
s xem xét vic s dng vòng lp đ tính giá tr các phn t ca dãy Fibonaci nh th nào.
u tiên, ta khai báo mt mng F các s t nhiên đ cha các s Fibonaci. Vòng lp đ tính
và gán các s này vào mng rt đn gin nh sau:
F[0]=0;
F[1]=1;
for (i=2; i<n-1; i++)
6
5
4
3
3 2
2 1 1
0
1
0
2 1
1
0
4
3 2
2 1 1
0
1
0
18
F[i] = F[i-1] + F [i-2];
Rõ ràng là vi vòng lp này, mi s Fibonaci (n) ch đc tính 1 ln thay vì đc tính toán
chng chéo nh trên.
Tóm li, nên tránh s dng đ qui nu có mt gii pháp khác cho bài toán. Mc dù vy, mt
s bài toán t ra rt phù hp vi phng pháp đ qui. Vic s dng đ qui đ gii quyt các bài
toán này hiu qu và rt d hiu. Trên thc t, tt c các gii thut đ qui đu có th
đc đa v
dng lp (còn gi là “kh” đ qui). Tuy nhiên, điu này có th làm cho chng trình tr nên phc
tp, nht là khi phi thc hin các thao tác điu khin stack đ qui (bn đc có th tìm hiu thêm
k thut kh đ qui các tài liu tham kho khác), dn đn vic chng trình tr nên rt khó hiu.
Phn tip theo s trình bày mt s thut toán đ
qui đin hình.
2.2 THIT K GII THUT QUI
2.2.1 Chng trình tính hàm n!
Theo đnh ngha đã trình bày phn trc, n! = 1 nu n=0, ngc li, n! = (n-1)! * n.
int giaithua (int n){
if (n==0) return 1;
else return giaithua(n-1) * n;
}
Trong chng trình trên, đim dng ca thut toán đ qui là khi n=0. Khi đó, giá tr ca
hàm giaithua(0) có th tính đc ngay lp tc mà không cn gi hm đ qui khác. Nu điu kin
dng không tha mãn, s có mt li gi đ qui hàm giai tha vi tham s là n-1, nh hn tham s
ban đu 1 đn v (tc là bài toán tính n! đã đc qui v bài toán đn gin hn là tính (n-1)!).
2.2.2 Thut toán Euclid tính c s
chung ln nht ca 2 s nguyên dng
c s chung ln nht (USCLN) ca 2 s nguyên dng m, n là 1 s k ln nht sao cho m
và n đu chia ht cho k. Mt phng pháp đn gin nht đ tìm USCLN ca m và n là duyt t s
nh hn trong 2 s m, n cho đn 1, ngay khi gp s nào đó mà m và n đu chia ht cho nó thì đó
chính là USCLN ca m, n. Tuy nhiên, phng pháp này không phi là cách tìm USCLN hiu qu.
Cách đây hn 2000 nm, Euclid đã phát minh ra mt gi
i thut tìm USCLN ca 2 s nguyên
dng m, n rt hiu qu. Ý tng c bn ca thut toán này cng tng t nh ý tng đ qui, tc
là đa bài toán v 1 bài toán đn gin hn. C th, gi s m ln hn n, khi đó vic tính USCLN
ca m và n s đc đa v bài toán tính USCLN ca m mod n và n vì USCLN(m, n) = USCLN(m
mod n, n).
Thut toán đc cài đt nh sau:
int USCLN(int m, int n){
if (n==0) return m;
else return USCLN(n, m % n);
}
im dng ca thut toán là khi n=0. Khi đó đng nhiên là USCLN ca m và 0 chính là
m, vì 0 chia ht cho mi s. Khi n khác 0, li gi đ qui USCLN(n, m% n) đc thc hin. Chú ý
rng ta gi s m >= n trong th tc tính USCLN, do đó, khi gi đ qui ta gi USCLN (n, m% n)
đ đm bo th t các tham s vì n bao gi cng ln hn phn d ca phép m cho n. Sau mi ln
gi đ qui, các tham s ca th tc s nh d
n đi, và sau 1 s hu hn li gi tham s nh hn s
bng 0. ó chính là đim dng ca thut toán.
19
Ví d, đ tính USCLN ca 108 và 45, ta gi th tc USCLN(108, 45). Khi đó, các th tc
sau s ln lt đc gi:
USCLN(108, 45) 108 chia 45 d 18, do đó tip theo gi
USCLN(45, 18) 45 chia 18 d 9, do đó tip theo gi
USCLN(18, 9) 18 chia 9 d 0, do đó tip theo gi
USCLN(9, 0) tham s th 2 = 0, do đó kt qu là tham s th nht, tc là 9.
Nh vy, ta tìm đc USCLN ca 108 và 45 là 9 ch sau 4 ln gi th t
c.
2.2.3 Các gii thut đ qui dng chia đ tr (divide and conquer)
Ý tng c bn ca các thut toán dng chia đ tr là phân chia bài toán ban đu thành 2
hoc nhiu bài toán con có dng tng t và ln lt gii quyt tng bài toán con này. Các bài
toán con này đc coi là dng đn gin hn ca bài toán ban đu, do vy có th s dng các li
gi đ qui đ gii quyt. Thông thng, các thut toán chia đ tr chia b
d liu đu vào thành 2
phn riêng r, sau đó gi 2 th tc đ qui đ vi các b d liu đu vào là các phn va đc chia.
Mt ví d đin hình ca gii thut chia đ tr là Quicksort, mt gii thut sp xp nhanh. Ý
tng c bn ca gii thut này nh sau:
Gii s ta cn sp xp 1 dãy các s theo chiu tng d
n. Tin hành chia dãy đó thành 2 na
sao cho các s trong na đu đu nh hn các s trong na sau. Sau đó, tin hành thc hin sp
xp trên mi na này. Rõ ràng là sau khi mi na đã đc sp, ta tin hành ghép chúng li thì s
có toàn b dãy đc sp. Chi tit v gii thut Quicksort s đc trình bày trong chng 7 - Sp
xp và tìm kim.
Tip theo, chúng ta s xem xét mt bài toán cng rt đin hình cho l
p bài toán đc gii
bng gii thut đ qui chia đ tr.
Bài toán tháp Hà ni
Có 3 chic cc và mt b n chic đa. Các đa này có kích thc khác nhau và mi đa đu
có 1 l gia đ có th xuyên chúng vào các cc. Ban đu, tt c các đa đu nm trên 1 cc,
trong đó, đa nh hn bao gi cùng nm trên đa ln hn.
Hình 2.2 Bài toán tháp Hà n
i
Yêu cu ca bài toán là chuyn b n đa t cc ban đu A sang cc đích C (có th s dng
cc trung gian B), vi các điu kin:
- Mi ln chuyn 1 đa.
- Trong mi trng hp, đa có kích thc nh hn bao gi cng phi nm trên đa có
kích thc ln hn.
Vi n=1, có th thc hin yêu cu bài toán bng cách chuyn tr
c tip đa 1 t cc A sang
cc C.
Cc A
Cc B
Cc C
20
Vi n=2, có th thc hin nh sau:
- Chuyn đa nh t cc A sang cc trung gian B.
- Chuyn đa ln t cc A sang cc đích C.
- Cui cùng, chuyn đa nh t cc trung gian B sang cc đích C.
Nh vy, c 2 đa đã đc chuyn sang cc đích C và không có tình hung nào đa ln nm
trên đa nh.
Vi n > 2, gi
s ta đã có cách chuyn n-1 đa, ta thc hin nh sau:
- Ly cc đích C làm cc trung gian đ chuyn n-1 đa bên trên sang cc trung gian B.
- Chuyn cc di cùng (cc th n) sang cc đích C.
- Ly cc ban đu A làm cc trung gian đ chuyn n-1 đa t cc trung gian B sang cc
đích C.
Có th minh ha quá trình chuyn này nh sau:
Trng thái ban đu:
Bc 1:
Chuyn n-1 đa bên trên t cc A sang cc B, s dng cc C làm cc trung gian.
Bc 2:
Chuyn đa di cùng t cc A thng sang cc C.
Bc 3:
Chuyn n-1 đa t cc B sang cc C s dng cc A làm cc trung gian.
Cc A
Cc B
Cc C
Cc A
Cc B
Cc C
Cc A
Cc B
Cc C
21
Nh vy, ta thy toàn b n đa đã đc chuyn t cc A sang cc C và không vi phm bt
c điu kin nào ca bài toán.
đây, ta thy rng bài toán chuyn n cc đã đc chuyn v bài toán đn gin hn là
chuyn n-1 cc. im dng ca thut toán đ qui là khi n=1 và ta chuyn thng cc này t cc
ban
đu sang cc đích.
Tính cht chia đ tr ca thut toán này th hin ch: Bài toán chuyn n đa đc chia làm
2 bài toán nh hn là chuyn n-1 đa. Ln th nht chuyn n-1 đa t cc a sang cc trung gian b,
và ln th 2 chuyn n-1 đa t cc trung gian b sang cc đích c.
Cài đt đ qui cho thut toán nh sau:
- Hàm chuyen(int n, int a, int c) thc hin vic chuyn đa th n t cc a sang c
c c.
- Hàm thaphanoi(int n, int a, int c, int b) là hàm đ qui thc hin vic chuyn n đa t cc
a sang cc c, s dng cc trung gian là cc b.
Chng trình nh sau:
void chuyen(int n, char a, char c){
printf(‘Chuyen dia thu %d tu coc %c sang coc %c
\n”,n,a,c);
return;
}
void thaphanoi(int n, char a, char c, char b){
if (n==1) chuyen(1, a, c);
else{
thaphanoi(n-1, a, b, c);
chuyen(n, a, c);
thaphanoi(n-1, b, c,a);
}
return;
}
Hàm chuyen thc hin thao tác in ra 1 dòng cho bit chuyn đa th my t cc nào sang
cc nào.
Hàm thaphanoi kim tra nu s đa bng 1 thì thc hin chuyn trc tip đa t cc a sang
cc c. Nu s đa ln hn 1, có 3 lnh đc thc hin:
1- Li gi đ qui thaphanoi(n-1, a, b, c) đ chuyn n-1 đa t cc a sang cc b, s dng cc
c làm cc trung gian.
2-
Thc hin chuyn đa th n t cc a sang cc c.
Cc A
Cc B
Cc C
22
3- Li gi đ qui thaphanoi(n-1, b, c, a) đ chuyn n-1 đa t cc b sang cc c, s dng cc
a làm cc trung gian.
Khi chy chng trình vi s đa là 4, ta có kt qu nh sau:
Hình 2.3 Kt qu chy chung trình tháp Hà ni vi 4 đa
phc tp ca thut toán là 2
n
-1. Ngha là đ chuyn n cc thì mt 2
n
-1 thao tác chuyn.
Ta s chng minh điu này bng phng pháp qui np toán hc:
Vi n=1 thì s ln chuyn là 1 = 2
1
-1.
Gi s gi thit đúng vi n-1, tc là đ chuyn n-1 đa cn thc hin 2
n-1
-1 thao tác chuyn.
Ta s chng minh rng đ chuyn n đa cn 2
n
–1 thao tác chuyn.
Tht vy, theo phng pháp chuyn ca gii thut thì có 3 bc. Bc 1 chuyn n-1 đa t
cc a sang cc b mt 2
n-1
-1 thao tác. Bc 2 chuyn 1 đa t cc a sang cc c mt 1 thao tác. Bc
3 chuyn n-1 đa t cc b sang cc c mt 2
n-1
-1 thao tác. Tng cng ta mt (2
n-1
-1) + (2
n-1
-1) + 1 =
2*2
n-1
-1 = 2
n
–1 thao tác chuyn. ó là điu cn chng minh.
Nh vy, thut toán có cp đ tng rt ln. Nói v cp đ tng này, có mt truyn thuyt vui
v bài toán tháp Hà ni nh sau: Ngày tn th s đn khi các nhà s mt ngôi chùa thc hin
xong vic chuyn 40 chic đa theo quy tc nh bài toán va trình bày. Vi đ phc tp ca bài
toàn va tính đc, nu gi
s mi ln chuyn 1 đa t cc này sang cc khác mt 1 giây thì vi
2
40
-1 ln chuyn, các nhà s này phi mt ít nht 34.800 nm thì mi có th chuyn xong toàn b
s đa này !
Di đây là toàn b mã ngun chng trình tháp Hà ni vit bng C:
#include<stdio.h>
#include<conio.h>
void chuyen(int n, char a, char c);
void thaphanoi(int n, char a, char c, char b);
23
void chuyen(int n, char a, char c){
printf("Chuyen dia thu %d tu coc %c sang coc %c \n", n,
a, c);
return;
}
void thaphanoi(int n, char a, char c, char b){
if (n==1) chuyen(1, a, c);
else{
thaphanoi(n-1, a, b, c);
chuyen(n, a, c);
thaphanoi(n-1, b, c,a);
}
return;
}
void main(){
int sodia;
clrscr();
printf("Cho biet so dia can chuyen: ");
scanf("%d",&sodia);
printf("\nCac buoc chuyen nhu sau:\n\n");
thaphanoi(sodia, 'a', 'c', 'b');
getch();
return;
}
2.2.4 Thut toán quay lui (backtracking algorithms)
Nh chúng ta đã bit, các thut toán đc xây dng đ giái quyt vn đ thng đa ra 1
quy tc tính toán nào đó. Tuy nhiên, có nhng vn đ không tuân theo 1 quy tc, và khi đó ta phi
dùng phng pháp th - sai (trial-and-error) đ gii quyt. Theo phng pháp này, quá trình th -
sai đc xem xét trên các bài toán đn gin hn (thng ch là 1 phn ca bài toán ban đu). Các
bài toán này thng đc mô t di dng đ qui và thng liên quan đn vic gi
i quyt mt s
hu hn các bài toán con.
hiu rõ hn thut toán này, chúng ta s xem xét 1 ví d đin hình cho thut toán quay
lui, đó là bài toán Mã đi tun.
Cho bàn c có kích thc n x n (có n
2
ô). Mt quân mã đc đt ti ô ban đu có to đ x
0
, y
0
và đc phép dch chuyn theo lut c thông thng. Bài toán đt ra là t ô ban đu, tìm mt chui
các nc đi ca quân mã, sao cho quân mã này đi qua tt c các ô ca bàn c, mi ô đúng 1 ln.
Nh đã nói trên, quá trình th - sai ban đu đc xem xét mc đn gin hn. C th,
trong bài toán này, thay vì xem xét vic tìm kim chui nc đi ph khp bàn c, ta xem xét vn
đ đn gin hn là tìm ki
m nc đi tip theo ca quân mã, hoc kt lun rng không còn nc đi
k tip tha mãn. Ti mi bc, nu có th tìm kim đc 1 nc đi k tip, ta tin hành ghi li
nc đi này cùng vi chui các nc đi trc đó và tip tc quá trình tìm kim nc đi. Nu ti
bc nào đó, không th tìm nc đi k tip th
a mãn yêu cu ca bài toán, ta quay tr li bc
24
trc, hy b nc đi đã lu li trc đó và th sang 1 nc đi mi. Quá trình có th phi th ri
quay li nhiu ln, cho ti khi tìm ra gii pháp hoc đã th ht các phng án mà không tìm ra
gii pháp.
Quá trình trên có th đc mô t bng hàm sau:
void ThuNuocTiepTheo;
{
Khi to danh sách các nc đi k tip;
do{
La chn 1 nc đi k ti
p t danh sách;
if Chp nhn đc
{
Ghi li nc đi;
if Bàn c còn ô trng
{
ThuNuocTiepTheo;
if Nc đi không thành công
Hy b nc đi đã lu bc trc
}
}
}while (nc đi không thành công) && (vn còn nc đi)
}
th hin hàm 1 cách c th hn qua ngôn ng C, trc ht ta phi đnh ngha các cu
trúc d liu và các bin dùng cho quá trình x lý.
u tiên, ta s d
ng 1 mng 2 chiu đ mô t bàn c:
int Banco[n][n];
Các phn t ca mng này có kiu d liu s nguyên. Mi phn t ca mng đi din cho 1
ô ca bàn c. Ch s ca phn t tng ng vi ta đ ca ô, chng hn phn t Banco[0][0]
tng ng vi ô (0,0) ca bàn c. Giá tr ca phn t cho bit ô đ
ó đã đc quân mã đi qua hay
cha. Nu giá tr ô = 0 tc là quân mã cha đi qua, ngc li ô đã đc quân mã đã đi qua.
Banco[x][y] = 0: ô (x,y) cha đc quân mã đi qua
Banco[x][y] = i: ô (x,y) đã đc quân mã đi qua ti nc th i.
Tip theo, ta cn phi thit lp thêm 1 s tham s. xác đnh danh sách các nc đi k
tip, ta cn ch ra ta đ hin ti ca quân mã, t đó theo lut c
thông thng ta xác đnh các ô
quân mã có th đi ti. Nh vy, cn có 2 bin x, y đ biu th ta đ hin ti ca quân mã. cho
bit nc đi có thành công hay không, ta cn dùng 1 bin kiu boolean.
Nc đi k tip chp nhn đc nu nó cha đc quân mã đi qua, tc là nu ô (u,v) đc
chn là nc đi k tip thì Banco[u][v] = 0 là điu kin đ chp nh
n. Ngoài ra, hin nhiên là ô đó
phi nm trong bàn c nên 0 ≤ u, v < n.
Vic ghi li nc đi tc là đánh du rng ô đó đã đc quân mã đi qua. Tuy nhiên, ta cng
cn bit là quân mã đi qua ô đó ti nc đi th my. Nh vy, ta cn 1 bin i đ cho bit hin ti
đang th nc đi th my, và ghi li nc đi thành công bng cách gán giá tr Banco[u][v]=i.
25
Do i tng lên theo tng bc th, nên ta có th kim tra xem bàn c còn ô trng không bng
cách kim tra xem i đã bng n
2
cha. Nu i<n
2
tc là bàn c vn còn ô trng.
bit nc đi có thành công hay không, ta có th kim tra bin boolean nh đã nói trên.
Khi nc đi không thành công, ta tin hành hy nc đi đã lu bc trc bng cách cho giá tr
Banco[u][v] = 0.
Nh vy, ta có th mô t c th hn hàm trên nh sau:
void ThuNuocTiepTheo(int i, int x, int y, int *q)
{
int u, v, *q1;
Khi to danh sách các nc đi k tip;
do{
*q1=0;
Chn nc đi (u,v) trong danh sách n
c đi k tip;
if ((0 <= u) && (u<n) && (0 <= v) && (v<n) && (Banco[u][v]==0))
{
Banco[u][v]=i;
if (i<n*n)
{
ThuNuocTiepTheo(i+1, u, v, q1)
if (*q1==0) Banco[u][v]=0;
} else *q1=1;
}
}while ((*q1==0) && (Vn còn nc đi))
*q=*q1;
}
Trong đon chng trình trên vn còn 1 thao tác cha đc th hin bng ngôn ng lp
trình, đó là thao tác khi to và chn nc đi k tip. Bây gi, ta s xem xét xem t ô (x,y), quân
mã có th đi ti các ô nào, và cách tính v trí tng đi ca các ô đó so vi ô (x,y) ra sao.
Theo lut c thông thng, quân mã t ô (x,y) có th
đi ti 8 ô trên bàn c nh trong hình v:
3 2
4 1
5 8
6 7
Hình 2.4 Các nc đi ca quân mã
x
y
