Các thuật toán cơ bản về xử lý mạng trong Pascal
Các phương pháp sắp xếp sẽ được phát triển, được mô tả, được so sánh với nhau. Các thuật toán cho nhiều vấn đề có liên quan sẽ được xem xét gồm có hàng đợi ưu tiên, phép chọn và phép trộn. Một vài nền tảng trong số này được dùng như là nền tảng cho các thuật toán khác tiếp sau trong phần này.
S¬ lîc vÒ c¸c chñ ®Ò
Sau ®©y lµ s¬ lîc vÒ c¸c chñ ®Ò sÏ ®îc ®Ò cËp trong phÇn nµy cña
ch¬ng tr×nh:
+ PhÇn c¬ së: lµ c¸c c«ng cô vµ ph¬ng ph¸p ®îc dïng xuyªn suèt cho tÊt
c¶ c¸c ch¬ng sau cña phÇn nµy. Nã gåm mét phÇn bµn luËn ng¾n vÒ
Pascal, theo sau lµ giíi thiÖu vÒ c¸c cÊu tróc d÷ liÖu c¬ b¶n gåm
m¶ng, x©u liªn kÕt, ng¨n xÕp, hµng ®îi vµ c©y. Chóng ta sÏ bµn luËn
vÒ c«ng dông thùc tiÔn ®Ö quy vµ b¾t ®Çu híng tíi viÖc ph©n tÝch
vµ tiÕp cËn thùc to¸n.
+ S¾p xÕp: C¸c ph¬ng ph¸p s¾p xÕp sÏ ®îc ph¸t triÓn, ®îc m« t¶, ®îc
so s¸nh víi nhau. C¸c thuËt to¸n cho nhiÒu vÊn ®Ò cã liªn quan sÏ ®îc
xem xÐt gåm cã hµng ®îi u tiªn, phÐp chän vµ phÐp trén. Mét vµi nÒn
t¶ng trong sè nµy ®îc dïng nh lµ nÒn t¶ng cho c¸c thuËt to¸n kh¸c tiÕp
sau trong phÇn nµy.
+ Xö lý chuçi: gåm mét lo¹t c¸c ph¬ng ph¸p ®Ó ph©n tÝch c©u. C¸c ky
thuËt nÐn tËp vµ mËt m· còng sÏ ®îc kh¶o s¸t. Còng vËy, mét giíi
thiÖu vÒ c¸c chñ ®Ò n©ng cao cïng ®îc cung cÊp qua viÖc xem xÐt
mét vµi bµi to¸n c¬ b¶n quan träng trong ph¹m vi cña chóng.
+ H×nh häc: lµ mét sù tËp hîp cã chän läc c¸c ph¬ng ph¸p ®Ó gi¶i
quyÕt c¸c bµi to¸n liªn quan ®Õn ®iÓm vµ ®êng ( vµ c¸c ®èi t îng h×nh
häc ®¬n gi¶n kh¸c ). Chóng ta sÏ xem xÐt c¸c thuËt to¸n ®Ó t×m bao
låi cña mét tËp ®iÓm, phÇn giao cña c¸c ®èi t îng, ®Ó gi¶i bµi to¸n
®iÓm gÇn nhÊt, t×m kiÕm nhiÒu chiÒu ...
+ §å thÞ: Mét chiÕn lîc tæng qu¸t ®Ó t×m kiÕm trªn c¸c ®å thÞ sÏ ®îc
ph¸t triÓn vµ ®îc ¸p dông cho c¸c bµi to¸n liªn th«ng c¬ b¶n, gåm cã ®-
êng ®i ng¾n nhÊt, c©y liªn th«ng tèi thiÓu, m¹ng vµ so khíp. Mét sù
xem xÐt thèng nhÊt ®èi víi c¸c thuËt to¸n nµy chøng tá r»ng tÊt c¶
®Òu dùa vµo mét thñ tôc vµ thñ tôc nµy phô thuéc vµo mét cÊu tróc d÷
liÖu c¬ b¶n ®· ph¸t triÓn tr íc ®ã.
+ C¸c thuËt to¸n to¸n häc: gåm c¸c ph¬ng ph¸p c¬ b¶n tõ sè häc vµ c¸c
sè nguyªn, ®a thøc, vµ ma trËn còng nh c¸c thuËt to¸n ®Ó gi¶i quyÕt
cac vÊn ®Ò to¸n häc mµ nã ph¸t sinh trong nhiÒu ng÷ c¶nh : viÖc t¹o
sè ngÉu nhiªn, lìi gi¶i cña c¸c ch¬ng tr×nh ®ång thêi, xÊp xØ d÷ liÖu,
1
vµ lÊy tÝch ph©n. Sù nhÊn m¹nh thiªn vÒ c¸c khÝa c¹nh thuËt to¸n
cña ph¬ng ph¸p, chø kh«ng ph¶i trªn nÒn t¶ng cña to¸n häc
+ C¸c chñ ®Ò cao cÊp: ®îc th¶o luËn nh»m môc ®Ých liªn hÖ c¸c chñ
®Ò trong tËp s¸ch nµy víi nhiÒu lÜnh vùc nghiªn cøu cao cÊp kh¸c.
PhÇn cøng chuyªn dông, quy ho¹ch ®éng, quy ho¹ch tuyÕn tÝnh, t×m
kiÕm- vÐt c¹n ...
I. Sắp xếp:
1. Kh¸i niÖm:
a) S¾p xÕp lµ mét qu¸ tr×nh tæ chøc l¹i mét d·y c¸c d÷ liÖu theo
mét trËt tù nhÊt ®Þnh.
b) Môc ®Ých cña viÖc s¾p xÕp lµ nh»m gióp cho viÖc t×m kiÕm
d÷ liÖu mét c¸ch dÔ dµng vµ nhanh chãng. S¾p xÕp lµ mét viÖc lµm
hÕt søc c¬ b¶n vµ ®îc dïng réng r·i trong c¸c kÜ thuËt lËp tr×nh nh»m
sö lý d÷ liÖu.
c) C¸c gi¶i thuËt s¾p xÕp ®îc ph©n chia thµnh hai nhãm chÝnh
lµ:
- S¾p xÕp trong (hay s¾p xÕp m¶ng).
Toµn bé c¬ së d÷ liÖu cÇn s¾p xÕp ph¶i ®îc ®a vµo bé nhí chÝnh cña
m¸y tÝnh. Do ®ã nã th êng ®îc sö dông khi khèi lîng d÷ liÖu kh«ng vît
qu¸ dung lîng bé nhí chÝnh.
Nhãm s¾p xÕp trong bao gåm c¸c ph¬ng ph¸p :
* Ph¬ng ph¸p ®Õm.
* Ph¬ng ph¸p chÌn.
* Ph¬ng ph¸p chän.
* Ph¬ng ph¸p ®æi chæ.
* Ph¬ng ph¸p trén.
- S¾p xÕp ngoµi (hay s¾p xÕp tËp tin).
VËn dông trong tr êng hîp ta ph¶i s¾p xÕp c¸c tËp tin chøa nhiÒu
mÉu tin vµ mçi mÉu tin cã chiÒu dµi t ¬ng ®èi lín do ®ã ta kh«ng thÓ
n¹p toµn bé vµo bé nhí chÝnh ®Ó s¾p xÕp thø tù. V× vËy ta ph¶i cã
nh÷ng ph¬ng ph¸p thÝch hîp cho viÖc s¾p xÕp tËp tin.
2. S¾p xÕp trong:
a) Kh¸i niÖm:
2
CÊu tróc d÷ liÖu thÝch hîp cho c¸c phÇn tö cÇn s¾p xÕp thø tù
lµ Record. Mçi phÇn tö cã hai vïng ®Æc tr ¬ng lµ: Vïng Key ®Ó chøa
kho¸ cña phÇn tö vµ ®îc sö dông trong c¸c gi¶i thuËt t×m kiÕm, vïng
info dïng ®Ó chøa ®÷ liÖu c¸c phÇn tö.
Ta khai b¸o :
Type
Item = Record
key : Integer;
Info : Integer;
End;
Var
A : Array[1..n] of Item;
Kho¸ cña phÇn tö cã thÓ lµ ch÷ hoÆc sè.
Yªu cÇu gi¶i thÝch lµ dïng Ýt vïng nhí vµ thêi gian thùc hiÖn nhanh.
b) Ph¬ng ph¸p ®Õm (Counting sort)
* Gi¶i thÝch:
Néi dung cña ph¬ng ph¸p nµy lµ ®Õm c¸c phÇn tö cã kho¸ nhá h¬n
hay b»ng kho¸ cña c¸c phÇn tö A[i]. NÕu cã j phÇn tö cã kho¸ nhá h¬n
kho¸ cña phÇn tö A[i] th× phÇn tö A[i] sÏ cã vÞ trÝ theo thø tù (j+1)
trong d·y ®· cã thø tù.
Trong gi¶i thuËt, ta dïng m¶ng Count[i] ( i = 1, 2, .. n ) víi Count[i]
cho biÕt sè phÇn tö cã kho¸ nhá h¬n kho¸ cña phÇn tö A[i]. Nh vËy
Count[i+1] lµ vÞ trÝ cña phÇn tö A[i] trong d·y ®· cã thø tù.
* VÝ dô:
S¾p xÕp d·y 2 3 1 5 2 7 6 9 4
i: 1 2 3 4 5 6 7 8
Count: 20416573
Nh vËy phÇn tö cã kho¸ 9 ë vÞ trÝ 8 v× Count[9]=7.
* ThÓ hiÖn b»ng Pascal:
Procedure Count_Sort;
Var
Count : Array[1..n] of Integer;
A : Array[1..n] of Item;
i,j : Integer;
Begin
3
For i := 1 to n do Count[i] := 0;
For i := n downto 2 do
For j := i-1 downto 1 do
If A[i].Key < A[j].Key Then
Count[j] := Count[j] + 1
Else Count[i] := Count[i] + 1;
For i := 1 to n do S[Count[i] + 1] := A[i];
For i := 1 to n do A[i] := S[i];
End;
c) Ph¬ng ph¸p chÌn (Insertion Sort)
* Gi¶i thÝch:
Néi dung cña ph¬ng ph¸p nµy lµ gi¶ sö ta cã d·y A[1]..A[i-1] ®· cã thø
tù, cã ph¶i x¸c ®Þnh vÞ trÝ thÝch hîp cña phÇn tö A[i] trong d·y
A[1]..A[i - 1] b»ng ph¬ng ph¸p t×m kiÕm tuÇn tù tõ A[i - 1] trë vÒ A[1]
®Ó t×m ra vÞ trÝ thÝch hîp cña A[i]. Ta chÌn A[i] vµo vÞ trÝ nµy vµ
kÕt qu¶ lµ ®·y A[1] .. A[i] cã thø tù. Ta ¸p dông c¸ch lµm nµy víi i = 2,
3, ..., n.
* VÝ dô:
Ta ph¶i s¾p xÕp d·y sè:
39 50 7 37 89 13 1 62
i=2 39 50 7 37 89 13 1 62
i=3 39 50 7 37 89 13 1 62
i=4 7 39 50 37 89 13 1 62
i=5 7 37 39 50 89 13 1 62
i=6 7 37 39 50 89 13 1 62
i=7 7 13 37 39 50 89 1 62
i=8 1 7 13 37 39 50 89 62
1 7 13 37 39 50 89 62
* ThÓ hiÖn b»ng Pascal:
Procedure Insertion_Sort;
Var
x : Item;
i,j : Integer;
Begin
For i := 2 to n do
4
Begin
x := A[i];
A[0] := x;
j := j - 1;
While x.Key < A[j].Key do
Begin
A[j+1] := A[j];
j := j - 1;
End;
A[j+1] := x;
End;
End;
d) Ph¬ng ph¸p chän (Selection Sort)
* Gi¶i thÝch:
Néi dung cña ph¬ng ph¸p nµy lµ ë bíc thø i (i = 1, 2, 3, ..., n-1 ) ta lùa
chän phÇn tö nhá nhÊt trong d·y A[i]..A[n] råi ®æi chæ phÇn tö nµy
víi phÇn tö A[i]. Cuèi cïng ta sÏ cã d·y A[1]..A[n] cã thø tù.
* VÝ dô:
Ta ph¶i s¾p xÕp d·y sè :
39 50 7 37 89 13 1 62
i=1 39 50 7 37 89 13 1 62
i=2 1 50 7 37 89 13 39 62
i=3 1 7 50 37 89 13 39 62
i=4 1 7 13 37 89 50 39 62
i=5 1 7 13 37 89 50 39 62
i=6 1 7 13 37 50 50 39 62
i=7 1 7 13 37 39 50 89 62
1 7 13 37 39 50 89 62
* ThÓ hiÖn b»ng Pascal:
Procedure Selection_Sort;
Var
x : Item;
i,j ,k : Integer;
min : Integer;
Begin
5
For i := 2 to n-1 do
Begin
min := A[i].Key;
k := i;
For i := 1 to n-1 do
For j := i+1 to n do
If A[j].Key < min Then
Begin
min := A[j].Key;
k := j;
End;
x := A[k];
A[k] := A[i];
A[i] := x;
End;
End;
e) Ph¬ng ph¸p ®æi chç:
Cã rÊt nhiÒu ph¬ng ph¸p s¾p xÕp dùa trªn viÖc ®æi chç gi÷a 2 phÇn
tö cña d·y. Sau ®©y chóng ta xÐt c¸c ph¬ng ph¸p:
- Bubble Sort.
- Shake Sort.
- Sell Sort.
- Quick Sort.
* Bubble Sort:
* Gi¶i thÝch:
Néi dung cña ph¬ng ph¸p nµy lµ duyÖt c¸c d·y A[1], ..., A[n]. NÕu
A[i].Key > A[i+1].Key (i = 1, 2, 3, ..., n-1)#0 th× ta ®æi chç A[i].Key víi
phÇn tö A[i+1].Key. LËp l¹i qu¸ tr×nh duyÖt d·y nµy cho ®Õn khi
kh«ng cßn viÖc ®æi chæ cña hai phÇn tö.
Chó ý r»ng bÊt cø lóc nµo phÇn tö nhá nhÊt còng gÆp tr íc tiªn. Nã
nh nh÷ng bét khÝ nhÑ sÏ næi lªn trªn khi ®un níc. Sau ®ã ë thø hai
phÇn tö nhá thø 2 sÏ ®îc ®Æ vµo ®óng mét vÞ trÝ. V× vËy s¾p xÕp
næi bét thao t¸c nh mét kiÓu s¾p xÕp chän, mÆc dï nã kh«ng lµm
nhiÒu viÖc h¬n ®Ó ®a tõng phÇn tö vµo ®óng vÞ trÝ.
6
* VÝ dô:
Ta ph¶i s¾p xÕp d·y sè:
39 50 7 37 89 13 1 62
Bíc 0 1 2 3 4 5 6 7
50 1 1 1 1 13 1 62
39 39 7 7 7 7 7 7
7 50 39 13 13 13 13 13
37 7 50 39 37 37 37 37
89 37 13 50 39 39 39 39
13 89 37 37 50 50 50 50
1 13 89 62 62 62 62 62
62 62 62 89 89 89 89 89
* ThÓ hiÖn b»ng Pascal:
Procedure Bubble_Sort;
Var
x : Item;
i,j : Integer;
Begin
For i := 2 to n do
For j := n downto i do
If A[j-1].Key > A[j].Key Then
Begin
x := A[j-1];
A[j-1] := A[j];
A[j-1] := x;
End;
End;
* C¶i tiÕn:
Ta nhËn thÊy r»ng nÕu ë mét lÇn duyÖt d·y nµo ®ã mµ kh«ng co s
xÈy ra sù ®æi chæ gi÷a hai phÇn tö th× d·y dang s¾p ®· cã thø tù vµ
gi¶i thuËt kÕt thóc.
Ta cã thÓ cµi ®Æt cê ®Ó ghi nhËn ®iÒu nµy vµ cã ch¬ng tr×nh sau:
Procedure Bubble_Sort2;
Var
7
x : Item;
i : Integer;
flag : Boolean;
Begin
flag := true;
While flag do
Begin
flag := False;
For i := 1 to n-1 do
If A[i].Key > A[i+1].Key Then
Begin
x := A[i];
A[i] := A[i+1];
A[i+1] := x;
End;
End;
End;
f* Shake Sort:
* Gi¶i thÝch:
Ph¬ng ph¸p nµy lµ mét c¶i tiÕn cña ph¬ng ph¸p Bubble Sort theo h-
íng "Kh«ng nh÷ng phÇn tö nhÑ næi lªn trªn mµ c¶ phÇn tö nÆng còng
xuèng díi" gièng nh khi ta rung"rung" mét c¸i nåi vµ thuËt to¸n s¾p
xÕp ph¶i ®îc ®iÒu khiÓn c¶ hai qu¸ tr×nh "næi lªn" vµ "ch×m xuèng"
nµy mét c¸ch tù gi¸c. Muèn vËy ta ph¶i ghi nhí lÇn ®æi chæ cuèi cïng
khi duyÖt d·y tõ trªn lªn vµ khi duyÖt tõ trªn xuoãng ®Ó quyÕt ®Þnh
chu tr×nh kÕ tiÕp sÏ duyÖt tõ ®©u ®Õn ®©u.
* VÝ dô:
S¾p xÕp d·y sè:
39 50 7 37 89 13 1 62
d= 2 3 3 4 4
c= 8 8 7 7 4
39 1 1 1 1
50 39 39 7 7
7 50 7 39 13
8
37 7 37 13 37
89 37 50 37 39
13 89 13 50 50
1 13 62 62 62
62 62 89 89 89
* ThÓ hiÖn b»ng Pascal:
Procedure Shake_Sort;
Var
x : Item;
i,k,d,c : Integer;
Begin
d := 2;
c := n;
k := n;
Repeat
For i := c downto d do
If A[i-1].Key > A[i].Key Then
Begin
x := A[i-1];
A[i-1] := A[i];
A[i-1] := x;
k := i;
End;
d := d + 1;
For i := d to c do
If A[i-1].Key > A[i].Key Then
Begin
x := A[i-1];
A[i-1] := A[i];
A[i-1] := x;
k := i;
End;
c := k-1;
Until d>c;
End;
9
g. * Shell Sort:
* Gi¶i thÝch:
C¸c ph¬ng ph¸p s¾p xÕp d· tr×nh bµy ë trªn nãi chung ®Òu di
chuyÓn mçi phÇn tö ®i mét vÞ trÝ trong mçi bíc. Ph¬ng ph¸p Shell
Sort dùa trªn ý t ëng chÝnh lµ ho¸n c¸c phÇn tö ë xa nhau. §Ó lµm ®îc
viÖc ®ã ta cÇn ph¶i s¾p c¸c tËp tin ®Ó nã cã tÝnh chÊt lµ viÖc lÊy
mäi phÇn tö thø h (b¾t ®Çu tõ vÞ trÝ bÊt k× nµo) còng ®Òu cho ra
tËp tin ®· s¾p. Mét tËp tin nh vËy ®îc gäi lµ s¾p theo ®é dµi bíc h.
Mét c¸ch nãi kh¸c, mét tËp tin dîc s¾p theo ®é dµi bíc h lµ tËp tin ®îc
s¾p ®éc lËp víi nhau, ®an xen vµo nhau. B»ng c¸ch s¾p xÕp theo ®é
dµi bíc h øng víi vµi gi¸ trÞ h kh¸ lín, chóng ta cã thÓ di chuyÓn c¸c
phÇn tö ë nh÷ng kho¶ng c¸ch xa nhau trong m¶ng vµ v× vËy dÔ dµng
h¬n ®Ó s¾p xÕp ®é dµi bíc h c¸c gi¸ tri nhá h¬n. Dïng thñ tôc cho bÊt
k× mét d·y c¸c gi¸ trÞ cña h tËn cïng lµ 1 sÏ cho ra mét tËp tin ®· s¾p
xong: Dã chÝnh lµ Shell Sort.
* VÝ dô:
Ta ph¶i s¾p xÕp d·y sè:
39 50 7 39 89 13 1 62
Bíc 1: 4-Sort
39 50 7 39 89 13 1 62
39 13 1 37 89 50 7 62
Bíc 2: 2-Sort
39 13 1 37 89 50 7 62
1 13 7 37 39 50 89 62
Bíc 3: 1-Sort
1 13 7 37 39 50 89 62
1 7 13 37 39 50 89 62
* ThÓ hiÖn b»ng Pascal:
Chó ý:
- Ta dïng d·y phô chøa dé t¨ng h[i], ..., h[t] ®Ó ®iÒu khiÓn qu¸ tr×nh
s¾p xÕp thø tù víi h[t]=1. ViÖc chén c¸c ®é t¨ng thÝch hîp sÏ lµm gi¶m
thêi gian s¾p thø tù.
- DÆt h1 = h[1] ta ph¶i khai b¸o d·y a nh sau:
10
A : Array[1..n] of Item;
c¸c phÇn tö A[i] (ih. Quick Sort:
* Gi¶i thÝch:
Néi dung cña ph¬ng ph¸p nµy lµ chän phÇn tö x ë gi÷a cña d·y lµm
chuÈn ®Ó so s¸nh. Ta ph©n ho¹ch d·y nµy thµnh 3 d·y con liªn tiÕp
nhau:
- D·y con thø nhÊt gåm phÇn tö cã kho¸ nhá h¬n x.key.
- D·y con thø hai gåm c¸c phÇn tö cã kho¸ b»ng x.key.
- D·y con thø ba gåm c¸c phÇn tö cã kho¸ lín h¬n x.key.
Sau ®ã ¸p dông gi¶i thuËt ph©n ho¹ch nµy cho d·y con thø nhÊt nhÊt
vµ d·y con thø ba, nÕu c¸c d·y con cã nhiÒu h¬n mét phÇn tö (§Ö qui).
Cô thÓ lµ xÐt mét do¹n cña d·y tõ thµnh phÇn L ®Õn thµnh phÇn thø
R.
- LÊy gi¸ trÞ cña thµnh phÇn thø (L+R) Div 2 g¸n vµo biÕn X.
- Cho i ban ®Çu lµ L.
- Cho j ban ®Çu lµ R.
- LËp l¹i.
* Chõng nµo cßn A[i] < X th× t¨ng i.
* Chõng nµo cßn A[j] > X th× gi¶m j.
* ij
+ S¾p xÕp ®o¹n tõ A[L] ®Õn A[j]
+ S¾p xÕp ®o¹n tõ A[i] ®Õn A[R]
* VÝ dô:
S¾p xÕp d·y sè:
39 50 7 37 89 13 1 62
X = 37
Sau 2 lÇn ®æi chæ ta ®îc d·y:
1 13 7 37 89 50 39 62
Xö lý d·y con:
1 13 7
Ta ®îc:
12
1 7 13
Sö lý d·y con:
89 50 39 62
Ta ®îc:
39 50 89 62
39 50 62 89
VËy d·y ®· s¾p xÕp lµ:
1 7 13 39 50 62 89
* ThÓ hiÖn b»ng Pascal:
§Ó ®¬n gi¶n ta viÕt thñ tôc s¾p mét m¶ng sè nguyªn ®îc truyÒn
tham biÕn.
Procedure Quick_Sort(Var A : Array[1..n] of Integer);
Procedure Sort(L,R : Integer);
Var
i,j,Tg,X : Integer;
Begin
X := A[(L+R) Div 2];
i := L;
j := R;
Repeat
While (A[i] < X) do Inc(i);
While (A[j] > X) do Dec(j);
If i j;
If L < j Then Sort(L,j);
If i < R Then Sort(i,R);
End;
Begin
13
Sort(1,n);
End;
i. Ph¬ng ph¸p trän (Merging Sort)
* Gi¶i thÝch:
Néi dung cña ph¬ng ph¸p nµy lµ chia d·y sè cÇn s¾p thµnh c¸c d·y con
®· cã thø tù(goi lµ c¸c Run) vµ cã sè phÇn tö lµ luü thõa 2 sau ®ã t×m
c¸ch trén dÇn chóng víi nhau thµnh c¸c Run cã thø tù chiÒu dµi t¨ng
dÇn cho ®Õn khi chØ cßn mét Run th× qu¸ tr×nh s¾p xÕp kÕt thóc.
Ta cã gi¶i thuËt sau ®©y ®Ó trén 2 Run x vµ y cïng thø tù cã chiÒu
dµi lÇn lît lµ m vµ n thµnh mét run z cã chiÒu dµi lµ m + n.
Procedure Merge;
Var
i,j,k : Integer;
Begin
i := 1;
j := 1;
k := 1;
While (i i := i + 1;
End;
While j0 then
Begin
m := (r+l) div 2;
mergesort (l,m); mergesort (m+1,r);
for i:=m downto l do b [i] := a [i];
for j:=m+1 to r do b [r+m+1-j] := a [j];
for k := l to r do
if b[i] < b [j] then
begin a [k] := b[i]; i:=i+1; end else
begin a [k] := b[j]; j:=j-1; end;
end;
End;
End;
15
II. Hình học:
- §iÓm lµ ®èi t îng c¬ së trong h×nh häc. Mçi ®iÓm mµ chóng ta xÐt
sau ®©y ®îc biÓu diÔn b»ng mét cÆp sè nguyªn- to¹ ®é ®iÓm ®ã trong
hÖ trôc Descart th êng dïng.
- Mét ®o¹n th¼ng lµ mét cÆp ®iÓm ®îc nèi víi nhau bëi 1 phÇn cña
®êng th¼ng.
- Mét ®a gi¸c lµ mét danh s¸ch c¸c ®iÓm, víi hai ®iÓm c¹nh nhau ®îc
nèi bëi mét ®êng th¼ng vµ ®iÓm ®Çu nèi víi ®iÓm cuèi t¹o thµnh
mét h×nh ®ãng.
Th«ng th êng chóng ta dïng mét m¶ng ®Ó biÓu diÔn mét ®a gi¸c, dï
r»ng trong mét sè tr êng hîp ta cã thÓ dïng danh s¸ch liªn kÕt hay c¸c
kiÓu kh¸c. HÇu hÕt trong c¸c ch¬ng tr×nh chóng ta dïng kiÓu sau
®©y:
Type point = record x , y : integer; end;
line = record p1 , p2 : pointer; end;
Var polygon : array [0 .. nmax] of point;
Chó ý r»ng c¸c ®iÓm ®îc biÓu diÔn trªn to¹ ®é nguyªn, còng cã thÓ
dïng sè thùc nhng dïng täa ®é nguyªn th× thuËt to¸n sÏ ®¬n gi¶n h¬n
nhiÒu vµ phÐp tÝnh thùc hiÖn nhanh h¬n ®¸ng kÓ.
NhiÒu ®èi t îng h×nh häc phøc t¹p sÏ ®îc biÓu diÔn dùa trªn c¸c phÇn
tö c¬ së nµy.
1/Giao c¸c ®o¹n th¼ng:
Trong bµi häc s¬ cÊp ®Çu tiªn, chóng ta sÏ xÐt xem 2 ®o¹n th¼ng cã
giao nhau hay kh«ng. Mét ph¬ng ph¸p dÔ hiÓu ®Ó gi¶i quyÕt bµi to¸n
nµy lµ t×m giao ®iÓm cña c¸c ®êng th¼ng x¸c ®Þnh bëi c¸c ®o¹n th¼ng
®ã råi kiÓm tra xem nã cã n»m gi÷a hai ®iÓm ®Çu cña hai ®o¹n
th¼ng ®ã hay kh«ng. Mét c¸ch dÔ dµng kh¸c lµ xem thö xem ®êng ®i
tõ ®iÓm thø nhÊt sang ®iÓm thø 2 råi sang ®iÓm thø 3 theo chiÒu
kim ®ång hå hay ngîc chiÒu kim ®ång hå:
Function ccw ( p0 , p1 , p2 : pointer ) : integer;
Var dx1 , dx2 , dy1 , dy2 : integer;
Begin
dx1:=p1.x; dy1:=p1.y-p0.y;
dx2:=p2.x; dy2:=p2.y-p0.y;
If dx1*dy2>dy1*dx2 then ccw:=1;
16
If dx1*dy2® Þnh, qua t Êt c¶ c¸c ® iÓm, kh«ng giao nhau vµ cuèi cïng t rë vÒ ® iÓm
b¾t ® Çu. §êng ® i nh t rªn gäi lµ ®êng khÐp kÝn ® ¬ n.
§Ó gi¸ i quyÕt bµi to¸ n nµy ta ph¶i chän mét ® iÓm lµm "® iÓm gèc".
Sau ® ã t Ýnh gãc t¹o b»ng c¸ch vÏ mét ® êng tõ mçi ® iÓm t rong t Ëp hîp
® Õn gèc vÏ ra t heo ph¬ ng ngang. Sau ® ã, s¾p t hø t ù c¸c ® iÓm t heo t hø
t ù t¨ ng dÇn cña gãc t ¬ ng øng, cuèi cïng nèi c¸c ® iÓm c¹nh nhau l¹i.
Gäi dx , dy lµ kho¶ng c¸ch tõ ® iÓm gèc ® Õn mét ® iÓm kh¸ c t heo t rôc
hoµnh vµ t ung t h× gãc cÇn t Ýnh t rong gi¶i t huËt nµy lµ cotan dy / dx.
Nhng hµm nµy cã vÏ chËm, v× vËy ta cã t hÓ t hay b»ng mét hµm kh¸ c
t ¬ ng t ù nhng dÔ t Ýnh h¬ n, ® ã lµ dy / ( dy + dx ). Ch¬ ng t r× nh sau t r¶
l¹i gi¸ t rÞ tõ 0 ® Õn 360, kh«ng ph¶i lµ gãc t¹o bëi p1 vµ p2 so víi ph¬ ng
ngang nhng cã cïng t huéc t Ýnh nh gãc ® ã.
Funct ion t heta ( p1 , p2 : pointer ) : real;
Var dx , dy , ax , ay : integer;
Begin
dx:= p2.x - p1.x; ax:= abs(dx);
dy:= p2.y - p1.y; ay:= abs(dy);
If (dx= 0) and (dy= 0) t hen t:= 0 else
t:= dy/(ax+ ay);
If dx < 0 t hen t:= 2-t else
If dy < 0 t hen t:= 4+ t;
t heta := t *90;
End;
3/ §iÓm n»m trong ®a gi¸c:
TiÕp theo, chóng ta sÏ xÐt mét bµi to¸n rÊt tù nhiªn: cho mét ®iÓm
vµ mét ®a gi¸c biÓu diÔn b»ng mét m¶ng c¸c ®iÓm, x¸c ®Þnh xem
®iÓm nµy n»m trong hay ngoµi ®a gi¸c. Mét gi¶i ph¸p dÔ hiÓu ®Ó gi¶i
bµi to¸n nµy lµ vÏ mét ®äan th¼ng dµi b¾t ®Çu tõ ®iÓm ®ã theo mét
híng bÊt kú vµ ®Õm sè lîng ®o¹n th¼ng t¹o ®îc do nã c¾t qua ®a gi¸c.
NÕu lµ sè lÏ, ®iÓm ®ã n»m trong ®a gi¸c vµ ngîc l¹i. ®iÒu nµy dÔ thÊy
nÕu chóng ta theo dâi nh÷ng g× x·y ra khi ®i tõ mét ®iÓm n»m ngoµi
®a gi¸c.
Tuy nhiªn, kh«ng ph¶i chØ nh thÕ, bëi v× mét sè giao ®iÓm cã thÓ
trïng víi ®a gi¸c, hoÆc ®o¹n th¼ng dïng ®Ó kiÓm tra trïng víi mét c¹nh
cña ®a gi¸c.
18
Nhu cÇu xö lý c¸c t×nh huèng khi c¸c ®Ønh c¶u ®a gi¸c r¬i trªn ®o¹n
th¼ng kiÓm tra buéc chóng ta ph¶i lµm nhiÒu h¬n lµ chØ ®Õm sè
giao ®iÓm cña c¸c c¹nh ®a gi¸c víi ®o¹n th¼ng kiÓm tra. Thùc chÊt,
chóng ta muèn ®i vßng quanh ®a gi¸c, t¨ng mét biÕn ®Õm khi nµo ta
di tõ mét bªn cña ®o¹n th¼ng kiÓm tra sang mét bªn kh¸c. Mét c¸ch ®Ó
thùc hiÖn lµ ®¬ngi¶n bá qua c¸c ®iÓm r¬i trªn ®o¹n th¼ng kiÓm tra,
nh trong ch¬ng tr×nh sau ®©y:
Function inside (t:point):boolean;
Var count,i,j:integer;
lt,lp:line;
Begin
count:=0; j:=0; p[0]:=p[N]; p[N+1]:=p[1];
lt.p1:=t; lt.p2:=t; lt.p2.x:=maxint;
For i:=1 to N do
Begin
lp.p1 := p [i]; lp.p2 := p [i];
If not intersect (lp,lt) then
Begin
lp . p2 := p [j]; j := i;
If intersect (lp,lt) then count := count + 1;
End;
End;
inside := ((count mod 2) = 1);
End;
Ch¬ng tr×nh nµy dïng ® êng th¼ng kiÓm tra theo ph¬ng ngang ®Ó
dÔ tÝnh to¸n. BiÕn j ® dïng ®Ó lu tr÷ chØ sè cña ®iÓm cuèi cïng cña
îc
®a gi¸c mµ kh«ng n»m trªn ®o¹n kiÓn tra. Ch¬ng tr×nh gi¶ sö r»ng p
[ 1 ] lµ ®iÓm cã täa ®éx nhá nhÊt trong sè tÊt c¶ c¸c®iÓm cã täa ®éy
nhá nhÊt, v× vËy nÕu p [ 1 ] n»m trªn ®o¹n kiÓm tra th× p [ 0 ] kh«ng
thÓ. Cïng mét ®a gi¸c cã thÓ biÓu diÔn b»ng N m¶ng kh¸c nhau, nhng
®iÒu nµy cho thÊy ¸p dông mét quy luËt chuÈn cho p [ 1 ] ®«i khi l¹i
tiÖn lîi. NÕu ®iÓm kÕt tiÕp trªn ®a gi¸c mµ kh«ng n»m trªn ®o¹n
kiÓm tra, ë cïng mét phÝa nh ®iÓm thø j ®èi víi ®o¹n kiÓm tra th×
chóng ta kh«ng cÇn ph¶i t¨ng biÕn ®Õm giao ®iÓm ( count ). Ngîc l¹i,
chóng ta cã ® mét giao ®iÓm.
îc
19
NÕu ® a gi¸c chØ cã 3 hay 4 c¹nh, t hêng gÆp t rong nhiÒu øng dông
t h× mét ch¬ ng t r× nh phøc t¹p nh vËy sÏ kh«ng ®îc sö dông, mét t hñ tôc
® ¬ n gi¶n ® Æt c¬ së t rªn viÖc gäi ccw sÏ t hÝch hîp h¬ n. Mét t r êng hîp
® Æc biÖt quan t räng kh¸ c l¸ ® èi víi ® a gi¸c låi, ®îc xÐt t rong ch¬ ng
kÕ, nã cã ® Æc ® iÓm lµ kh«ng cã ® o¹n kiÓm t ra nµo cã h¬ n 2 giao
® iÓm víi ® a gi¸c. Trong t r êng hîp nµy, mét t hñ tôc nh t× m nhÞ ph© n
cã t hÓ dïng ® Ó x¸c ® Þnh t rong O ( log N ) bíc ® Ó biÕt ®îc ® iÓm cã ë
bªn t rong hay kh«ng.
III. Cặp ghép:
1. Giíi thiÖu chung:
XÐt hai t¹p h÷u h¹n X, Y gåm n phÇn tö:
X= { x1, x2, ... xn }
Y= { y1, y2, ... yn }
CÆp phÇn tö (x, y) víi x thuéc X, y thuéc Y ®îc gäi lµ mét cÆp ghép.
Hai cÆp ghép (x , y) vµ (x1, y1) ®îc gäi lµ rêi nhau nÕu x # x1 vµ y #
y1. TËp M gåm c¸c cÆp ghÐp rêi nhau ®îc gäi lµ mét tËp cÆp ghÐp.
Th«ng th êng bµi to¸n x©y dùng c¸c cÆp ghÐp ®îc tiÕp cËn theo 2 h-
íng: HoÆc tho¶ m·n mét sè ®iÒu kiÖn ghÐp cÆp nµo ®Êy, khi ®ã ng-
êi ta quan t©m ®Õn kh¶ n¨ng ghÐp cÆp tèi ®a, hoÆc l îng ho¸ viÖc
ghÐp cÆp, khi ®ã ngêi ta quan t©m ®Õn viÖc tèi u ho¸ theo c¸c gi¸ trÞ
®· lîng ho¸.
V× sè tËp cÆp ghÐp lµ h÷u h¹n, nªn cã mét ph¬ng ph¸p x©y dùng
tÇm cì lµ thö tÊt c¶ c¸c kh¶ n¨ng. Tuy nhiªn, sè kh¶ n¨ng nh vËy rÊt
lín (cì n!). V× thÕ, ngêi ta quan t©m ®Õn viÖc t×m kiÕm nh÷ng thuËt
gi¶i h÷u hiÖu, dÔ cµi ®Æt ch¬ng tr×nh vµ cã tÝnh kh¶ thi cao. Bµi
to¸n nµy nh»m giíi mét sè mô h×nh ghÐp cÆp nh vËy.
2. CÆp ghÐp ®Çy ®ñ tèi u
a. Giíi thiÖu bµi to¸n
Mét cÆp ghÐp, sao cho tÊt c¶ c¸c phÇn tö cña X vµ Y ®Òu ®îc ghÐp
cÆp (nghÜa lµ cã ®ñ n cÆp víi n lµ sè phÇn tö cña X vµ Y), ®îc gäi lµ
ghÐp cÆp ®Çy ®ñ.
Râ rµng mçi song ¸nh p: X -> Y x¸c ®Þnh mét tËp ghÐp cÆp ®Çy ®ñ,
trong ®ã mçi cÆp ghÐp ®îc viÕt díi d¹ng (x , p(x)), x thuéc X. Tõ ®ã
suy ra cã tÊt c¶ n! c¸ch x©y dùng tËp cÆp ghÐp ®Çy ®ñ kh¸c nhau.
20
