Các thuật toán cơ bản về xử lý mạng trong Pascal

Chia sẻ: Diemanh Diemanh | Ngày: | Loại File: DOC | Số trang:27

Thêm vào BST

Báo xấu

662
lượt xem 166
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các thuật toán cơ bản về xử lý mạng trong Pascal

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] (i
h. 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