Bài tập học phần Toán rời rạc 2
111 trang
2870
Bạn đang xem 20 trang mẫu của tài liệu "Bài tập học phần Toán rời rạc 2", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- bai_tap_hoc_phan_toan_roi_rac_2.pdf
Nội dung text: Bài tập học phần Toán rời rạc 2
- TRƯ NG ð I H C SƯ PH M K THU T HƯNG YÊN KHOA CƠNG NGH THƠNG TIN BÀI T P H C PH N TỐN R I R C 2 Trình đ đào t o : ð i h c H đào t o : Chính quy/Liên thơng
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 L I NĨI ð U Cĩ th nĩi tốn h c r i r c là mơn tiên quy t và hi u qu nh t đ ngư i h c nâng cao tư duy tốn h c trong phân tích, thi t k thu t tốn và rèn luy n k năng l p trình v i nh ng thu t tốn ph c t p. Khơng nh ng th nĩ cịn là “c a ngõ” đ ngư i h c cĩ th ti p c n v i r t nhi u modul trong khoa h c máy tính (như Chương trình d ch, lý thuy t tính tốn, Trí tu nhân t o, ). Bài t p đ c ng c và nâng cao ki n th c trong mơn h c này V n i dung, bám sát v i chương trình c a nhà trư ng và h th ng bài t p cũng đư c biên so n theo các chương lý thuy t. V i m i chương s đư c chia thành 4 ph n: Ph n A. Nh c l i lý thuy t : tĩm t t các ki n th c cơ b n, các ví d và các lưu ý h u ích, các kinh nghi m trong khi l p trình Ph n B. ð bài t p: đưa ra các lo i bài t p khác nhau, v i các m c đ khác nhau. Ph n C. Bài t p m u: Hư ng d n gi i m t s bài tiêu bi u trong ph n B, cĩ phân tích thu t tốn và cài đ t chương trình. Ph n D. Bài t p t gi i : ngư i h c th c hi n vi c gi i các bài t p này Mong r ng tài li u này đáp ng đư c ph n nào nhu c u c a h c sinh, sinh viên. Hưng Yên, tháng 7 năm 2010 B mơn Cơng ngh ph n m m Khoa Cơng ngh thơng tin Trư ng đ i h c sư ph m k thu t Hưng Yên Trang 1
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 M C L C Bài 1: Các khái ni m cơ b n c a Lý thuy t đ th 4 M c tiêu 4 a. Nh c l i lý thuy t 4 b. ð bài t p 4 c. Hư ng d n gi i 5 d. Bài t p t gi i 6 Bài 2: Bi u di n đ th trên máy tính 9 M c tiêu 9 a. Nh c l i lý thuy t 9 b. ð bài t p 9 c. Hư ng d n gi i 9 d. Bài t p t gi i 13 Bài 3: ð th Euler 14 M c tiêu 14 a. Nh c l i lý thuy t 14 b. ð bài t p 15 c. Hư ng d n gi i 15 d. Bài t p t gi i 18 Bài 4: ð th hamilton 19 M c tiêu 19 a. Nh c l i lý thuy t 19 b. ð bài t p 19 c. Hư ng d n gi i 19 d. Bài t p t gi i 21 Bài 5: Th o lu n cài đ t đ th , các thu t tốn li t kê chu trình Euler và Hamilton. Th o lu n v bài t p l n 22 M c tiêu 22 a. Nh c l i lý thuy t 22 b. ð bài t p 22 c. Hư ng d n gi i 22 d. Bài t p t gi i 30 Bài 6 Thu t tốn tìm ki m trên đ th và ng d ng 33 M c tiêu 33 a. Nh c l i lý thuy t 33 b. ð bài t p 33 c. Hư ng d n gi i 33 d. Bài t p t gi i 50 Bài 7: Cây và cây khung 51 M c tiêu 51 a. Nh c l i lý thuy t 51 b. ð bài t p 52 c. Hư ng d n gi i 53 d. Bài t p t gi i 54 Bài 8: Th o lu n v cài đ t thu t tốn tìm cây khung nh nh t trên đ th 57 M c tiêu 57 a. Nh c l i lý thuy t 57 b. ð bài t p 57 c. Hư ng d n gi i 57 d. Bài t p t gi i 69 Trang 2
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 9, 10: Bài tốn tìm đư ng đi ng n nh t 70 M c tiêu 70 a. Nh c l i lý thuy t 70 b. ð bài t p 70 c. Hư ng d n gi i 72 d. Bài t p t gi i 91 Bài 12: Bài tốn lu ng c c đ i trong m ng 96 M c tiêu 96 a. Nh c l i lý thuy t 96 b. ð bài t p 97 c. Hư ng d n gi i 98 d. Bài t p t gi i 100 Trang 3
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 1: Các khái ni m cơ b n c a Lý thuy t đ th M c tiêu Lưu tr đư c đ th trên máy tính theo nh ng phương pháp khác nhau. Cài đ t đư c chương trình chuy n đ i gi a các phương pháp. Sinh viên cĩ kh năng t h c. a. Nh c l i lý thuy t Hai đ nh x, y đư c g i là c p đ nh liên thơng , n u ho c gi a x và y cĩ ít nh t m t xích n i v i nhau, ho c t n t i ít nh t m t đư ng đi t y sang x. ð th vơ hư ng G(V,E) đư c g i là đ th liên thơng, n u m i c p đ nh c a nĩ đ u liên thơng. ð th cĩ hư ng G(V,E) đư c g i là đ th liên thơng m ch, n u m i c p đ nh c a nĩ đ u liên thơng. Bi u di n d ng hình h c: Gi s cĩ đ th G(V,E). Bi u di n đ nh: l y các đi m trên m t ph ng hay trên khơng gian tương ng v i các ph n t c a t p V và dùng ngay ký hi u các ph n t này đ ghi trên các đi m tương ng. Bi u di n c nh: N u c nh a v i hai đ nh đ u là x,y thì nĩ đư c bi u di n b ng đo n th ng hay m t đo n cong n i gi a hai đi m x, y và khơng đi qua các đi m tương ng trong khơng gian. Bi u di n cung: n u cung a cĩ đ nh đ u là x, đ nh cu i là y, thì nĩ đư c bi u di n b ng m t đo n th ng ho c đo n cong đư c đ nh hư ng đi t x sang y và khơng qua các đi m tương ng trung gian khác. Hình nh n đư c g i là d ng bi u di n hình h c c a đ th G(V, E). ðơi khi ngư i ta cũng g i d ng bi u di n hình h c là m t đ th . b. ð bài t p Bài 1 Cho G đ th g m 4 ph n G1, G2, G3 và G4 như sau: a. Ch ra t p đ nh, c nh(vơ hư ng,cĩ hư ng, khuyên, ) c a m i đ th đã cho? Ch lo i đ th đĩ? b. ð th G, G1, G2, G3, G4 và G5 cĩ liên thơng ko? N u đ th ko liên thơng hãy ch ra các thành ph n liên thơng? Trang 4
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 c. ð th G, G1, G2, G3, G4 và G5 cĩ chu trình ko? Ch ra các chu trình c a đ th (n u cĩ)? 1 2 5 8 00 G4 3 4 6 7 9 G2 G3 G1 c. Hư ng d n gi i Bài 1 a. Tên đ th T p đ nh V T p c nh E Lo i đ th G1 1,2,3,4 (1,2);(1,4);(2,3);(2,4);(3,4) Vơ hư ng G2 5,6,7 (5,6);(5,7);(6,7) Cĩ hư ng G3 8,9 (8,9) Vơ hư ng G4 0 G 1,2,3,4,5,6,7,8,9,0 (1,2);(1,4);(2,3);(2,4);(3,4); H n h p (8,9) (5,6);(5,7);(6,7) b. Tên đ th Tính liên thơng Tên thành ph n liên thơng G1 Cĩ G1 G2 Cĩ G2 Trang 5
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 G3 Cĩ G3 G4 Cĩ G4 G Khơng G1,G2,G3,G4 c. Tên đ th Cĩ chu trình? Tên chu trình G1 Cĩ (1,2,4,1);(1,2,3,4,1);(2,3,4,2) G2 Khơng G3 Khơng G4 Khơng G Cĩ (1,2,4,1);(1,2,3,4,1);(2,3,4,2) d. Bài t p t gi i Bài 1. M t qu n đ o cĩ n( n ) hịn đ o và hai hịn đ o b t kì thu c qu n đ o đ u cĩ s đ u m i đư ng ng m t i m t trong nhưng hịn đ o n y đ u nh hơn n. Ch ng minh r ng t m t hịn đ o tùy ý thu c qu n đ o ta cĩ th đi đ n m t hịn đ o b t kì khác c a qu n đ o b ng đư ng ng m. Bài 2 Khi v ngh hè m i b n h c sinh c a l p 11A trư ng Lê H ng Phong đ u trao đ i đ a ch v i ít nh t m t n a s b n trong l p. Ch ng minh r ng trong th i gian ngh hè m i b n c a l p 11A đ u cĩ th báo tin tr c ti p hay gián ti p cho các b n trong l p. Bài 3 Trong m t cu c h p cĩ đúng hai đ i bi u khơng que nhau và m i đ i bi u này cĩ m t s l ngư i que đ n d . Ch ng minh r ng luơn luơn cĩ th x p m t s đ i bieetr ng i chen gi a hai đ i bi nĩi trên , đ ngư i ng i gi a hai ngư i mà anh( ch ) ta quen. Hư ng đ n: Trang 6
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 ð gi i đư c bài tốn trên trư c h t ta xây d ng các đ th tương ng, sau đĩ v n d ng k t qu c a đ nh lý 4.1, h qu 4.1 và đ nh lý 4.2 mà suy ra k t lu n. Xuây d ng đ th • ð nh: L y các đi m trong m t ph ng hay trong khơng gian tương ng v i các hịn đ o thu c qu n đ o ( các b n h c sinh trong l p 11A, các đ i bi u đ n h p). • C nh: Hai đi m x, y đư c n i b ng m t c nh khi và ch khi hai hịn đ o x, y cĩ đư ng ng m tr c ti p v i nhau( các b n x, y trao đ i đ a ch cho nhau, các đ i bi u x, y quen nhau) ð th nhân đư c ký hi u b ng G1 , ( G2 , G 3) ð th G1 mơ t tồn b lư i đư ng ng m trong qu n đ o ð th G2 mơ t tồn b quan h trao đ i đ a ch trong l p 11A ð th G3 mơ t tồn b quen bi t trong các đ i bi u trong các đ i bi u đ n d h p. V n d ng k t qu các đ nh lý đ suy ra k t lu n Do hai hịn đ o b t kì đ u cĩ t ng s đ u m i đư ng ng m khơng nh hơn n, nên hai đ nh b t kì c a đ th G1 đ u cĩ t ng b c khơng nh hơn n. B i v y theo đ nh lý 4.1. đ th G1 liên thơng, nên hai hịn đ o b t kì cĩ đư ng h m n i v i nhau. Vì m i b n h c sinh trong l p 11A trao đ i đ a ch v i ít nh t m t n a s b n tron l p, nên b c c a m i đ nh c a G2 khơng nh hơn m t n a s đ nh c a đ th . Khi đĩ , theo h qu 4.1. đ th G2 liên thơng. B i v y hai đ nh x, y đ u cĩ xích n i v i nhau. Khi đĩ thơng qua các b n tương ng v i các đ nh thu c xích , mà b n tương ng v i đ nh x báo tin đư c cho tương ng v i đ nh y và ngư c l i. Hai đ i bi u khơng quen nhau, thì hai đ nh tương ng khơng k nhau. M i đ i bi u này l i cĩ m t s l ngư i quen đ n h p, nên trong đ th liên thơng G3 cĩ đúng hai đ nh b c l và hai đ nh này l i khơng k nhau. Khi dĩ, theo đ nh lý 4.2, hai đ nh này liên thơng nên cĩ ít nh t m t xich n i gi a hai đ nh này. Gi s là m t trong nh ng m i xích n i gi a hai b c l này. D a vào ta s p x p các đ i bi u tương ng ng i gi a hai ngư i mà anh ch quen. Bài 4 Cho G đ th như sau: Ch ra t p đ nh, c nh(vơ hư ng,cĩ hư ng, khuyên, ) c a m i đ th đã cho? Ch lo i đ th đĩ? ð th cĩ liên thơng ko? N u đ th ko liên thơng hãy ch ra các Trang 7
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 thành ph n liên thơng? ð th cĩ chu trình ko? Ch ra các chu trình c a đ th (n u cĩ)? Trang 8
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 2: Bi u di n đ th trên máy tính M c tiêu Nêu đư c các cách bi u di n đ th và bi u di n đ th trên máy tính trên máy tính. ðưa ra đư c ma tr n k , danh sách các c nh, cung tương ng v i 1 đ th cho trư c. Lưu tr đư c đ th trên máy tính theo nh ng phương pháp khác nhau. Phân tích đư c bài tốn th c t tương ng ph n lý thuy t đã h c. Sinh viên cĩ kh năng t h c. a. Nh c l i lý thuy t b. ð bài t p Bài 1 Cho G đ th g m 4 ph n G1, G2, G3 và G4 như sau: 1 2 5 8 00 G4 3 4 6 7 9 G2 G3 G1 a. Bi u di n các đ th G,G1,G2,G3,G4 dư i d ng ma tr n k b. Bi u di n các đ th G,G1,G2,G3,G4 dư i d ng danh sách c nh(cung) c. Bi u di n các đ th G,G1,G2,G3,G4 dư i d ng danh sách k Bài 2 Cài đ t chương trình nh p danh sách k c a đ th t bàn phím và đưa danh sách đĩ ra màn hình. c. Hư ng d n gi i Bài 1 Trang 9
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Tên đ th a. ma tr n k b. danh sách c.danh sách k c nh(cung) G1 1 2 3 4 Danh sách c nh 1 2 4 1 0 1 0 1 1 2 2 1 4 2 1 0 0 1 1 4 3 4 3 0 0 0 1 2 3 4 1 2 3 4 1 1 1 0 2 4 3 4 G2 5 6 7 Danh sách cung 5 6 7 5 0 0 1 5 6 6 7 6 1 0 1 5 7 7 0 0 0 6 7 G3 8 9 Danh sách c nh 8 9 8 0 1 8 9 9 8 9 1 0 G4 0 0 0 G 1 2 3 4 5 6 7 8 9 0 Danh sách cung 1 2 4 1 0 1 0 1 0 0 0 0 0 0 1 2 2 1 4 2 1 0 0 1 0 0 0 0 0 0 1 4 3 4 3 0 0 0 1 0 0 0 0 0 0 2 1 4 1 2 3 4 1 1 1 0 0 0 0 0 0 0 2 3 5 6 7 5 0 0 0 0 0 0 1 0 0 0 2 4 6 7 Trang 10
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 6 0 0 0 0 1 0 1 0 0 0 3 2 8 9 7 0 0 0 0 0 0 0 0 0 0 3 4 9 8 8 0 0 0 0 0 0 0 0 1 0 4 1 0 9 0 0 0 0 0 0 0 1 0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 4 3 5 6 5 7 6 7 Bài 2 Chương trình nh p danh sách k c a đ th t bàn phím và đưa danh sách đĩ ra màn hình Phân tích bài tốn : Trong r t nhi u thu t tốn làm vi c v i đ th chúng ta thư ng xuyên ph i th c hi n các thao tác: Thêm ho c b t m t s c nh. Trong trư ng h p này C u trúc d li u dùng trên là khơng thu n ti n. Khi đĩ nên chuy n sang s d ng danh sách k liên k t (Linked Adjancency List) như mơ t trong chương trình nh p danh sách k c a đ th t bàn phím và đưa danh sách đĩ ra màn hình Chương trình minh h a : Program AdjList; Const maxV=100; Type link=^node; node=record Trang 11
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 v:integer; next:link; End; Var j,x,y,m,n,u,v:integer; t:link; Ke:array[1. .Vmax] of link; Begin Write(‘Cho so canh va dinh cua do thi:’); readln(m,n); (*Khoi tao*) for j:=1 to n do Ke[j]:=nil; for j:=1 to m do begin write(‘Cho dinh dau va cuoi cua canh ‘,j,’:’); readln(x,y); new(t); t^.v:=x, t^.next:=Ke[y]; Ke[y]:=t; new(t); t^.v:=y, t^.next:=Ke[x]; Ke[x]:=t; end; writeln(‘Danh sach ke cua cac dinh cua do thi:’); for J:=1 to m do begin writeln(‘Danh sachcac dinh ke cua dinh ‘,j,’:’); t:=Ke[j]; Trang 12
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 while t^.next<>nil do begin write(t^.v:4); t:=t^.next; end; end; readln; End. d. Bài t p t gi i Trang 13
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 3: ð th Euler M c tiêu Ki m tra đư c m t đ th b t kỳ cĩ là đ th euler hay khơng. Áp d ng đư c thu t tốn tìm chu trình Euler, đư ng Euler, v i 1 đ th cho trư c. Lưu tr đư c đ th trên máy tính theo nh ng phương pháp khác nhau. Cài đ t đư c chương trình chuy n đ i gi a các phương pháp. Cài đ t đư c thu t tốn Tìm chu trình Euler. Cài đ t đư c thu t tốn duyêt đ th duy t theo chi u sâu ho c duy t theo chi u r ng. Sinh viên cĩ kh năng t h c. a. Nh c l i lý thuy t Chu trình (t.ư. đư ng đi) đơn ch a t t c các c nh (ho c cung) c a đ th (vơ hư ng ho c cĩ hư ng) G đư c g i là chu trình (t.ư. đư ng đi) Euler. M t đ th liên thơng (liên thơng y u đ i v i đ th cĩ hư ng) cĩ ch a m t chu trình (t.ư. đư ng đi) Euler đư c g i là đ th Euler (t.ư. n a Euler) . Trang 14
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 ð nh lý ð th (vơ hư ng) liên thơng G là đ th Euler khi và ch khi m i đ nh c a G đ u cĩ b c ch n. H qu ð th liên thơng G là n a Euler (mà khơng là Euler) khi và ch khi cĩ đúng hai đ nh b c l trong G. Thu t tốn v ch đư c m t chu trình Euler trong đ th liên thơng G cĩ b c c a m i đ nh là ch n theo thu t tốn Fleury sau đây. Xu t phát t m t đ nh b t kỳ c a G và tuân theo hai quy t c sau: 1. M i khi đi qua m t c nh nào thì xố nĩ đi; sau đĩ xố đ nh cơ l p (n u cĩ); 2. Khơng bao gi đi qua m t c u, tr phi khơng cịn cách đi nào khác. b. ð bài t p Bài 1: ð th sau cĩ là đ th n a Euler hay đ th Euler ko? Gi i thích? c. Hư ng d n gi i Bài 1: ð th sau cĩ là đ th n a Euler hay đ th Euler ko? Gi i thích? Trang 15
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 b c a e d G1 ð th G1 là đ th n a Euler Th t vây, các đ nh a,b,e cĩ b c là 2,4,4 là b c ch n, các đ nh c và d cĩ b c là 3 là b c l a b d c G2 ð th G2 là đ th n a Euler Th t vây, các đ nh c và d cĩ b c là 2 là b c ch n, các đ nh a và c cĩ b c là 1 là b c l Trang 16
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 a b e d c f g G3 ð th G3 khơng là đ th Euler Th t v y G3 cĩ 3 đ nh a,d và g cĩ b c là 1 là b c l 1 5 2 4 3 G4 ð th G4 là đ th n a Euler vì theo h qu Th t vây, các đ nh 3,4,5 cĩ b c là 2 là b c ch n, các đ nh 1 và 2 cĩ b c là 3 là b c l Bài 2 Trang 17
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Xu t phát t u, ta cĩ th đi theo c nh (u,v) ho c (u,x), gi s là (u,v) (xố (u,v)). T v cĩ th đi qua m t trong các c nh (v,w), (v,x), (v,t), gi s (v,w) (xố (v,w)). Ti p t c, cĩ th đi theo m t trong các c nh (w,s), (w,y), (w,z), gi s (w,s) (xố (w,s)). ði theo c nh (s,y) (xố (s,y) và s). Vì (y,x) là c u nên cĩ th đi theo m t trong hai c nh (y,w), (y,z), gi s (y,w) (xố (y,w)). ði theo (w,z) (xố (w,z) và w) và theo (z,y) (xố (z,y) và z). Ti p t c đi theo c nh (y,x) (xố (y,x) và y). Vì (x,u) là c u nên đi theo c nh (x,v) ho c (x,t), gi s (x,v) (xố (x,v)). Ti p t c đi theo c nh (v,t) (xố (v,t) và v), theo c nh (t,x) (xố c nh (t,x) và t), cu i cung đi theo c nh (x,u) (xố (x,u), x và u). d. Bài t p t gi i Trang 18
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 4: ð th hamilton M c tiêu Ki m tra đư c m t đ th b t kỳ cĩ là đ th Hamilton hay khơng. Áp d ng đư c thu t tốn tìm chu trình Hamilton, đư ng Hamilton, v i 1 đ th cho trư c. Lưu tr đư c đ th trên máy tính theo nh ng phương pháp khác nhau. Cài đ t đư c chương trình chuy n đ i gi a các phương pháp. Cài đ t đư c thu t tốn Tìm chu trình Halmiton. Cài đ t đư c thu t tốn duyêt đ th duy t theo chi u sâu ho c duy t theo chi u r ng. Sinh viên cĩ kh năng t h c. a. Nh c l i lý thuy t ð th Hamilton(n a Hamilton) là đ th cĩ ch a m t chu trình(đư ng đi) Hamilton Hay ðư ng đi (x[1],x[2], ,x[n]) đư c g i là đư ng đi Hamilton n u x[i]≠x[j] (1≤i<j≤n) Chu trình (x[1],x[2], ,x[n],x[1]) đư c g i là chu trình Hamilton n u x[i]≠x[j] (1≤i<j≤n) Note! Cho t i nay, v n chưa tìm ra phương pháp v i đ ph c t p đa th c đ tìm chu trình cũng như đư ng đi Hamilton trong trư ng h p đ th t ng quát. Cĩ th s d ng thu t tốn quay lui đ li t kê chu trình Hamilton b. ð bài t p Bài 1: ð th sau cĩ là đ th n a Hamilton hay đ th Hamilton ko? Gi i thích? c. Hư ng d n gi i Bài 1: ð th sau cĩ là đ th n a Hamilton hay đ th Hamilton ko? Gi i thích? Trang 19
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 b c a e d G1 ð th G1 là đ th Hamilton a b d c G2 ð th G2 là đ th n a Hamilton a b e d c f g G3 ð th G3 khơng cĩ chu trình hay đư ng đi Hamilton Trang 20
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 1 5 2 4 3 G4 ð th G4 là đ th Hamilton, vì cĩ chu trình Hamilton (1,3,5,2,4,1) d. Bài t p t gi i Trang 21
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 5: Th o lu n cài đ t đ th , các thu t tốn li t kê chu trình Euler và Hamilton. Th o lu n v bài t p l n M c tiêu Lưu tr đư c đ th trên máy tính theo nh ng phương pháp khác nhau. Chuy n đ i gi a các ki u bi u di n đ th trên máy tính. Nâng cao kh năng làm vi c nhĩm. Rèn luy n tư duy sáng t o. Phân tích đư c bài tốn th c t tương ng ph n lý thuy t đã h c. Sinh viên cĩ kh năng t h c. a. Nh c l i lý thuy t Xem l i trong bài 3 và bài 4 b. ð bài t p Bài 1 Tìm chu trình Euler trong đ th G. Bài 2 Tìm chu trình Halmiton trong đ th G. c. Hư ng d n gi i Bài 1 ð bài : Cài đ t chương trình tìm chu trình Euler trong đ th G. Cho đ th G=(X,E) t n t i chu trình Euler. Hãy tìm chu trình (chi trình Euler là chu trình đi qua t t c các c nh c a đ th , m i c nh đi qua đúng m t l n). Phân tích bài tốn : ð u vào: ð th G ð u ra: Chu trình Euler (n u cĩ) 2. Thu t tốn: Xu t phát t m t đ nh u b t kỳ, khi đi qua c nh nào thì xố c nh đĩ kh i đ th và ghi l i t trái sang ph i. Khi th c hi n thu t tốn c n lưu ý n u g p c nh b c c u gi a 2 thành ph n liên thơng thì ta ph i xố h t thành ph n liên thơng r i m i xố đ n c nh b c c u. Trang 22
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Khi xố c nh b c c u thì ph i lo i h t các đ nh trơ tr i (nghĩa là khơng k v i b t c đ nh nào thu c đ th ). C u trúc d li u: Bi u di n đ th b ng ma tr n k a(i,j), do đĩ lưu ý khi xố đi m t c nh ta ch vi c gán a(i,j)=a(j,i)=0, đ ng th i ph i lưu c nh v a xố vào m t m ng khác: M ng Ctr. M ng lt: array [1 Nmax] of integer dùng trong th t c tìm thành ph n liên thơng (gi ng như m t thu t tốn tìm thành ph n liên thơng trình bày trên). M ng dd: array [1 Nmax] of Boolean, giá tr dd[i] cho bi t đ nh i b lo i kh i đ th hay chưa. N u b l i thì dd[i]=True; ngư c l i dd[i]=False; Th t c Procedure Euler_Cycle; Begin STACK:= ∅ ; CE:= ∅ ; Chon u la mot dinh nao do cua do thi; STACK ← u; While STACK ∅ then Begin Y:=dinh dau tien trong danh sach Ke(x); STACK ← y; (* loai bo canh (x,y) khoi do thi *) Ke(x):=Ke(x)\ { y} ; Ke(y):=Ke(y)\{ x} ; Trang 23
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 End Else Begin x⇐ STACK; CE ⇐ x; End; End; End; Chương trình minh h a : Program Chu_trinh_Euler; Const Nmax=100; Emax=100; Var a:array[1 Nmax,1 Nmax]of integer; Ctr: array[1 Emax,1,2]of integer; dd: array[1 Nmax]of Boolean; lt: array[1 Nmax]of integer; SolC,N:integer; (*Bi n Solc là s c nh c a chu trình, s tăng lên m t đơn v m i khi ta đi qua m t c nh*). Program Timtplt(k :integer) ; (* Th t c này tìm thành ph n liên thơng gi ng như thu t tốn tình thành ph n liên thơng trình bày trên ch khác m t đi m là ta ch tìm tplt đ i v i các đ nh chưa b lo i kh i đ th *). Var i:integer; Begin lt[k]:=sotp; Trang 24
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 For i=1 to N do If dd[i] and (lt[i]=0) and(a[i,k]=1)then Begin lt[i]:=sotp; Timtplt(i); End; End; Function KTLT (u,v:integer):Boolean; (* Hàm này ki m tra xem khi ta xố c nh (u,v) đi thì đ th cịn liên thơng n a hay khơng? N u cịn thì s tplt luơn b ng 1. ðây coi như ki m tra c nh (u,v) cĩ ph i là c nh b c c u hay khơng*). Var i:integer; Begin(* ð u tiên ta ph i xố c nh (u,v) kh i đ th r i m i ti n hành ki m tra *). a[u,v]:=0;a[u,v]:=0; Fillchar(lt,sizeof(lt),0); (* ðo n mã sau tìm s tplt c a đ th đi m đang xét *). Sotp:=0; For i=1 to N do If dd[i] and (lt[i]=0)then Begin inc(sotp); Timtplt (i); End; Trang 25
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 If sotp=1 then KTLT=True Else Bengin ( *n u khơng cĩ c nh b c c u thì khi khơi ph c l i c nh (u,v)*). a[u,v]:=1 a[v,u]:=1 KTLT:=False End; End; Procedure Timchutrinh ; Var i,u,dem:integer; Begin solc:=0; u:=1; (* Chu trình c a ta xu t phát t đ nh 1, tuy nhiên đi u này khơng b t bu c *) For i=1 to N do dd[i] true; (* Kh i t o t t c các giá tr dd[i]=True nghĩa là chưa cĩ đ nh nào b lo i *) REPEAT Dem:=0; (* Bi n đ m là s c nh k v i đ nh u *) Begin For i=1 to N do If a[u,i]=1 then Trang 26
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Begin (*xố c nh (u,i) kh i đ th *) a[u,i]:=0 a[i,u]:=0 (*Lo i đ nh u kh i đ th *) dd[u]:=False; (*ðua c nh (u,i) vào chu trình*). inc(solC); Ctr[solC,1]:=u; Ctr[solC,2]:=i; Break; End; End Else (*Ngư c l i n u cịn nhi u c nh n i v i u ta tìm m t c nh khơng ph i là c nh b c c u và xố c nh đĩ đ ng th i đưa nĩ vào chu trình*) If dem>1 then Begin For i=1 to N do If (a[u,i]=1 and dd[i] and KTLT (u,i)then (*N u c nh (u,i) tho mãn khơng ph i là c nh b c c u thì ta ch n: Nghĩa là nĩ ph i k v i u, chưa b lo i kh i đ th và sau khi xố c nh k đĩ thì đ th v n liên thơng. Riêng đi u ki n th 3 ta dùng hàm KTLT(u,i) đ ki m tra xem khi xáo c nh (u,i) đi thì đ th cịn liên thơng n a hay khơng*). Begin (*ðo n mã sau xố c nh (u,i) và đưa c nh này Trang 27
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 vào chu trình*). a[u,i]:=0 a[i,u]:=0 inc(solC); Ctr[solC,1]:=u; Ctr[solC,2]:=i; Break; (*Sau khi tìm đư c đ nh i thì ta ph i thốt kh i vịng l p For n u khơng cĩ l nh Break thì chương trình s ch y sai*). End; End; (*Chu n b cho phép ti p chu trình c a chúng ta l i xu t phát t đ nh*) u:=1; UNTIL dem=0; End; Procedure Ghifile; Var f:text; I:integer; Begin Assign(f,’kq.out’);Rewrite(f); For i:=1 to solC do writeln(f,Ctr[i,1],’ ‘,Ctr[i,2]); Close(f); BEGIN Trang 28
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Docfile; Timchutrinh; Ghifile; END. Bài 2 ð bài : Li t kê t t c các chu trình Hamilton c a đ th Phân tích bài tốn : Thu t tốn sau đây đư c xây d ng d a trên cơ s thu t tốn quay lui cho phép li t kê t t c các chu trình Hamilton c a đ th . Hình dư i đây mơ t cây tìm ki m theo thu t tốn v a mơ t . ð th và cây li t kê chu trình Hamilton c a nĩ theo thu t tốn quay lui. Trong trư ng h p đ th cĩ khơng quá nhi u c nh thu t tốn trên cĩ th s d ng đ ki m tra đ th cĩ ph i là Hamilton hay khơng. Chương trình minh h a : Procedure Hamilton(k); (* liet ke cac chu trinh Hamilton thu duoc bang viec p hat trien day dinh (X[1],. . . , X[k 1]) cua do thi G=(V,E) cho boi danh sach ke: Ke(v), v ∈ V *) begin Trang 29
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 for y ∈ Ke(X[k 1]) do if (k =N+1) and (y=v0) then Ghinhan(X[1],. . . , X[n], v0) else if Chuaxet[y] then begin X[k]:=y; Chuaxet[y]:=false; Hamilton(k+1); Chuaxet[y]:=true; end; end; (* Main program*) begin for v ∈ V do Chuaxet[v]:=true; X[1]:=0; (* v0 la mot dinh nao do cua do thi *) Chuaxet[v0]:=false; Hamilton(2); end. d. Bài t p t gi i Bài t p 1: H i ngh bàn trịn T ng thư ký ð i h i đ ng Liên h p qu c tri u t p m t cu c h p cĩ N nhà ngo i giao c a N t ch c tham gia. Các đ i di n ngo i giao đư c b trí ng i quanh m t bàn trịn. Gi a m t s t ch c cĩ quan h căng th ng, vì v y khơng th x p h Trang 30
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 ng i c nh nhau đư c. Thơng tin v quan h gi a các t ch c đư c cho dư i d ng c p s nguyên i, j n u gi a 2 t ch c này cĩ quan h căng th ng. Hãy l p trình giúp T ng thư ký Liên h p qu c b trí ch ng i quanh bàn h p. Các t ch c đư c đánh s t 1 t i N, 0 < N <= 500. D li u vào: t file CONF.INP, dịng đ u tiên ch a s nguyên N, các dịng sau, m i dịng m t c p s i, j cho bi t các đ i di n i và j khơng ng i c nh nhau đư c. K t thúc là m t dịng ch a 2 s 0. K t qu : đưa ra file CONF.OUT. N u khơng cĩ cách b trí th a mãn yêu c u thì đưa ra thơng báo KHONG CO, trong trư ng h p ngư c l i – đưa ra dãy N s nguyên xác đ nh v trí ai ng i c nh ai quanh bàn trịn. Ví d : CONF.INP CONF.OUT 11 1 9 7 4 11 5 8 2 10 3 6 1 4 1 7 5 7 10 7 10 8 10 9 3 4 0 0 Bài t p 2: Ki m tra đư ng M t tr m qu ng đư ng giao thơng ph i ch u trách nhiêm v tình tr ng c a m t m ng lư i giao thơng n i gi a các đi m dân cư. Hàng tháng, h ph i c m t đ i đi ki m tra m t vịng qua kh p m ng lư i đ xem xét tình tr ng hi n th i c a các đư ng giao thơng nh m báo s a ch a k p th i n u cĩ nhu c u. Hãy vi t chương trình nh p vào m ng lư i giao thơng và giúp tr m quy t đ nh l trình c a đ i ki m tra sao cho cĩ th thăm t t c các con đư ng mà t ng chi u dài đo n đư ng đi qua là nh nh t. Bài t p 3: Mã đi tu n Hãy cài đ t chương trình xác đ nh l trình c a con mã trên bàn c 8x8 ơ b t đ u t ơ (i, j) đi qua t t c các ơ c a bàn c vàm i ơ ch 1 l n duy nh t. M r ng v i trư ng h p bàn c kích thư c NxN. Bài t p 4: H i ngh bàn trịn Cĩ 12 ngư i ng i chung 1 bàn ti c trịn. M i ngư i cĩ ít nh t 6 ngư i quen. Hãy ch ra cách s p x p sao cho m i ngư i đ u ng i c nh ngư i mình quen . T ng Trang 31
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 quát, hãy s p N ngư i ng i chung quanh bàn trịn sao cho m i ngư i đ u ng i c nh ngư i mình quen. Bi t m i ngư i cĩ ít nh t (N + 1)/2 ngư i quen. Trang 32
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 6 Thu t tốn tìm ki m trên đ th và ng d ng M c tiêu Trình bày đư c ý tư ng, cách cài đ t và cài đ t đư c thu t tốn BFS, DFS. Nêu ưu như c c a t ng thu t tốn đ i v i t ng lo i đ th . Phân tích đư c bài tốn th c t tương ng ph n lý thuy t đã h c. Sinh viên cĩ kh năng t h c. Rèn luy n tư duy sáng t o. a. Nh c l i lý thuy t b. ð bài t p Bài 1 Dùng cây đ mơ t k t qu duy t chi u sâu và duy t theo chi u r ng trên đ th sau: Bài 2 Cho đ th G=(X,E) v i t p các đ nh X và t p các cung E. Xét xem đ th cĩ bao nhiêu thành ph n liên thơng, m i thành ph n liên thơng bao g m nh ng đ nh nào? Bài 3 Thu t tốn tìm đư ng đi theo chi u sâu (thu t tốn duy t theo chi u sâu) Bài 4 Thu t tốn tìm đư ng đi theo chi u r ng (thu t tốn duy t theo chi u r ng) c. Hư ng d n gi i Bài 1 Dùng cây đ mơ t k t qu duy t chi u sâu và duy t theo chi u r ng trên đ th sau: Trang 33
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Duy t r ng Duy t sâu: Bài 2 Thu t tốn tìm s thành ph n liên thơng Cho đ th G=(X,E) v i t p các đ nh X và t p các cung E. Xét xem đ th cĩ bao nhiêu thành ph n liên thơng, m i thành ph n liên thơng bao g m nh ng đ nh nào? Phân tích bài tốn : 3 5 Trang 34
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 8 2 6 3 1 2 2 7 9 2 1 1 3 1 4 1 ð th v i các thành ph n LT ð u vào: a. Bi u di n đ th b ng ma tr n k Dothi.txt Kq.txt 9 So tph cua do thi la:3 0 1 1 1 0 0 0 0 0 TPLT 1 bao gom cac dinh: 1 2 3 4 1 0 1 0 0 0 0 0 0 TPLT 2 bao gom cac dinh: 5 8 1 1 0 1 0 0 0 0 0 TPLT 3 bao gom cac dinh: 6 7 9 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 Trang 35
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 C u trúc d li u ð u tiên đánh s các đ nh là 0 (Dùng m t m ng bi u di n các thành ph n là m ng chúng ta c n tìm, ban đ u ta gán t t c các giá tr c a m ng b ng 0) L y ra đ nh L gán lt[i]:=1 + Duy t các đ nh k c a 1 g p đ nh ti p theo là đ nh 2 chưa đư c đánh s ta đánh s 1 gán lt[2]:=1 sang bư c ti p theo. + Duy t các đ nh k c a 2, g p đ nh 1 đư c đánh s r i nên b qua, g p đ nh chưa đánh s nên đánh s 1, gán lt[4]:=1 sang bư c ti p theo. + Duy t các đ nh k c a 4, g p đ nh 1 đánh s r i nên b qua. G p đ nh 2 đánh s r i nên b qua. G p đ nh 3 chưa đánh s nên đánh s 1, lt[3]:=1 sang bư c ti p theo. + Duy t các đ nh k c a 3 g p tồn các đ nh đánh s r i nên khơng đánh s n a d ng vi c đánh s . Như v y ta đã tìm đư c 1 thành ph n liên thơng. L y ra m t đ nh chưa đánh s ví d ta l y đ nh 6 Ta l i làm như trên ta l i tìm đư c thành ph n liên thơng khác. Như v y ta rút ra đư c C u trúc d li u c a bài tốn này. ð i v i đ th và các c nh thì ta cĩ th dùng ma tr n k ho c danh sách k , và nên đ c t file đ đơn gi n hố. Dùng m t m ng lt[1 n] bi u di n TPLT lt[i]:=K n u đ nh i thu c thành ph n liên thơng. Chương trình minh h a : Trang 36
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 a. Bi u di n đ th b ng ma tr n k . a(i,j)=1 n u 2 đ nh i và j k nhau và =0 n u 2 đ nh i và j khơng k nhau. Program tim_thanh_phan_lien_thong; Const Nmax=100; Type mang=array[1 Nmax] of integer; Var lt:mang; a: array[1 Nmax, 1 Nmax] of byte; N:integer; Sotp: integer; (*Th t c này đ c t file dothi.txt s N là s đ nh c a đ th ma tr n k bi u di n đ th *) Procedure Docfile; Var i,j: integer; f: text; Begin Assign(f,’dothi.txt’);reset(f); Readln(f,N); For i:=1 to N do Read(f,a[i,j]); Close(f); End; (*Th t c đ quy này dùng đ tìm các đ nh thu c m t thành ph n liên thơng *) Procedure Docfile; Var i,j: integer; Trang 37
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Begin lt[k]:=sotp; (*Duy t qua các đ nh c a đ th *) For i:=1 to N do (*N u đ nh i k v i k và chưa đánh d u thì ta g i th t c đ quy. Tìm LT nghĩa là l i đánh d u và duy t các đ nh k c a i *) lf (lt[i]=0)and(a[i,k]=1)then TimLT(i); End; (*Th t c này đư c coi như bư c 2 trong v d *) Procedure TimTPLT; Var i: integer; Begin sotp:=0; (*Duy t các đ nh chưa đư c đánh d u *) For i:=1 to N do (*N u cĩ m t đ nh chưa thu c thành ph n liên thơng nào lt[i]=0 nghĩa là tìm ra m t thành ph n m i nên ta tăng s lư ng thành ph n và b t đ u ta đi tìm thành ph n liên thơng m i đĩ b ng th t c đ quy TimLT(i)*) lf lt[i]=0 then Begin Inc(sotp); TimLT(i); End; End; (*Th t c in ra các thành ph n liên thơng c a đ th *) Trang 38
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Procedure Ghifile; Var i,j: integer; Begin Writeln(‘so thanh phan lien thong cua do thi l : ;sotp); For i:=1 to sotp do Begin Writeln(‘TPLT’, i ,’bao gom cac dinh:’); For j:=1 to N do (*n u j thu c thành ph n liên thơng th i thì in ra *) lf lt[j]=i then Write(J,’ ‘); Writeln; End; Readln; End; BEGIN Docfile; Tim TPLT; Ghifile; END. b. Bi u di n đ th b ng danh sách c nh Ma tr n c a chúng ta ( ví d trên) đư c vi t dư i d ng: 2 3 4 9 Trang 39
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 1 3 0 1 2 3 4 2 4 0 2 1 3 1 3 0 3 2 4 8 0 0 4 1 3 7 9 0 5 8 6 9 0 6 7 9 5 0 0 7 6 9 6 7 0 85 9 6 7 a[i,9] là s lư ng các đ nh k v i đ nh i; a[i,j] chính là các đ nh k v i các đ nh i (j=1,2,3, ) Khi đĩ th t c Docfile đư c vi t l i như sau: Procedure Docfile; Var i,j,t: integer; f: text; Begin Assign(f,’dothi.txt’);reset(f); Readln(f,N); For i:=1 to sotp do Bengin Read(f,t); While not eoln(f) do Begin Read(f,t); Trang 40
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Inc(j); a[i,j]:=t; End; a[i,0]:=j; End; Close(f); End; Th t c Ghifile và thuc t c TimTPLT khơng cĩ gì thay đ i Th t c TimTPLT thay đ i như sau: Procedure TimLT (k:integer); Var i: integer; Begin Lt[k]:=sotp; For i:=1 to a[k,0] do If lt[a[k,i]]=0 then TimLT(a[k,i]); End; Bài 3 ð bài : Thu t tốn tìm đư ng đi theo chi u sâu (thu t tốn duy t theo chi u sâu).Tìm đư ng đi gi a hai đ nh xp và kt trên đ th G vơ hư ng và khơng cĩ tr ng s . Phân tích bài tốn : Trang 41
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Thu t tốn c a bài tốn này cũng gi ng như thu t tốn tìm thành ph n liên thơng c a đ th . Trong ph n C u trúc d li u cĩ dùng m ng trư c đ lưu đư ng đi t đ nh xp đ n đ nh kt. Chương trình minh h a : Program Duyetchieusau; Const Nmax=100; Type Mang=array[1 Nmax] of integer; Matran= array[1 Nmax,1 Nmax] of integer; Var a:Matran; so,duong:mang; N:integer; (*th t c đ c t p và ghi t p gi ng như bài trư c ch đ c thêm hai đ nh xp và kt *) Procedure Duyet (k:integer); Var i:integer; Begin For i:=1 to N do (*Duy t các đ nh k v i k *) lf (a[i,k]=1)and(truoc[i]=0)then Begin (*ta gán đ nh đã đi trư c đ nh i là đ nh k *) Truoc[i]:=k; Duyet(i); End; End; Trang 42
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Procedure Duyetsau; Var i:integer; Begin For i:=1 to N do truoc[i]:=0 Truoc[xp]:= 1; Duyet(xp); End; Procedure Timduong; (*th t c này gi ng th t c tìm ngư c trong duy t chi u r ng, nhưng ch tìm m t đư ng đi ng n nh t trong r t nhi u đư ng đi ng n nh t t xp đ n kt *). Var i,u: integer; Begin sold:=0; u:=kt; REPEAT Inc(sold); Duong[sold]:=u; U:=truoc[u]; UNTIL u= 1; End; BEGIN Doctiep; Duyetsau; Timduong; Trang 43
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Ghitep; END. Bài 4 ð bài : Thu t tốn tìm đư ng đi theo chi u r ng (thu t tốn duy t theo chi u r ng). Cho đ th vơ hư ng G=(X,E). Hãy tìm đư ng đi ng n nh t gi a 2 đ nh xp và kt cho trư c (đư ng đi ng n nh t là xích cĩ 2 đ u là xp và kt và đi qua ít cung ho c ít đ nh nh t). Phân tích bài tốn S d ng hàng đ i đ gi i quy t bài tốn này. Cách đưa m t đ nh c a đ th và l y 1 đ nh ra s d ng ph i tuân theo m t quy t c nh t đ nh. S d ng m t m ng đánh d u đư ng đi truoc: array[1 Nmax] of integer Khi đi t đ nh xp mà mu n cĩ đư ng đi ng n nh t đ n u thì ta ph i qua đ nh truoc [u], mu n cĩ đư ng đi ng n nh t đ n truoc [u] thì ta ph i đi qua truoc [ truoc [u] ], Yêu c u: Sau th t c duy t theo chi u r ng thì ta ph i tìm đư c m ng truoc. Kh i t o giá tr ban đ u c a m ng truoc b ng 0. B1: Kh i t o hàng đ i. ðưa xp vào hàng đ i. Gán truoc [xp]: = 1 B2: REPEAT L y 1 đ nh ra kh i hàng đ i. Gi s đ nh u. Duy t nh ng đ nh k v i u, gi s duy t đ n đ nh v. N u trư c [v] = 0 thì ta đưa v vào hàng đ i đ ng th i gán truoc [v]: = u. Nghĩa là mu n đi qua v thì ph i đi qua đ nh trư c đĩ là u; B3: Ki m tra v cĩ ph i là kt hay khơng, n u cĩ thì thốt kh i th t c; N u truoc [v] 0 Trang 44
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Hàng đ i r ng nghĩa là khơng cịn đ nh nào trong hàng đ i. Trên đây là sư n c a th t c duy t chi u r ng, n u sau nh ng bư c này mà truoc [kt] = 0 nghĩa là khơng t n t i đư ng đi t xp đ n kt. B4: (Tim đư ng đi thơng qua m ng truoc) Dùng m t m ng duong : array [1 Nmax] of integer đ bi u di n các đ nh n m trên đư ng đi. M ng này th hi n đư ng đi ngư c t kt v xp. Do đĩ khi in k t qu ra màn hình ta ph i in ngư c t cu i m ng. Kh i đ u u: = kt; sold: = 0 (s lư ng đ nh trên đư ng đi kh i đ u b ng 0) REPEAT Tăng sold lên 1 đơn v gán duong [sold]: = u; đi ngư c l i bư c trư c u: = truoc [u]; UNILT u = 1 B5: In k t qu . Thu t tốn hơi khĩ hi u. B n s th y rõ trong ph n cài đ t chương trình. C u trúc d li u M ng 2 chi u a (ij) bi u di n ma tr n liên thu c các đ nh và các cung c a đ th . M ng truoc và m ng duong mơ t như trên. M ng q (quene) mơ t c u trúc c a hàng đ i. Th t c Program Duyet _chieu_rong; Const Nmax = 100; Type mang = array [1 Nmax] of integer; Trang 45
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Var q,truoc,duong:mang; A:array [1 Nmax, 1 Nmax] of byte; Sold; N,xp,kt,qf,ql: integer; (* qf queue first là con ch y đ u hàng đ i ql queue last là con ch y cu i hàng đ i*) Chương trình minh h a : Procedure Docfile; Var ij: integer; f: text; Begin Assign (f, ‘dothi.txt’); reset (f); Readln (f,N); For i:= 1 to N do Forj:= 1 to N do Read (f,a[ i j]); Close(f); Readln (f,xp,kt); End; (*Th t c kh i đ ng hàng đ i *); Procedure InitQ; Begin ql: = 1 qf: = 0 Trang 46
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 End; (*Th t c đưa m t đ nh vào cu i hàng đ i *) Prcedure Put (k:integer); Begin q[ql]: = k; inc (ql); End; (*Hàm l y m t đ nh ra kh i hàng đ i – l y đ u hàng đ i*) Function Get:integer; Begin Get:= q[qf]; inc (qf); End; (*Hàm ki m tra hàng đ i r ng hay khơng*) Function Qempty: Boolean; Begin Qempty: = (qf>ql); End; (*Th t c duy t chi u r ng *) Procedure DuyetCR; Trang 47
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Var v,u:integer; Begin InitQ ; Put (xp; Truoc [xp]: = 1; REPEAT U: = Get; (Duy t các đ nh k c a u*) For v: = 1 to N do If (a[u,v] = 1 and (truoc [v]= 0) then Beign (*N u v k v i u và chưa đi qua thì đánh d u và đưa v vào hàng đ i*) Truoc [v]: = u; Put (v); End; UNILT Qempty or (truoc [kt] <>0); End; (*Th t c tìm m ng đư ng đi t xp đ n kt d ng ngư c *) Procedure Timduong ; Var u:integer; Begin sold: = 0; u:= kt; REPEAT Trang 48
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 inc (sold); Duong[sold]:=u; u:=truoc[u]: UNILT u = xp; End; (*Th t c in k t qu ra màn hình *) Procedure Inkq ; Var i:integer; Begin If truoc[kt]= 0 then Writeln (‘khong co duong di tư ‘,xp, ‘den’, kt) else Begin Writeln (‘Duong di tư ‘, xp, ‘den’, kt); (*Khi in ph i in ngư c m ng đư ng t sold tr v 1*) For i: = sold downto 1 do Write (duong[i], ‘ ‘); End; Realn; End; BEGIN Docfile; Trang 49
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Duyet CR; (*Ch c ch n r ng n u cĩ đư ng đi đ n đ nh kt thì ta m i tìm m ng đư ng *) If truoc[kt]<>0 then Timduong; Inkq; END. d. Bài t p t gi i Trang 50
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 7: Cây và cây khung M c tiêu M c tiêu c a bài này ngư i h c cĩ kh năng: Xác đ nh đư c m t đư ng đi, m t chu trình trong đ th b t kỳ. Bi u di n đ th trên máy tính b ng các phương pháp khác nhau. Áp d ng đư c thu t tốn Kruskal và Prim đ tìm cây khung nh nh t ng v i m t đ th xác đ nh. Cài đ t đư c thu t tốn. Phân tích đư c bài tốn th c t tương ng ph n lý thuy t đã h c. Sinh viên cĩ kh năng t h c. a. Nh c l i lý thuy t Các đ nh nghĩa: đ th , c nh, cung, đ nh k , cây, cây khung. Các phương pháp bi n di n đ th trên máy tính ð nh lý 3.4.2: Cho T là m t đ th cĩ n ≥ 2 đ nh. Các đi u sau là tương đương: 1) T là m t cây. 2) T liên thơng và cĩ n −1 c nh. 3) T khơng ch a chu trình và cĩ n −1 c nh. 4) T liên thơng và m i c nh là c u. 5) Gi a hai đ nh phân bi t b t kỳ c a T luơn cĩ duy nh t m t đư ng đi sơ c p. 6) T khơng ch a chu trình nhưng khi thêm m t c nh m i thì cĩ đư c m t chu trình duy nh t. Bài tốn cây khung nh nh t Thu t tốn Kruskal v i ý tư ng “ch n d n” B1: Ch n c nh tr ng s nh nh t B2: Ch n c nh tr ng s nh nh t trong các c nh cịn l i B3: Ch n c nh tr ng s nh nh t trong các c nh cịn l i, mà ko t o thành chu trình. Trang 51
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 L p l i bư c 3 cho t i khi ch n đư c n 1 c nh. Thu t tốn Prim v i ý tư ng “lan t a”. Gi s lan t a t đ nh A B1: Ch n c nh tr ng s nh nh t thu c A (t c cĩ 1 đ u là đ nh A) Gi s là c nh (A,B) B2: Ch n c nh tr ng s nh nh t trong các c nh cịn l i thu c A ho c B (t c cĩ 1 đ u là đ nh A ho c B). Gi s là c nh (C,B) ho c (C,A) B3: Ch n c nh tr ng s nh nh t trong các c nh cịn l i thu c A ho c B ho c C, mà ko t o thành chu trình. L p l i bư c 3 cho t i khi ch n đư c n 1 c nh. b. ð bài t p Bài t p 1 : Cho đ th vơ hư ng cĩ tr ng s sau: Bi u di n đ th d ng ma tr n k , danh sách c nh(cung), danh sách lien k t. Áp d ng thu t tốn Prim( xu t phát t i đ nh 1) ho c Kruskal tìm cây khung nh nh t cho đ th trên. Bài 2 Áp d ng thu t tốn Kruskal đ tìm cây khung nh nh t c a đ th cho trong hình dư i đây: Trang 52
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 c. Hư ng d n gi i Bài t p 1 : Thu t tốn Prim v i ý tư ng “lan t a”, xu t phát t đ nh 1 “lan t a” ta cĩ các c nh t o thành cây khung nh nh t l n lư t là: (1,5); (5,4);(4,2) và (4,3) G i V(E) là t p các đ nh(c nh) c a đ th , Vt(Et) là t p các đ nh(c nh) c a cây khung nh nh t c n tìm. Thu t tốn Prim v i các bư c th t đư c miêu t trong b ng sau: Bư c E Et Vt Kh i {} {1} t o 1 {(1,5)} {1,5} 2 { (1,5); (5,4); } {1,5,4} 3 { (1,5); (5,4);(4,2) } {1,5,4,2} 4 { (1,5); (5,4);(4,2) và {1,5,4,2,3}=V => d ng (4,3) } Chú ý: Thu t tốn Kruskal v i ý tư ng “ch n d n” các đ nh cĩ tr ng s nh nh t trong các c nh cịn l i, n u ko t o thành chu trình. Quá trình l p l i cho t i khi ch n đư c n 1 c nh. Trang 53
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Các c nh đư c ch n đ t o thành cây khung nh nh t l n lư t là: (2,4);(4,5);(4,3) và (1,5) Thu t tốn Prim v i ý tư ng “lan t a”, xu t phát t đ nh 4 “lan t a” ta cĩ các c nh t o thành cây khung nh nh t l n lư t là: (4,2);(4,5);(4,3) và (1,5) V i các bư c th t (t làm) Bài 2: Bư c kh i t o. ð t T:=Ỉ . S p x p các c nh c a đ th theo th t khơng gi m c a đ dài ta cĩ dãy: (3,5) , (4,6) , (4,5) , (5,6) , (3,4) , (1,3) , (2,3) , (2,4) , (1,2) dãy đ dài tương ng c a chúng 4, 8, 9, 14, 16, 17, 18, 20, 23. ba l n g p đ u tiên ta l n lư t b sung vào t p T các c nh (3,5) , (4,6) , (4,5). Rõ ràng n u thêm c nh (5,6) vào T thì s t o thành 2 c nh (4,5), (4,6) đã cĩ trong T chu trình. Tình hu ng tương t cũng x y ra đ i v i c nh (3,4) là c nh ti p theo c a dãy. Ti p theo ta b sung c nh (1,3), (2,3) vào T và thu đư c t p T g m 5 c nh: T = { (3,5) , (4,6) , (4,5) , (1,3) , (2,3) } Chính là t p c nh c a cây khung nh nh t c n tìm. d. Bài t p t gi i Bài t p 1: Bi u di n đ th d ng ma tr n k , danh sách c nh(cung), danh sách lien k t. Áp d ng thu t tốn Prim và Kruskal tìm cây khung nh nh t cho đ th sau: Trang 54
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài t p 2 : M ng an tồn Cho m t m ng N (N <= 20) máy tính đư c đánh s t 1 đ n N. Sơ đ m ng đư c cho b i h g m M kênh (đo n) n i tr c ti p gi a m t s c p máy trong m ng, m kênh tương ng v i m c p. Cho bi t chi phí truy n 1 đơn v thơng tin theo m i kênh c a m ng. Ngư i ta c n chuy n m t b c thơng đi p t máy s đ n máy t. ð đ m b o an tồn, ngư i ta chuy n b c thơng đi n này theo hai đư ng truy n tin khác nhau (t c khơng cĩ kênh nào) c a m ng đư c s d ng trong c hai đư ng truy n tin; cho phép hai đư ng truy n tin cùng đi qua m t s máy tính). Chi phí c a m t đư ng truy n đư c hi u là t ng chi phí trên các kênh c a nĩ. ðơn giá đư ng truy n t máy s sang máy t đư c tính như sau: V i hai máy s và t, cùng b c thơng đi p cĩ đ dài là 1 đơn v thơng tin, đơn giá truy n cho c p (s, t) đư c tính b ng t ng chi phí chuy n thơng đi p an tồn (b ng t ng chi phí c a hai đư ng truy n tin) là nh nh t. M ng truy n tin nĩi trên th a mãn tính ch t an tồn theo nghĩa là t m t máy b t kỳ luơn truy n đư c (m t cách an tồn) thơng đi p t i m t máy b t kỳ khác. Khi m t m ng an tồn, ngư i ta tính đư c đơn giá c a m ng là t ng đơn giá m i đư ng truy n t m t máy b t kỳ t i m t máy b t kỳ khác. Trang 55
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Ma tr n đơn giá c a m ng là m ng hai chi u A cĩ N dịng và N c t, mà giá tr ph n t A[i, j] chính là đơn giá t máy i sang máy j. Câu 1: Cho trư c m t m ng, hãy ki m ra tính an tồn c a m ng đĩ. Câu 2: Khi m ng khơng an tồn đư c phép b sung m t s kênh truy n đ nĩ tr thành an tồn. ðơn giá m i kênh truy n b sung theo đư c coi b ng hai l n giá tr c c đ i đơn giá các kênh đã cĩ. M i kênh b sung đư c coi cĩ đơn giá như nhau. Hãy tìm cách b sung các kênh m i mà đơn giá m ng là nh nh t. Câu 3: Khi m ng an tồn ho c sau khi b sung kênh đ m ng an tồn, hãy in ra đơn giá m ng và ma tr n đơn giá. D li u vào: cho trong file INP.B2 v i c u trúc như sau: Dịng đ u tiên ghi 2 s n, m cách nhau b i d u cách. M i dịng th i trong s m dịng ti p theo ghi thơng tin v kênh n i th i c a m ng g m 3 s d[i], c[i], g[i] trong đĩ d[i], c[i] là ch s c a hai máy tương ng v i kênh này và g[i] (nguyên dương) là chi phí đ truy n m t đơn v thơng tin t máy d[i] đ n máy c[i] theo kênh này. Các giá tr g[i] cho trư c khơng vư t quá 40 (và như v y đơn giá các kênh b sung khơng vư t quá 80). K t qu : ghi ra file OUT.B2 theo qui cách sau: Dịng đ u tiên ghi 1 s nguyên p th hi n m ng cĩ an tồn hay khơng và p cĩ ý nghĩa là s lư ng kênh c n b sung. p=0 cĩ nghĩa m ng an tồn; p>0 cĩ nghĩa m ng khơng an tồn và c n b sung p kênh n a đ m ng an tồn v i chi phí b sung ít nh t. p dịng ti p theo ghi p kênh b sung. Cách ghi như trong file d li u vào. Dịng ti p theo ghi đơn giá c a m ng an tồn. N dịng ti p theo ghi ma tr n đơn giá c a m ng an tồn: m i hàng c a ma tr n ghi trên m t dịng. Bài t p 3: Xây d ng đư ng ng nư c Cĩ 1 tr m c p nư c và N đi m dân cư. Hãy xây d ng chương trình thi t k tuy n đư ng ng nư c cung c p đ n m i nhà sao cho t ng chi u dài đư ng ng ph i dùng là ít nh t. Gi s r ng các đư ng ng ch đư c n i gi a 2 đi m dân cư ho c gi a tr m c p nư c v i đi m dân cư. Trang 56
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 8: Th o lu n v cài đ t thu t tốn tìm cây khung nh nh t trên đ th M c tiêu Cài đ t đư c thu t tốn xây d ng t p các chu trình cơ b n. Cài đ t đư c thu t tốn Prim, Kruskal đ đưa ra cây khung nh nh t c a đ th cho trư c. M r ng ý tư ng, m r ng thu t tốn Prim. Cài đ t đư c thu t tốn xây d ng t p các chu trình cơ b n. Phân tích đư c bài tốn th c t tương ng ph n lý thuy t đã h c. Sinh viên cĩ kh năng t h c. Rèn luy n tư duy sáng t o. a. Nh c l i lý thuy t b. ð bài t p Bài 1 Tìm cây bao trùm nh nh t c a đ th G dung thu t tốn Kruskal Bài 2 Tìm cây bao trùm nh nh t c a đ th G dung thu t tốn Prim c. Hư ng d n gi i Bài 1 ð bài : Tìm cây bao trùm nh nh t c a đ th G Phân tích bài tốn : Trư c h t ta ph i xét ví d sau: 8 3 2 1 7 2 3 7 5 1 8 Trang 57
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 2 1 4 1 7 6 6 1 9 Tư tư ng c a thu t tốn là đưa t ng c nh vào cây b t đ u t nh ng c nh cĩ tr ng s nh nh t và làm cho đ n khi cây bao g m t t c các đ nh c a đ th . Gi s T là cây bao trùm c n tìm. Và t p V là t p bao g m các t p Gi cĩ tính ch t như sau: G i cĩ ph n t là các đ nh c a đ th mà chúng đư c n i v i nhau b i các c nh đã đư c đưa vào T. T m t đ nh thu c G i luơn cĩ đư ng đi đ n m t đ nh khác cũng thu c G i. Giao c a G i và G J b ng r ng. V i đ nh nghĩa như trên ta nh n th y rõ ràng r ng m i m t t p G i thu c t p V là m t cây bao trùm con nh nh t. Như v y thu t tốn c a chúng ta như m t bài tốn quy n p là g p nhưng cây bao trùm này thành nh ng cây trùm l n hơn cho đ n khi nĩ g m t t c các đ nh c a đ th và đương nhiên ta ph i n i nh ng cây bao trùm G i này b ng nh ng c nh cĩ tr ng s nh nh t. K t thúc khi V = { {1,2,3 ,n} } = {X}; Ban đ u: + Cây bao trùm c a đ th là r ng nghĩa là chưa cĩ c nh nào đư c đưa vào cây bao trùm. (T = ). + G i chính là nh ng đ nh c a đ th => V = { {1}, {2}, {3} ,{n} } Thu t tốn đư c vi t c th v i ví d trên như sau: Kh i t o T = { } V = { {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9} } ðưa c nh nh nh t (1,2) vào cây khi đĩ 1 đư c n i v i 2 nên thay {1} và {2} trong V b ng {1,2} Trang 58
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 T = { (1,2) } V = { {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9} } ðưa c nh (4,5) vào cây: T = { (1,2); (4,5)} V = { {1,2}, {3}, {4,5}, {5}, {6}, {7}, {8}, {9} } ðưa c nh (5,6) vào cây: T = {(1,2); (4,5); (5,6)} V = { {1,2}, {3}, {4,5,6}, {7}, {8}, {9} } ðưa c nh (6,9) vào cây: T = {(1,2); (4,5); (5,6); (6,9)} V = { {1,2}, {3}, {4,5,6,9}, {7}, {8} } ðưa c nh (1,4) vào cây: T = {(1,2); (4,5); (5,6); (6,9); (1,4)} V = { {1,2,4,5,6,9}, {3}, {7}, {8} } ðưa c nh (5,7) vào cây: T = {(1,2); (4,5); (5,6); (6,9); (1,4); (5,7)} V = { {1,2,4,5,6,9}, {3}, {8} } ðưa c nh (3,5) vào cây: T = {(1,2); (4,5); (5,6); (6,9); (1,4); (5,7); (3,5)} V = { {1,2,3,4,5,6,7,9}; {8} } ðưa c nh (7,8) vào cây: T = {(1,2); (4,5); (5,6); (6,9); (1,4); (5,7); (3,5); (7,8)} V = { {1,2,3,4,5,6,7,8,9} } K t thúc vì V = {X}; Trang 59
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Chú ý: Th t ch n các c nh đưa vào cây là ưu tiên các c nh cĩ tr ng s bé hơn. C u trúc d li u Ta bi u di n đ th dư i d ng li t kê các cung (ch áp d ng cho đ th nh ) Như v y dung m t m ng hai chi u: e: array [1 Emax, 1 3] of Integer v i e [i,3] là tr ng s c a cung (e[i,1], e[i,2], ,emax) M ng T: array [1 Emax, 1 2] of Integer bi u di n các c nh đư c đưa vào T. Dùng bi n solT đ xác đ nh s lư ng c nh đã đưa vào cây T; (kh i t o solT: = 0 nghĩa là cây T = ) Bi u di n V là t p h p c a các t p h p r t ph c t p, do đĩ ta dùng m t C u trúc d li u đơn gi n đ mơ ph ng t p V như sau: M ng tap V: array[1 Nmax] of integer Trong đĩ hai đ nh i và j thu c cùng m t t p G k nào đĩ n u như tap V[i] = tap [j] Như v y ban đ u giá tr c a m ng tapV là tapV[i] gán b ng i; m i bư c khi ta ghép các đ nh c a 2 t p G k và G h thành m t t p thì ta ch vi c gán c các giá tr c a t p G k b ng giá tr c a t p G h. Ví d v i N = 10; m t bư c nào đĩ m ng tapV = [ 1,2,2,6,6,2,1,4,4,10] ta hi u là V = { {1,7}; {2,3,6}, {4,5}, {8,9}, {10} } đ n bư c ti p theo ta đưa c nh (4,6) vào cây nghĩa là c n g p 2 t p {2,3,6 }và {4,5} thành m t. Ta gán tapV[4] = tapV[2;] tapV[5] = tapV[2;]; Khi đĩ m ng tapV = [1,2,2,2,2,2,1,4,4,10] ði u này r t cĩ l i khi ta g p hai t p h p con v i nhau. Trang 60
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 V i tồn b d li u đư c mơ t như trên ta cĩ ph n cài đ t chương trình: Chương trình minh h a : Program kruskal; Const Nmax = 100; Emax = 1000; Type mangcanh = array [1 Emax, 1 2] of integer; Dinh = array [1 Nmax] of integer; Var e,T; Mangcanh; TapV: Dinh; N, solE, solT: integer; (*solE là s c nh c a đ th cịn solT là s c nh đư c đưa vào T*) Prrocudure Doctep; (* D li u vào g m cĩ: Dịng đ u tiên ch a s N T dịng th hai tr đi m i dịng ch a 3 s nguyên là 2 đ nh c a m t c nh và tr ng s c a c nh đĩ. *) Var f: text; i,j,k: integer; Begin Assign (f’, cung.txt’); Reset(f); Readln (F,N); SolE: = 0; While not eof(f) do Trang 61
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 begin Read (f,i,j,k); Inc(solE); e[solE,1]: = i; e[solE,2]: = j; e[solE,3]: = k; End; Close (f); End; Procedure Sapxep; (*Dùng phương pháp s p x p n i b t đ s p x p các c nh theo th t tr ng s t nh t i l n(*) Var ij : integer; Beign For i:= 1 to solE 1 do For j:= i + 1 to solE do If e[i,3] > e[j,3] then Doicho(i,j); End; Procedure Doicho (i,j;integer); Var temp: integer; Begin Temp: = e[i,1]; Trang 62
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 e[i,1]: = e[j,1]; e[j,1]: Temp; Temp: = e[i,2]; e[i,2]: = e[j,2]; e[j,2]: = Temp; Temp: = e[i,3]; e[i,3]: = e[j,3]; e[j,3]: = Temp; End; Procedure TimCay: Var i,k, temp:integer; Begin solT: = 0; (*T = *) For i: = 1 to N do TapV [i]: = i; K: = 0; While (not KttapV) and (K tapV [e [k,2] ] then (* N u 2 đ nh e[k,l] và e[k,2] chưa thu c cùng 1 cây con thì ta m i đưa vào cây T Trang 63
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 và th c hi n ti p. Ngư c l i thì b qua c nh này đ tránh t o thành chu trình trong cây*) Begin Inc(solT); T [solT,1]: = e[k,1]; T [solT,2]: = e[k,2]; (* ð ng nh t giá tr trong 2 t p con ch a 2 đ nh e[k,1] và e[k,2] c a V*). ðưa c nh vào cây khung. temp: = tapV [ e[k,2] ]; For i: = 1 to N do If tapV [i] = temp then TapV [i]: = TapV [ e[i,2] ]; End; End; End; Function KTtapV: Boolean; (*Hàm ki m tra xem các giá tr c a t p V cĩ b ng nhau hay khơng*) Var i: integer; Begin KTtapV: = True; For i: = 2 to N do If tapV [i] <> tapV [i] then Begin KTtapV: = False; Exit; Trang 64
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 End; End; Procedure GhiTep; (*Ta ch vi c đưa cây T ra màn hình*) Var i: integer; begin Writeln (‘ Cac cung thuoc cay bao trum nho nhat T la:’) For i: = 1 to solT do Writeln (T [i, l]; ‘ ‘; T[i,2]; Readln; End; BEGIN DocTep; Sapxep; TimCay; GhiTep; END. Bài 2 ð bài : Tìm cây bao trùm nh nh t c a đ th G Phân tích bài tốn : Gi s T là cây bao trùm t i thi u c n xây d ng. Gi x ta b t đ u t đ nh u. G i U là t p các đ nh k v i các đ nh cĩ cung n i v i cây T; Kh i t o U = u; Trang 65
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 T = ; B1: Ch n (u,v) là c nh cĩ tr ng s bé nh t v i u B2: ðưa đ nh v vào t p U; B3: N u U = X thì k t thúc; ngư c l i thì quay l i bư c 1; C u trúc d li u Ta bi u di n đ th dư i d ng li t kê các cung (ch áp d ng cho đ th nh ) Như v y dung m t m ng hai chi u: e: array [1 Emax, 1 3] of Integer v i e [i,3] là tr ng s c a cung (e[i,1], e[i,2], ,emax) M ng T: array [1 Emax, 1 2] of Integer bi u di n các c nh đư c đưa vào T. Dùng bi n solT đ xác đ nh s lư ng c nh đã đưa vào cây T; (kh i t o solT: = 0 nghĩa là cây T = ) Bi u di n V là t p h p c a các t p h p r t ph c t p, do đĩ ta dùng m t C u trúc d li u đơn gi n đ mơ ph ng t p V như sau: M ng tap V: array[1 Nmax] of integer Trong đĩ hai đ nh i và j thu c cùng m t t p G k nào đĩ n u như tap V[i] = tap [j] Như v y ban đ u giá tr c a m ng tapV là tapV[i] gán b ng i; m i bư c khi ta ghép các đ nh c a 2 t p G k và G h thành m t t p thì ta ch vi c gán c các giá tr c a t p G k b ng giá tr c a t p G h. Ví d v i N = 10; m t bư c nào đĩ m ng tapV = [ 1,2,2,6,6,2,1,4,4,10] ta hi u là V = { {1,7}; {2,3,6}, {4,5}, {8,9}, {10} } đ n bư c ti p theo ta đưa c nh (4,6) vào cây nghĩa là c n g p 2 t p {2,3,6 }và {4,5} thành m t. Ta gán tapV[4] = tapV[2;] Trang 66
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 tapV[5] = tapV[2;]; Khi đĩ m ng tapV = [1,2,2,2,2,2,1,4,4,10] ði u này r t cĩ l i khi ta g p hai t p h p con v i nhau. T p U là t p các đ nh cĩ cung n i v i T, khai báo T,X: set of 1 Nmax; Các thành ph n d li u khác khai báo gi ng như ph n trư c. Program Prim; Const Nmax = 100; Emax = 1000; Type mangcanh = array [1 Emax, 1 3]of integer; Tap = set of 1 Nmax; Var e,T: Mangcanh; VT X: Tap; {X: T p đ nh c a đ th ; V T: T p đ nh c a cây} N, solE, solT: integer; (*Th t c đ c file và ghi file tương t như trên*) Procedure Timcay; Var k,i,j: integer; TrongsoMin: Longint; Begin solT: = 0; V T = [xp] X: = [ ]; For i: = 1 to N do X: = X + [i]; Trang 67
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 REPEAT (*Tìm c nh (u,v) sao cho u và cĩ tr ng s nh nh t *) TrongsoMin: = MaxLongint; For k: = 1 to solE do Begin If (e[k,l] in V T and not e[k,2] in V T and (e[k,3] < TrongsoMin) then Begin i: = e[k,1]; j: = e[k,2]; TrongsoMin: = e[k,3; End; If not e[k,1] in V T and (e[k,2] in V T and (e[k,3] < TrongsoMin) then Begin i: = e[k,2]; j: = e[k,1]; TrongsoMin: = e[k,3]; End; (*ðưa j vào t p U*) vT = V T + [j]; (*ðưa c nh (i,j) vào cây T*) inc(solT); Trang 68
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 T [solT,1]: = i; T [solT,2]: = j; UNILT U = X; End; BEGIN Docfile; Timcay; Ghifile; END. d. Bài t p t gi i Trang 69
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 9, 10: Bài tốn tìm đư ng đi ng n nh t M c tiêu M c tiêu c a bài này ngư i h c cĩ kh năng: Bi u di n đ th trên máy tính b ng các phương pháp khác nhau. Áp d ng đư c thu t tốn ford bellman và dijkstra tìm đư ng đi ng n nh t ng v i m t đ th xác đ nh. Cài đ t đư c thu t tốn. Phân tích đư c bài tốn th c t tương ng ph n lý thuy t đã h c. Sinh viên cĩ kh năng t h c. a. Nh c l i lý thuy t Thu t tốn dijkstra v i ý tư ng “lan t a” và lưu 1 ch s t i m i đ nh. ð tìm l i đư ng đi ng n nh t, ta lưu c tên đ nh li n k trư c nĩ trên đư ng đi ng n nh t. b. ð bài t p Bài t p 1: Bi u di n đ th d ng ma tr n k , danh sách c nh(cung). Áp d ng thu t tốn Dijkstra tìm đư ng đi ng n nh t t đ nh 5 t i các đ nh cịn l i cho đ th sau: Bài2 Tìm đư ng đi ng n nh t t 1 đ n các đ nh cịn l i c a đ th Trang 70
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 3 ðưa thư Nhà bác đưa thư cĩ vi c b n, bác đưa thư r t s t ru t mu n v nhà ngay nhưng bác ph i đưa m t thư quan tr ng cho anh B qu n Ba ðình. Hi n t i bác qu n Thanh Xuân. ðư ng đi t ch bác t i nhà anh B ph i đi qua m t s qu n huy n khác v i kho ng cách gi a các qu n như sau. Hãy giúp bác đưa thư tìm đư ng đi ng n nh t v i th i gian ít nh t đ bác cĩ th v nhanh chĩng gi i quy t cơng vi c gia đình. Bài 4 H b t m i M t con h đ ng trên đ i cao nhìn xu ng khu r ng và phát hi n ra 5 con m i 5 v trí khác nhau. Con h mu n b t con Nai trong s 5 con v t đĩ là Nai, Gà, Hươu, Th , Bị đ ăn th t. Khi con H mu n b t con Nai đĩ, nĩ ph i ch y qua đư ng mà 4 con v t cịn l i đang đ ng. V trí và kho ng cách mà các con v t đư c bi u di n như sau. Tìm đư ng đi đ quãng đư ng mà con H ph i ch y là ng n nh t đ b t đư c con Nai. Bài 5 Mèo b t chu t Mèo Tom(1) rình chú chu t nh Jeny(4) đang ăn tr m phomat. T ch Tom đ n Jeny cĩ cái xơ nư c(2), ch u cây c nh (3), gh sofa(5) v i th i gian đ Tom ch y đ n các đ v t trên và gi a các đ v t cũng như th i gian Tom ch y t các đ v t đ n Jeny như sau: xơ nư c ch u cây c nh Trang 71
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Tom Jeny gh sofa Tom cĩ th ch y đ n n p ch các đ v t trên đ rình và b t Jeny. Tìm th i gian nh nh t đ Tom ch y đ n b t Jeny mà khơng b Jeny phát hi n(nh n p vào các đ v t cĩ trên đư ng đi) Bài 6 Cho đ th cĩ tr ng s G = (X,E). Tìm đư ng đi ng n nh t gi a 2 đ nh xp và k t thúc c a đ th c. Hư ng d n gi i Bài 1: Bi u di n đ th d ng ma tr n k như sau: 0 18 M 13 12 18 0 11 3 M M 11 0 5 9 13 3 5 0 4 12 M 9 4 0 Dùng thu t tốn Dijkstra gi m tr ng s 1 l n t i m i đ nh ta cĩ: Kí hi u: Trang 72
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 D[i] : Ch s t i đ nh i (T ng tr ng s t đ nh xu t phát t i đ nh i, đư c c p nh t theo t ng bư c c a thu t tốn) T[i] : Tên đ nh k ngay trư c đ nh i trên đư ng đi ng n nh t đư c c p nh t theo t ng bư c c a thu t tốn Bư c ð nh 5 Các đ nh D[1],T[1] D[2],T[2] D[3],T[3] D[4],T[4] đư c chưa xét ch n Kh i t o 5 1,3,4,2 12,5 ∞ 9,5 4,5 1 4 1,3,2 12.5 7,4 9,5 4,5 2 2 1,3 12,5 7,4 9,5 4,5 3 3 1 12,5 7,4 9,5 4,5 4 1 12,5 7,4 9,5 4,5 Trong đĩ, bư c kh i t o đư c cho trong dịng đ u tiên. Th c hi n bư c 1, trong D[v], v i v=1, 2, 3, 4 dịng đ u tiên, thì D[4 ] = 4 là nh nh t nên đ nh 4 đư c ch n. Ta xác đ nh l i các D[v] cho các đ nh cịn l i 1, 2 và 3. Ch cĩ D[2] là nh đi và D[2] = 7, vì D[4] + c(4,2) = 4 + 3 = 7 < ∞. Ti p t c th c hi n các bư c 2, 3, 4 ta thu đư c đ dài đư ng đi ng n nh t t đ nh 0 t i các đ nh 1, 2, 3, 4 đư c cho dịng cu i cùng trong b ng, ch ng h n đ dài đư ng đi ng n nh t t 5 t i 2 là D[2] = 7 và đĩ là đ dài c a đư ng đi 5 42. Bài2 Tìm đư ng đi ng n nh t t 1 đ n các đ nh cịn l i c a đ th Trang 73
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 K t qu tính tốn theo thu t tốn đư c trình bày theo b ng dư i đây: Quy ư c vi t hai thành ph n c a nhãn theo th t d[v]. ð nh đư c đánh d u * là đ nh đư c ch n đ c đ nh nhãn bư c l p đang xét, nhãn c a nĩ khơng bi n đ i các bư c ti p theo, vì th ta đánh d u ( ). Bư c l p ð nh 1 ð nh 2 ð nh 3 ð nh 4 ð nh 5 ð nh 6 Kh i 0, 1 1, 1 * ∞, 1 ∞, 1 ∞, 1 ∞, 1 1 6, 2 3, 2 * ∞, 1 8, 2 2 4, 4 * 7, 4 8, 2 3 7, 4 5, 3 * 4 6, 6 * Bài 3 Nhà bác đưa thư cĩ vi c b n, bác đưa thư r t s t ru t mu n v nhà ngay nhưng bác ph i đưa m t thư quan tr ng cho anh B qu n Ba ðình. Hi n t i bác qu n Thanh Xuân. ðư ng đi t ch bác t i nhà anh B ph i đi qua m t s qu n huy n khác v i kho ng cách gi a các qu n như sau Trang 74
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Hãy giúp bác đưa thư tìm đư ng đi ng n nh t v i th i gian ít nh t đ bác cĩ th v nhanh chĩng gi i quy t cơng vi c gia đình. *Phân tích bài tốn: Bác đưa thư c n chuy n thư t qu n Thanh Xuân t i Qu n Ba ðình nhưng l i khơng cĩ đư ng đi tr c ti p t qu n Thanh Xuân t i qu n Ba ðình mà ph i đi qua m t s qu n khác. V i đi m xu t phát là qu n Thanh Xuân tìm các con đư ng cĩ th đi t i qu n Ba ðình và tính kho ng cách gi a hai qu n đĩ khi đi qua các con đư ng khác nhau. Ta tính kho ng cách t Qu n Thanh Xuân (Q.TX) t i các Q.Thanh Trì (Q.TT), Q.Hồng Mai (Q.HM), Q.Tây H (Q.TH), Q.Hà ðơng (Q.Hð). Ta th y khơng cĩ đư ng đi tr c ti p t Q.Thanh Xuân đ n Q.Hà ðơng, nên cịn 3 s l a ch n là đi qua Q.TT, Q.HM và Q.TH. Ta cĩ kho ng cách tương ng là: Q.TX Q.TT = 1km; Q.TX Q.HM = 7km; Q.TX Q.TH = 6km; NX: Quãng đư ng t Q.TX đ n Q.TT ng n nh t v i 1km. V y ta s ch n và đánh d u l i đi này. Ti p t c tính đư ng đi t Q.TT đ n Q.HM, Q.TH, Q.H ð và Q.B ð. Ta cĩ: Q.TT Q.HM = ∞; Q.TT Q.TH = 3km; Q.TT Q.Hð = 4km; Trang 75
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Q.TT Q.Bð = 1km; NX: Quãng đư ng t Q.TT đ n Q.Bð là ng n nh t 1km và là đích c a chuy n đi. V y t ng kho ng cách t Q.TX Q.Bð là 1+1=2km. Gi s các đ nh 1,2,3,4,5,6 tương ng v i các qu n Thanh Xuân, Hồng Mai, Tây H , Thanh Trì, Hà ðơng và qu n Ba ðình. Ta cĩ đ th sau: Tìm đư ng đi ng n nh t t qu n Thanh Xuân t i Ba ðình là tìm đư ng đi ng n nh t gi a t đ nh 1 t i đ nh 6 c a đ th trên. Áp d ng thu t tốn Dijkstra ta cĩ b ng sau: 1 2 3 4 5 6 Kh i t o 1,0* 1,∞ 1,∞ 1,∞ 1,∞ 1,∞ 1 1,7 1,6 1,1* 2 4,4 4,5 4,2* 3 * 6,4 4 * T b ng trên ta th y con đư ng ng n nh t đ đi t đ nh 1 t i đ nh 6 là 1 4 6 v i tr ng s là 2, nĩi cách khác bác đưa thư cĩ th đi t qu n Thanh Xuân t i qu n Thanh Trì và t i qu n Ba ðình v i quãng đư ng là 2km. Trang 76
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 4 M t con h đ ng trên đ i cao nhìn xu ng khu r ng và phát hi n ra 5 con m i 5 v trí khác nhau. Con h mu n b t con Nai trong s 5 con v t đĩ là Nai, Gà, Hươu, Th , Bị đ ăn th t. Khi con H mu n b t con Nai đĩ, nĩ ph i ch y qua đư ng mà 4 con v t cịn l i đang đ ng. V trí và kho ng cách mà các con v t đư c bi u di n như sau. Tìm đư ng đi đ quãng đư ng mà con H ph i ch y là ng n nh t đ b t đư c con Nai. *Phân tích bài tốn: Con h khơng th b t đư c t t c 5 con v t đĩ, và nĩ ch cĩ th ch n 1. Trong các con đư ng đ đi đ n ch con Nai mà nĩ mu n b t đĩ, cĩ nh ng con đư ng dài và ng n khác nhau. Nĩ ph i tính tốn sao cho quãng đư ng ch y đ n con Nai đĩ là ng n nh t đ đ phịng con v t đĩ nhìn th y t xa và b ch y. G i v trí H , Bị, Th , Hươu, Nai tương ng là 1,2,3,4 v i các đ nh c a đ th sau: ð đi t 1 đ n 5 ta tính kho ng cách t 1 đ n các đ nh cịn l i: 1 2 = 4 1 3 = ∞ Trang 77
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 1 4 = ∞ 1 5 = ∞ Ta th y cĩ đư ng đi duy nh t là 1 2. Ti p t c tính kho ng cách t 2 3, 4, 5 ta cĩ: 2 3 = 10 2 4 = 2 2 5 = 8 NX: Quãng đư ng 2 4 là nh nh t. ðánh d u và ch n con đư ng này. Khi ch n đư ng đi, n u đư ng nào đã đư c ch n và đánh d u s khơng đư c xét l i n a. V y cịn l i 2 đ nh chưa xét là 3 và 5, nhưng khơng cĩ đư ng đi tr c ti p t 4 3, ch cịn đư ng 4 5 v i kho ng cách là 1km và là m c đích c a bài tốn. KL: ðư ng đi ng n nh t t 1 5 là 1 2 4 5 v i kho ng cách là 1+4+2=7 Áp d ng thu t tốn Djstral ta cĩ b ng sau: 1 2 3 4 5 Kh i t o 1,0* 1,∞ 1,∞ 1,∞ 1,∞ 1 1,4* 2 2,14 2,6* 2,12 3 4,7* 4 Nhìn vào b ng trên ta th y đư ng đi ng n nh t t 1 đ n 5 là 1 2 4 5 v i tr ng s là 7. Nĩi cách khác con H mu n b t và ăn th t con Nai thì H ph i đi qua ch con Bị và con Hươu. Bài 5 Trang 78
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Mèo Tom(1) rình chú chu t nh Jeny(4) đang ăn tr m phomat. T ch Tom đ n Jeny cĩ cái xơ nư c(2), ch u cây c nh (3), gh sofa(5) v i th i gian đ Tom ch y đ n các đ v t trên và gi a các đ v t cũng như th i gian Tom ch y t các đ v t đ n Jeny như sau: xơ nư c ch u cây c nh Tom Jeny gh sofa Tom cĩ th ch y đ n n p ch các đ v t trên đ rình và b t Jeny. Tìm th i gian nh nh t đ Tom ch y đ n b t Jeny mà khơng b Jeny phát hi n(nh n p vào các đ v t cĩ trên đư ng đi) Bài làm: Gi s v trí các đ i tư ng tương ng v i các đ nh 1, 2, 3, 4, 5 c a đ th sau: Phân tích tương t như 2 bài tốn trên ta s tìm đư c con đư ng c n tìm Áp d ng thu t tốn Dijkstra đ tìm đư ng đi ng n nh t t 1 4 1 2 3 4 5 Kh i t o 1,0* 1,∞ 1,∞ 1,∞ 1,∞ 1 1,3* 1,12 Trang 79
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 2 2,8 2,7* 3 5,15* 4 D a vào b ng trên ta cĩ con đư ng ng n nh t là 1 – 2 – 5 4 v i th i gian là 15 Bài 6 Cho đ th cĩ tr ng s G = (X,E). Tìm đư ng đi ng n nh t gi a 2 đ nh xp và k t thúc c a đ th . Phân tích bài tốn : Phương pháp 1: T i m i đ nh th c hi n vi c gi m tr ng s nhi u l n. Bài tốn này cũng dùng m ng truoc đánh d u các đ nh trên đư ng đi như trên và dùng c u trúc hàng đ i. Cĩ m t đi m m i là nĩ c n thêm m t m ng trongso : array[1 Nmax] of (tuỳ vào bài tốn cĩ th là ki u real ho c ki u longint). Trongso [i] b ng t ng tr ng s c a các cung n m trên đư ng đi tính t đ nh xp cho đ n i. Bài tốn c a chúng ta tr thành tìm m ng trongso [i] sao cho nĩ đ t giá tr nh nh t. Thu t tốn c a ph n này r t gi ng thu t tốn duy t chi u r ng nhưng c i ti n m t chút là cĩ g n thêm m ng tr ng s . Khi duy t các đ nh k c a m t đ nh u v a l y ra kh i hành đ i, g p m t đ nh i k v i u ta khơng c n bi t truoc [i] là đ nh nào, mà ta ch quan tâm đư ng đi t u đ n i cĩ ng n hơn đư ng cũ khơng ( trongso [i]??? trongso [u] + a[u,i]. Trongso [i] chính là đư ng đi cũ đ n đ nh i, trongso [u] + a[u,i] là đư ng đi m i t đ nh u đi đ n. N u đư ng m i ng n hơn nghĩa là trongso [u] + a[u,i] < trongso [i] thì ta ghi nh n đư ng đi m i, ta ph i dán l i: trongso [i] := trongso [u] + a[u,i]; Trang 80
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 truoc [i]:= u; Thu t tốn đư c trình bày c th như sau: Kh i t o: M ng trongso [i] = Maxlongint; Truoc [xp]: = 1; Kh i đ ng hàng đ i và đưa xp vào; Th c hi n bư c l p. REPEAT L y 1 đ nh kh i hàng đ i g n vào bi n u; Duy t các đ nh i k v i u; (N u đư ng đi m i ng n hơn đư ng đi cũ thì th c hi n gi m tr ng s cho i) N u trongso[i]>trongso[u] +a[u,i] thì + trongso[i]:= trongso[u] + a[u,i]; + truoc [i]:= u; UNILT ; Chương trình minh h a : Program DIJSTRA_phuongphap1; Const Nmax = 100; Type MATRANKE = array[1 Nmax, 1 Nmax] of integer; MANG = array [1 Nmax] of Longint; Var a: MATRANKE; q, duong, truoc, trongso: MANG; Trang 81
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 N, sold, xp, kt, qf, ql: Integer; fifo: text: (*fi: file input la tep doc du lieu vao fo: file output la tep doc du lieu ra*) Procedore Doctep ; Var i,j: integer; Begin Asign (fi,’matran:inp’); Reset(fi); Readln (fi, N); For i: = 1 to N do For j: = 1 to N do Read (fi, a[i,j]); Readln (f,xp,kt); Close (f); End; Procedure InitQ: (*Thu tuc khoi dong hang doi *) Begin qf: = 0; ql:= 1; End; Trang 82
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Procedure Put (u:integer); (*Dua mot phan tu vao hang doi *) Begin Inc(ql); q[ql]: = u; End; Function Get: Integer; (*Ham lay mot phan tu ra khoi hang doi*) Begin Get:= q[qf]; inc [qf]; End; Function Qempty : Boolean; (*Ham kiem tra hang doi da rong hay chưa*) Begin Qempty:= (qf>ql); End; Procudure Dijstra (*Thu tuc duyet Dijstra theo phuong phap 1: giam trong so nhieu lan*) Var i, u: integer; Trang 83
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Begin (*cac buoc khoi tao (giong trong phan thuat toan)*) truoc[xp]:= 1; Fullhar( ) = For i:= 0 to N do Trongso[i]:= MaxLongint; Trongso[xp]:= 0; InitQ; Put(xp); (*Bat dau vong lap*) REPEAT (*Lay mot dinh khoi hang doi gan vao bien u*) u:= Get; For i:= 1 to N do (*Duyet tat ca cac dinh i cua do thi*) If (a[u,i]>=0) and (trongso [i]>trongso [u] + a[u,i]then (*Neu dinh i ke voi u va duong di cu lon hon duong di moi thi:*) Begin (* Gan lai gia tri duong di moi*) trongso [i]:= trongso [u] +a[u,i]; (*danh dau duong di moi den i qua dinh truoc do la u*) truoc [i]:= u; Put (i); End; UNILTQempty: (*Ket thuc khi khong di duoc nua*) End; Trang 84
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Procedure Timnguoc; Var u:integer; Begin sold:= 0; (*M ng đư ng r ng*) (*Ban đ u gán u b ng kt*) u:= kt; Repeat (*V i m i bư c l p ghi u vào m ng duong*) Inc(sold); duong[sold]:= u; (*Mu n đ n bư c ti p theo ph i g n u = truoc [u]*) u:= truoc[u]; Unilt u = 1; (*Ket thuc khi u:= 1 do luc truoc ta gan truoc [xp]= 1). End; procedure Ghitep : Var ij:integer; Begin Asign (fo, ‘kq.out’); Rewrite (fo); If truoc [kt] <> 0 then Begin Timnguoc ; For i:= sold downto 1 do Write (fo, duong [i], ‘ ‘)’ Trang 85
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 End else Writeln (f,0); Close (fo); End; BEGIN Doctep; Dijstra; Ghitep; END. Phương pháp 2: Gi m tr ng s 1 l n t i m i đ nh. ð làm rõ thu t tốn này ta xét ví d c th sau: G= (X,E) đưa ra hình v M ng ma tr n tr ng s như sau: 1 1 2 5 1 1 1 1 1 1 3 1 1 1 3 2 1 1 7 1 1 1 5 5 3 7 1 5 1 13 1 4 1 1 1 5 1 2 1 1 1 1 1 2 1 6 2 6 1 1 1 13 1 6 1 7 Ta tìm đư ng đi b t đ u t đ nh 1. Trang 86
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Các bư c th c hi n c a thu t tốn đ i v i ví d này như sau: (M = MaxLongint). Trình t th c hi n m i bư c t trái sang ph i. ð nh cĩ tr ng s Bư c T p A T p B M ng trongso M ng Truoc nh nh t trong B B1 [1] [2,3,4,5,6,7] [0,M,M,M,M,M,M] [ 1,0,0,0,0,0,0,] B2 [1] [2,3,4,5,6,7] [0,1,2,5,M,M,M] [ 1,1,1,1,0] B3 2 [1,2] [3,4,5,6,7] [0,1,2,4,M,M,M] [ 1,1,1,2,0,0,0] B4 3 [1,2,3] [4,5,6,7] [0,1,2,4,M,M,M] [ 1,1,1,2,0,0,0] B5 4 [1,2,3,4] [5,6,7] [0,1,2,4,8,M,17] [ 1,1,1,2,4,0,4] B6 5 [1,2,3,4,5] [6,7] [0,1,2,4,8,10,17] [ 1,1,1,2,4,5,4] B7 6 [1,2,3,4,5,6] [7] [0,1,2,4,8,10,16] [ 1,1,1,2,4,5,6] B8 7 [1,2,3,4,5,6,7] [] nt Nt B9 K t thúc Bài tốn này cũng dùng m ng trư c đánh d u các đ nh trên đư ng đi như trên nhưng khơng dùng c u trúc hàng đ i. Dùng m t m ng trongso: array [1 Nmax] of (tuỳ vào bài tốn cĩ th là ki u real ho c ki u longint). Trongso [i] b ng t ng tr ng s c a các cung n m trên đư ng đi t đ nh xp cho đ n i. Bài tốn c a chúng ta tr thành tìm m ng trongso [i] sao cho nĩ đ t giá tr nh nh t. Chia t p các đ nh c a đ th X thành 2 ph n a. T p các đ nh cĩ tr ng s đư c gán c đ nh A. b. T p các đ nh cĩ tr ng s đư c gán t m th i B. Trang 87
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Trong su t quá trình duy t nh ng đ nh đư c đưa vào t p A thì tr ng s c a đ nh đĩ khơng thay đ i và là đ dài đư ng đi ng n nh t t xp đ n nĩ, nh ng đ nh t p B cĩ tr ng s thay đ i đ n khi nh nh t thì đư c đưa vào t p A. Cách thay đ i tr ng s đ nh nh t đư c th hi n như sau: B1: Kh i t o Kh i t o các giá tr c a m ng trongso = Maxlongint (ho c Maxreal) L p hai t p A và B. Ban đ u A r ng cịn B = X Duy t t t c các đ nh u k v i đ nh xp thì gán trongso [u] = a[u, xp] và truoc[u] = xp; REPEAT B2: Tìm đ nh v thu c t p B cĩ tr ng s nh nh t. ðưa đ nh v vào t p A (B/{v}; A + {v}) B3: Duy t t t c các đ nh i thu c B mà k v i v N u trongso[i]>trongso[v]+ a[i,v] thì + Gán l i trongso [i]:= trongso[v] + a[i,v]; + ð ng th i gán truoc [i]:= v; UNILT ; C u trúc d li u Ma tr n k bi u di n quan h c a đ th : a(i;j) = 1 n u i khơng n i v i j >= n u i n i v i j và a(a,j) là tr ng s c a cung 9i,j). M ng truoc và trongso đư c mơ t như trên. M ng duong đ lưu các đ nh trên đư ng đi. ð bi u di n t p A và B ta dùng ki u t p h p. tap:set of Trang 88
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Trong ph n cài đ t trên, khai báo t p A ch là minh hồ cho thu t tốn cịn trong bài tốn này khơng c n thi t ph i s d ng t p A, ta hi u ng m khi lo i m t ph n t kh i t p B thì nghĩa là ta đã đưa nĩ vào t p A. Chương trình minh h a : Program Difstra_Phuongphap2; Const Nmax = 100; Type Mang = array [0 Nmax] of Longint; Tapcacdinh = set of a Nmax; Var a: array[1 Nmax, 1 Nmax] of integer; duong, truoc, trongso: Mang; N, sold, xp, kt: Integer; tap A, tap B: set of Tapcacdinh; (*Ch trình bày th t c Dijstra, các th t c khác tương t như ph n trên *) Prcedure Dijstra; Var i, u, v: integer; Begin (*B1 kh i t o các giá tr c n thi t *) For i;= 0 to N do Trongso [i]:= MaxLongint; (*Kh i t o t p B là t p t t c các đ nh c a đ th *) tapB: = [ ]; For i:= 1 to N do tap B:= tapB +[i]; (*ðưa xp vào t p A*) tapA:= [xp] Trang 89
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 tapB: = tapB [xp]; truoc[xp]:= 1; (*Tìm các đ nh k v i xp g n tr ng s và nhân cho nh ng đ nh đĩ*) For i:= 1 to N do if a [xp;i]>=0 then Begin trongso[i]:= a[xp,i]; truoc[i]:= xp End; REPEAT (*Tìm đ nh v cĩ tr ng s nh nh t trong t p B và đưa vào t p A, lo i kh i t p B*). j: = Dinh_co_trong_so_min; tapA:= tapA + [j]; tapB:= tapB + [j]; (*Tìm t t c các đ nh thu c B k v i đ nh v và th c hi n vi c gi m tr ng s cho chúng*). For i:= 1 to N do If (i in tapB) and (a [i,j]>=0 and(trongso[i]>trongso[j] + a[i,j]) then Begin trongso [i]: = trongso[j] + a[i,j]; truoc[i]:= j; End; UNILT tapB = [ ]; Trang 90
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 End; (*Hàm tìm đ nh cĩ tr ng s nh nh t trong các đ nh thu c t p B*) Function Dinh_co_trong_so_min: Integer; Var i,t: integer; Begin tS [it]:= maxint For i:= 1 to N do If (i in tap B and (trongso[i] < trongso[t] then t:=i; Dinh_co_trong_so_+min:= t End; d. Bài t p t gi i Bài t p 1: Áp d ng thu t tốn Dijkstra tìm đư ng đi ng n nh t cho đ th sau: Trang 91
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài t p 2: Di chuy n trên các hình trịn Cho N hình trịn (đánh s t 1 đ n N). M t ngư i mu n đi t hình trịn này sang hình trịn khác c n tuân theo qui ư c: N u kho ng cách gi a 2 đi m g n nh t c a 2 hình trịn khơng quá 50 cm thì cĩ th bư c sang. N u kho ng cách này hơn 50cm và khơng quá 80cm thì cĩ th nh y sang. Các trư ng h p khác khơng th sang đư c. M t đư ng đi t hình trịn này sang hình trịn khác đu c g i là càng "t t" n u s l n ph i nh y là càng ít. Hai đư ng đi cĩ s l n nh y b ng nhau thì đư ng đi nào cĩ s hình trịn đi qua ít hơn thì đư ng đi đĩ "t t" hơn. Các hình trịn đư c cho trong m t file văn b n, trong đĩ dịng th i mơ t hình trịn s hi u i (i = 1, 2, , N) bao g m 3 s th c: hồnh đ tâm, tung đ tâm, đ l n bán kính (đơn v đo b ng mét). L p trình đ c các hình trịn t m t file văn b n (tên file vào t bàn phím), sau đĩ c m i l n đ c s hi u hình trịn xu t phát S và hình trịn k t thúc T t bàn phím, chương trình s đưa ra đư ng đi t S đ n T là "t t nh t" theo nghĩa đã nêu (ho c thơng báo là khơng cĩ). Yêu c u đư ng đi đư c vi t dư i d ng m t dãy các s hi u hình trịn l n lư t c n đư c đi qua trong đĩ nĩi rõ t ng s các bư c nh y, t ng s các hình trịn đi qua và nh ng bư c nào c n ph i nh y. Gi i h n s hình trịn khơng quá 100. Bài t p 3: Tìm hành trình t n ít xăng nh t Trang 92
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Trên m t m ng lư i giao thơng, m t ngư i mu n đi t đi m A đ n đi m B b ng xe máy. Xe ch a đư c t i đa 3 lít xăng và ch y 100km h t 2,5 lít. Các tr m xăng ch đư c đ t các đi m dân cư, khơng đ t gi a đư ng và ngư i này khơng mang theo b t kỳ thùng ch a xăng nào khác. Hãy vi t chương trình nh p vào m ng lư i giao thơng và xác đ nh giúp ngư i này tuy n đư ng đi t A đ n B sao cho ít t n xăng nh t. Bài t p 4: Di chuy n gi a các đ o Trên m t đ o qu c, cĩ N hịn đ o. Gi s t t c các đ o đ u cĩ hình d ng là hình ch nh t n m ngang. Trên m i hịn đ o cĩ th cĩ sân bay n m trung tâm đ o, cĩ th cĩ c ng n m 4 gĩc đ o. Trên m i đ o đ u cĩ tuy n đư ng xe buýt n i 4 gĩc đ o v i nhau và v i trung tâm đ o. Gi a 2 đ o cĩ th đi l i b ng máy bay n u c 2 đ o đ u cĩ sân bay và cĩ th đi l i b ng tàu n u c 2 đ o đ u cĩ c ng. Gi s r ng: Các tuy n đư ng (b , khơng, th y) đ u là đư ng th ng. Chi phí cho m i km và t c đ c a m i lo i phương ti n là: Phương ti n T c đ Chi phí (km/h) (đ/km) Máy bay 1000 1000 Xe buýt 70 100 Tàu th y 30 50 Hãy vi t chương trình xác đ nh tuy n đư ng và cách di chuy n gi a 2 hịn đ o trong đ o qu c sao cho: Th i gian di chuy n ít nh t. Chi phí di chuy n ít nh t. Th i gian di chuy n ít nh t nhưng v i m t s ti n chi phí khơng quá ð đ ng. Trang 93
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Chi phí di chuy n ít nh t nhưng v i th i gian di chuy n khơng vư t quá T gi . Bài t p 5: Tìm đư ng ng n nh t Gi s X là t p các khu dân cư, U là t p các đư ng sá n i li n các khu đĩ. Ta gi s m i ch giao nhau c a các con đư ng đ u thu c X. V i con đư ng u, s l(u) là đ dài c a u tính b ng km. Hãy ch ra tuy n đư ng đi t m t khu i sang khu j sao cho t ng chi u dài là nh nh t. Bài t p 6: ðư ng đi trên lư i Cho 1 ma tr n A[M, N], m i ph n t c a nĩ ch a 1 s t nhiên. T 1 ơ (i, j) ta cĩ th đi sang ơ k nĩ (cĩ chung 1 c nh) n u giá tr c a ơ k này nh hơn giá tr lưu trong (i, j). Hãy tìm 1 đư ng đi t ơ (i, j) t i ơ (k, l) trên ma tr n sao cho ph i đi qua ít ơ nh t. Hãy tìm 1 đư ng đi t ơ (i, j) t i ơ (k, l) trên ma tr n sao cho t ng giá tr các ơ ph i đi qua nh nh t. Bài t p 7 : Tìm đư ng v i chi phí ph i tr cho phép Cĩ N thành ph đư c đánh s t 1 N n i v i nhau b ng các đo n đư ng m t chi u. M i đo n đư ng bao g m 2 thơng s : ð dài và chi phí đi c a đo n đư ng. A s ng t i thành ph 1 và A mu n di chuy n đ n thành ph N nhanh nh t cĩ th . B n hãy giúp A tìm ra đư ng đi ng n nh t t thành ph 1 đ n thành ph N mà A cĩ kh năng chi tr ti n. D li u vào : ROADS.IN Dịng đ u tiên ch a s nguyên K, 0 <= K <= 10000, s ti n mà A cĩ. Dịng th 2 ch a s nguyên N, 2 <= N <= 100, s thành ph . Dịng th 3 ch a s nguyên R, 1 <= R <= 10000, t ng s đo n đư ng. M i dịng trong s R dịng ti p theo mơ t m t đo n đư ng b ng các s S, D, L và T cách nhau b i ít nh t m t kho ng tr ng. + S là thành ph kh i hành, 1 <= S <= N. + D là thành ph đ n, 1 <= D <= N. Trang 94
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 + L là đ dài c a đo n đư ng, 1 N và nh hơn K. ROADS.IN ROADS.IN 5 0 6 4 7 4 1 2 2 3 1 4 5 2 2 4 3 3 1 2 1 0 3 4 2 4 2 3 1 1 1 3 4 1 3 4 1 0 4 6 2 1 ROADS.OUT 3 5 2 0 1 5 4 3 2 ROADS.OUT 11 Trang 95
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài 12: Bài tốn lu ng c c đ i trong m ng M c tiêu Trình bày đư c tư tư ng ch đ o c a thu t tốn Ford_Fulkerson và cài đ t đư c thu t tốn. Phân tích đư c bài tốn th c t tương ng ph n lý thuy t đã h c. Sinh viên cĩ kh năng t h c. a. Nh c l i lý thuy t ð nh nghĩa 1 . Ta g i m ng là đ th cĩ hư ng G = (V,E), trong đĩ cĩ duy nh t m t đ nh s khơng cĩ cung đi vào g i là đi m phát, duy nh t m t đ nh t khơng cĩ cung đi ra g i là đi m thu và m i cung e = (v,w) ∈ E đư c gán v i m t s khơng âm c(e) = c(v,w) g i là kh năng thơng qua c a cung e. ð nh nghĩa 2 . Gi s cho m ng G = (V,E). Ta g i lu ng f trong m ng G = (V,E) là ánh x f: E R + gán cho m i cung e =(v,w) ∈ E m t s th c khơng âm f(e) = f(v,w), g i là luơng trên cung e, tho mãn các đi u ki n sau: 1. Lu ng trên m i cung e ∈ E khơng vư t quá kh năng thơng qua c a nĩ: 0 ≤ f (e) ≤ c(e), 2. ði u ki n cân b ng lu ng trên m i đ nh c a m ng : T ng lu ng trên các cung đi vào đ nh v b ng t ng lu ng trên các cung đi ra kh i đ nh v, n u v ≠ s,t: Div f (v) = ∑ f (v) − ∑ f (v, w) = 0 w∈Γ − (v ) w∈Γ + (v ) Trong đĩ Γ − (v) t p các đ nh c a m ng mà t đĩ cĩ cung đ n v, Γ + (v) t p các đ nh c a m ng mà t v cĩ cung đ n nĩ: Γ − (v) = {w ∈V (: w,v) ∈ E},Γ + (v) = {w ∈V (: v, w) ∈ E}. 3.Giá tr c a lu ng f là s val ( f ) = ∑ f (s, w) = ∑ f (w,t .) w∈Γ+ (s) w∈Γ− (t ) Trang 96
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài tốn lu ng c c đ i trong m ng Cho m ng G=(V,E). Hãy tìm lu ng f* trong m ng v i giá tr lu ng val(f*) là l n nh t . Lu ng như v y ta s g i là lu ng c c đ i trong m ng. Gi i quy t bài tốn T m ng G = (V,E) kh năng thơng qua các cung và các đ nh. Ta s gi i quy t theo hai bư c sau: 10 Xác đ nh m ng G’. 20 Tìm lu ng c c đ i trong m ng G’. B t đ u t lu ng zero v i kh năng thơng qua cung. Thu t tốn Ford – Fulkerson 1. Xu t phát t m t lu ng ch p nh n đư c f. 2. Tìm m t đư ng đi tăng lu ng P. N u khơng cĩ thì thu t tốn k t thúc. N u cĩ, ti p bư c 3 dư i đây. 3. N u δ(P) = + ∞ thu t tốn k t thúc. Thu t tốn gán nhãn (The labeling algorithm) 1. N u t ∈ VT ho c VT = ∅, thu t tốn k t thúc. Ngư c l i thì ch n m t đ nh u ∈ VT đ thăm và đưa nĩ ra kh i VT. Xét t t c các đ nh c nh u, t c là xét m i cung cĩ d ng (u,v) và (v,u). 2. N u (u,v) ∈ E, F(u,v) 0 và v chưa gán nhãn thì gán nhãn nĩ và đưa vào t p VT. b. ð bài t p Bài 1 Áp d ng thu t tốn Ford Fullkerson tìm lu ng c c đ i b ng cách gán nhãn cho lu ng zero sau: Trang 97
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 a 7,0 b 6,0 5,0 4,0 4,0 s 4,0 c t 5,0 3,0 12,0 7,0 d 9,0 e c. Hư ng d n gi i Bài 1 + Bư c l p 1: s → a → b → t, δ1 = 1 a(s+, 6) 7,0 b(a+, 6) 6,0 5,0 4,0 4,0 4,0 s c(s+, 4) t(e+, 2) 5,0 3,0 (s, ∞) 12,0 7,0 d(s+, 7) 9,0 e(d+, 4) a 7,4 b 6,4 5,0 4,4 4,0 s 4,0 c t 5,0 3,0 12,0 7,0 d 9,0 e + Bư c l p 2: s → a → b → c → e → t, δ2 = 2 Trang 98
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 a(s+, 2) 7,4 b(a+, 2) 6,4 5,0 4,4 4,0 4,0 s c(b+, 2) t(e+, 2) 5,0 3,0 (s, ∞) 12,0 7,0 d(s+, 7) 9,0 e(c+, 2) a(s+, 0) 7,6 b(a+, 1) 6,6 5,0 4,4 4,2 4,0 s c(s+, 4) t(e+, 1) 5,0 3,2 12,2 (s, ∞) 7,0 d(s+, 7) 9,0 e(c+, 1) a 7,6 b 6,6 5,0 4,4 4,2 s 4,0 c t 5,0 3,2 12,2 7,0 d 9,0 e + Bư c l p 3: s → c → e → t, δ3 = 1 a 7,6 b 6,6 5,0 4,4 4,2 s 4,1 c t 5,0 3,3 12,3 7,0 d 9,0 e + Bư c l p 4: s → d → e → t, δ4 = 7 Trang 99
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 a 7,6 b 6,6 5,0 4,4 4,2 s 4,1 c t 5,0 3,3 12,10 7,7 d 9,7 e a(s+, 0) 7,6 b(a+, 1) 6,6 5,0 4,4 4,2 4,1 s c(s+, 3) t(e+, 7) 5,0 3,3 12,3 (s, ∞) 7,0 d(s+, 7) 9,0 e(d+, 7) + Bư c l p 5: s → c → d → e → t, δ5 = 2 a 7,6 b 6,6 5,0 4,4 4,2 s 4,3 c t 5,2 3,3 12,12 7,7 d 9,9 e a(s+, 0) 7,6 b(a+, 1) 6,6 5,0 4,4 4,2 4,1 s c(s+, 3) t(e+, 2) 5,0 3,3 12,10 (s, ∞) 7,7 d(c+, 3) 9,7 e(d+, 2) + Bư c l p 6: Khơng cịn đư ng tăng lu ng n a, Val(f max ) = 6+3+7 = 16. d. Bài t p t gi i Bài t p 1 : Cho G=(V,E) đ th cĩ hư ng trong đĩ khơng cĩ cung (s,t). Ch ng minh r ng s đư ng đi cơ b n n i hai đ nh s và t là b ng s ít nh t các đ nh c a đ th c n lo i b đ trong đ th khơng cịn đư ng đi n i s v i t. Trang 100
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài t p 2 : Xây d ng thu t tốn tìm t p E 1 t t c các cung c a đ th mà vi c tăng kh năng thơng qua c a b t kỳ cung nào trong E đ u d n đ n tăng giá tr c a lu ng c c đ i trong m ng. Bài t p 3 : Cho hai dãy s nguyên dương {p i, i=1,2, ,m} và {q j, j=1,2, ,n}. Hãy xây d ng ma tr n A={a ij : i=1,2, ,m; j=1,2, n} v i các ph n t ai j ∈ {0,1} cĩ t ng các ph n t trên dịng i là p i , t ng các ph n t trên c t j là q j. Bài t p 4 : Cĩ m chàng trai, n cơ gái và k bà m i, m i bà m i p (p=1,2, ,k) cĩ m t danh sách L p m t s chàng trai và cơ gái trong s các chàng trai và cơ gái nĩi trên là khách hàng c a bà ta. Bà m i p cĩ th se duyên cho b t c c p trai gái nào là khách hàng c a bà ta, nhưng khơng đ s c t ch c quá d p đám cư i. Hãy xây d ng thu t tốn căn c vào danh sách Lp, d p, p=1,2, ,k; đưa ra cách t ch c nhi u nh t các đám cư i gi a m chàng trai và n cơ gái v i s giúp đ c a các bà m i. Bài t p 5 : Chuy n bi C u bé v N (N<=100) vịng trịn, đánh s t 1 t i N và tơ màu các vịng trịn đĩ (cĩ th cĩ các vịng trịn cĩ màu gi ng nhau), sau đĩ n i t ng c p các cung đ nh hư ng, m i cung cĩ m t màu nh t đ nh. Các màu (c a cung và vịng trịn) đư c đánh s t 1 đ n 100. C u bé ch n 3 s nguyên khác nhau L, K và Q n m trong ph m vi t 1 t i N, đ t vào trong các vịng trịn s L và K m i vịng m t hịn bi, sau đĩ b t đ u di chuy n bi theo nguyên t c sau: Bi ch đư c chuy n theo cung cĩ màu trùng v i màu c a vịng trịn ch a viên bi th 2. Bi ch đư c chuy n theo chi u cung Hai viên bi khơng đư c đ ng th i cùng m t vịng trịn; Khơng nh t thi t ph i di chuy n l n lư t các viên bi, Quá trình di chuy n k t thúc, khi m t trong hai viên bi t i vịng trịn Q. Hãy l p trình xác đ nh cách di chuy n đ ch m d t quá trình sau m t s ít nh t các bư c chuy n. D li u vào t file BL.INP: Trang 101
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Dịng đ u: 4 s nguyên N L K Q Dịng th 2: N s nguyên C 1, C 2, ,C n; C i là màu vịng trịn i Dịng th 3: s nguyên M (0 < M < 10000) M dịng sau: m i dịng 3 s nguyên A i B i D i; xác đ nh cung màu D i t vịng trịn A i t i vịng trịn B i. Các s trên m t dịng cách nhau m t d u cách. K t qu đưa ra file BL.OUT: Dịng đ u: CO ho c KHONG, cho bi t quá trình cĩ k t thúc đư c hay khơng, N u dịng đ u là CO thì dịng 2 ch a s nguyên xác đ nh s bư c chuy n t i thi u . BL.INP BL.OUT 5 3 4 1 CO 2 3 2 1 4 3 8 2 1 2 4 1 5 4 5 2 4 5 2 5 1 3 3 2 2 2 3 4 5 3 1 3 5 1 Trang 102
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 Bài t p 6 : B ng đi n M t lư i ơ vuơng đư c ph trên m t b ng đi n hình vuơng. V trí n m trên giao c a 2 đư ng k c a lư i s đư c g i là nút. T t c cĩ nxn nút trên lư i. Cĩ m t s nút ch a ti p đi m. Nhi m v c a b n là c n n i các ti p đi m v i các nút trên biên c a b ng b i các đo n dây d n (g i là các m ch). Các m ch ch đư c ch y d c theo các đư ng k c a lư i (nghĩa là khơng đư c ch y theo đư ng chéo). Hai m ch khơng đư c phép cĩ đi m chung, vì v y hai m ch b t kỳ khơng đư c phép cùng ch y qua cùng m t đo n đư ng k c a lư i cũng như khơng đư c ch y qua cùng m t nút c a lư i. Các m ch cũng khơng đư c ch y d c theo các đo n k c a lư i trên biên (m ch ph i k t thúc khi nĩ g p biên) và cũng khơng đư c ch y qua nút ch a ti p đi m khác. Ví d : B ng đi n và các ti p đi m đư c cho trong hình 2a. Nút tơ đ m trong hình v th hi n v trí các ti p đi m. Yêu c u: Vi t chương trình cho phép n i đư c m t s nhi u nh t các ti p đi m v i biên. Các ti p đi m trên biên đã th a mãn địi h i đ t ra, vì th khơng nh t thi t ph i th c hi n m ch n i chúng. N u như cĩ nhi u l i gi i thì chi c n đưa ra m t trong s chúng. D li u vào: file văn b n ELE.INP: Dịng đ u tiên ch a s nguyên n (3 <= n <= 15). M i dịng trong s n dịng ti p theo ch a n ký t phân cách nhau b i m t d u cách. M i ký t ch là 0 ho c 1. Ký t 1 th hi n ti p đi m, ký t 0 th hi n nút khơng cĩ ti p đi m trên v trí tương ng c a lư i. Các nút đư c đánh s t 1 đ n n*n theo th t t trái sang ph i, t Trang 103
- Giáo trình TỐN R I R C 2 B mơn Cơng ngh ph n m m 2010 trên xu ng dư i. Ch s c a nút ch a ti p đi m s là ch s c a ti p đi m. K t qu : ghi ra file ELE.OUT: Dịng đ u tiên ch a k là s ti p đi m l n nh t cĩ th n i v i biên b i các m ch. M i dịng trong s k dịng ti p theo mơ t m t m ch n i m t trong s k ti p đi m v i biên theo qui cách sau: đ u tiên là ch s c a ti p đi m đư c n i, ti p đ n là dãy các ký t mơ t hư ng c a m ch n i: E: đơng, W: tây, N: b c, S: nam. Gi a ch s và dãy ký t ph i cĩ đúng m t d u cách, cịn gi a các ký t trong dãy ký t khơng đư c cĩ d u cách. K t qu ph i đư c đưa ra theo th t tăng d n c a ch s ti p đi m. Ví d : ELE.IN ELE.OUT 6 11 E 0 0 0 1 1 1 16 NWN 0 0 0 0 1 0 17 SE 0 0 0 1 1 1 27 S 0 0 0 0 0 0 28 NWWSS 0 0 1 1 1 1 29 S 0 0 0 1 0 1 Bài t p 7: M t khĩa h c g m N mơn h c, mơn h c i ph i h c trong ti ngày. Gi a các mơn h c cĩ m i quan h trư c/sau: cĩ mơn h c ch h c đư c sau khi đã h c m t s mơn h c khác. M i quan h đĩ đư c th hi n b i m t m ng hai chi u A[i, j]; i, j = 1, , N trong đĩ A[i, j] = 1/0 và A[i, i] b ng 0 v i m i i, A[i, j] = 1 khi và ch khi mơn h c i ph i đư c d y xong trư c khi h c mơn j (ngày k t thúc mơn i ph i Trang 104
