intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Giáo trình phân tích quy trình ứng dụng nguyên lý sử dụng cấu trúc dữ liệu và giải thuật p10

Chia sẻ: Sdfasf Fasf | Ngày: | Loại File: PDF | Số trang:5

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

Tham khảo tài liệu 'giáo trình phân tích quy trình ứng dụng nguyên lý sử dụng cấu trúc dữ liệu và giải thuật p10', công nghệ thông tin, tin học văn phòng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:
Lưu

Nội dung Text: Giáo trình phân tích quy trình ứng dụng nguyên lý sử dụng cấu trúc dữ liệu và giải thuật p10

  1. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N . y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o + ÔÛ moãi laàn phaân phoái run chuùng ta phaûi thöïc hieän: N pheùp gaùn vaø 2N pheùp so saùnh c u -tr a c k c u -tr a c k (N pheùp so saùnh heát ñöôøng chaïy vaø N pheùp so saùnh heát daõy). + ÔÛ moãi laàn troän run chuùng ta cuõng phaûi thöïc hieän: N pheùp gaùn vaø 2N+N/2 pheùp so saùnh (N pheùp so saùnh heát ñöôøng chaïy, N pheùp so saùnh heát daõy vaø N/2 pheùp so saùnh giaù trò caùc caëp töông öùng treân 2 daõy phuï). + Trong moïi tröôøng hôïp: Soá pheùp gaùn: G = 2N×Log2(N) Soá pheùp so saùnh: S = (4N+N/2)×Log2(N) Soá pheùp hoaùn vò: Hmin = 0 + Trong thuaät giaûi naøy chuùng ta söû duïng 02 daõy phuï, tuy nhieân toång soá phaàn töû ôû 02 daõy phuï naøy cuõng chæ baèng N, do vaäy ñaõ taïo ra söï laõng phí boä nhôù khoâng caàn thieát. Ñeå giaûi quyeát vaán ñeà naøy chuùng ta chæ caàn söû duïng 01 daõy phuï song chuùng ta keát hôïp quaù trình troän caùc caëp run coù chieàu daøi L töông öùng ôû hai ñaàu daõy thaønh caùc run coù chieàu daøi 2L vaø phaân phoái luaân phieân veà hai ñaàu cuûa moät daõy phuï. Sau ñoù chuùng ta ñoåi vai troø cuûa 02 daõy naøy cho nhau. + Tröôùc khi hieäu chænh laïi thuaät giaûi chuùng ta xeùt daõy M goàm 10 phaàn töû sau ñeå minh hoïa cho quaù trình naøy: Giaû söû ta caàn saép xeáp maûng M coù 10 phaàn töû sau (N = 10): M: 81 63 69 74 14 77 56 57 9 25 Ta thöïc hieän caùc laàn troän caùc caëp run ôû hai ñaàu daõy naøy vaø keát hôïp phaân phoái caùc run môùi troän veà hai ñaàu daõy kia nhö sau: Laàn 1: L = 1 Troän caùc caëp run coù chieàu daøi L = 1 treân M thaønh caùc run coù chieàu daøi L = 2 vaø keát hôïp phaân phoái luaân phieân caùc run naøy veà hai ñaàu daõy Tmp: M: 81 63 69 74 14 77 56 57 9 25 Tmp: 25 81 57 69 14 77 74 56 63 9 Ñoåi vai troø cuûa M vaø Tmp cho nhau M: 25 81 57 69 14 77 74 56 63 9 Laàn 2: L = 2 Troän caùc caëp run coù chieàu daøi L = 2 treân M thaønh caùc run coù chieàu daøi L = 4 vaø keát hôïp phaân phoái luaân phieân caùc run naøy veà hai ñaàu daõy Tmp: M: 25 81 57 69 14 77 74 56 63 9 Tmp: 9 25 63 81 14 77 74 69 57 56 Trang: 48
  2. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N . y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o Ñoåi vai troø cuûa M vaø Tmp cho nhau c u -tr a c k c u -tr a c k M: 9 25 63 81 14 77 74 69 57 56 Laàn 3: L = 4 Troän caùc caëp run coù chieàu daøi L = 4 treân M thaønh caùc run coù chieàu daøi L = 8 vaø keát hôïp phaân phoái luaân phieân caùc run naøy veà hai ñaàu daõy Tmp: M: 9 25 63 81 14 77 74 69 57 56 Tmp: 9 25 56 57 63 69 74 81 77 14 Ñoåi vai troø cuûa M vaø Tmp cho nhau M: 9 25 56 57 63 69 74 81 77 14 Laàn 4: L = 8 Troän caùc caëp run coù chieàu daøi L = 4 treân M thaønh caùc run coù chieàu daøi L = 8 vaø keát hôïp phaân phoái luaân phieân caùc run naøy veà hai ñaàu daõy Tmp: M: 9 25 56 57 63 69 74 81 77 14 Tmp: 9 14 25 56 57 63 69 74 77 81 Ñoåi vai troø cuûa M vaø Tmp cho nhau M: 9 14 25 56 57 63 69 74 77 81 L = 16 > 10: Keát thuùc thuaät toaùn + Nhö vaäy, trong thuaät giaûi naøy chuùng ta chæ coøn thao taùc troän caùc caëp run coù chieàu daøi L töông öùng ôû hai ñaàu daõy thaønh moät run môùi coù chieàu daøi 2L ñeå ñöa veà daõy phuï. Vaán ñeà laø chuùng ta seõ luaân phieân ñaët run môùi vaøo ñaàu daõy phuï (theo thöù töï taêng) vaø cuoái daõy phuï (theo thöù töï giaûm). Töùc laø hai böôùc troän vaø phaân phoái ñaõ ñöôïc keát hôïp laïi vôùi nhau. Thuaät giaûi hieäu chænh nhö sau: - Thuaät toaùn Troän – Phaân phoái caùc caëp ñöôøng chaïy: B1: I1 = 1 // Chæ soá töø ñaàu daõy M B2: I2 = N // Chæ soá töø cuoái daõy M B3: J1 = 1 // Chæ soá töø ñaàu daõy Temp B4: J2 = N // Chæ soá töø cuoái daõy Temp B5: Head = True // Côø baùo phía ñaët run môùi trong quaù trình troän - phaân phoái B6: K1 = 1 // Chæ soá ñeå duyeät caùc run ñaàu daõy M B7: K2 = 1 // Chæ soá ñeå duyeät caùc run cuoái daõy M B8: IF (I1 > I2) // Ñaõ troän vaø phaân phoái heát caùc run Trang: 49
  3. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N . y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o Thöïc hieän Bkt c u -tr a c k c u -tr a c k B9: IF (M[I1] ≤ M[I2]) // M[I1] ñöùng tröôùc M[I2] treân Temp B9.1: If (Head = True) B9.1.1: Temp[J1] = M[I1] B9.1.2: J1++ B9.2: Else B9.2.1: Temp[J2] = M[I1] B9.2.2: J2-- B9.3: I1++ B9.4: If (I1 > I2) Thöïc hieän Bkt B9.5: K1++ B9.6: If (K1 > L) //Ñaõ duyeät heát 1 run phía ñaàu trong M Thöïc hieän B11 B9.7: Laëp laïi B9 B10: ELSE // M[I2] ñöùng tröôùc M[I1] treân Temp B10.1: If (Head = True) B10.1.1: Temp[J1] = M[I2] B10.1.2: J1++ B10.2: Else B10.2.1: Temp[J2] = M[I2] B10.2.2: J2-- B10.3: I2-- B10.4: If (I1 > I2) Thöïc hieän Bkt B10.5: K2++ B10.6: If (K2 > L) //Ñaõ duyeät heát 1 run phía sau trong M Thöïc hieän B18 B10.7: Laëp laïi B9 //Cheùp phaàn run coøn laïi ôû phía sau trong M veà Temp B11: IF (K2 > L) //Ñaõ cheùp heát phaàn run coøn laïi ôû phía sau trong M veà Temp B11.1: Head = Not(Head) B11.2: Laëp laïi B6 B12: IF (Head = True) B12.1: Temp[J1] = M[I2] B12.2: J1++ B13: ELSE B13.1: Temp[J2] = M[I2] B13.2: J2-- B14: I2-- B15: If (I1 > I2) Thöïc hieän Bkt B16: K2++ B17: Laëp laïi B11 //Cheùp phaàn run coøn laïi ôû phía tröôùc trong M veà Temp B18: IF (K1 > L) //Ñaõ cheùp heát phaàn run coøn laïi ôû phía tröôùc trong M veà Temp Trang: 50
  4. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N . y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o B18.1: Head = Not(Head) c u -tr a c k c u -tr a c k B18.2: Laëp laïi B6 B19: IF (Head = True) B19.1: Temp[J1] = M[I1] B19.2: J1++ B20: ELSE B20.1: Temp[J2] = M[I1] B20.2: J2-- B21: I1++ B22: If (I1 > I2) Thöïc hieän Bkt B23: K1++ B24: Laëp laïi B18 Bkt: Keát thuùc - Thuaät toaùn saép xeáp troän thaúng hieäu chænh: B1: L = 1 //Chieàu daøi ban ñaàu cuûa caùc run B2: IF (L ≥ N) //Daõy chæ coøn 01 run Thöïc hieän Bkt B3: Troän_Phaân_Phoái(M, N, Temp, L) B4: L = 2*L B5: IF (L > N) // Cheùp caùc phaàn töû töø Temp veà M B5.1: I = 1 B5.2: If (I > N) Thöïc hieän Bkt B5.3: M[I] = Temp[I] B5.4: I++ B5.5: Laëp laïi B5.2 B6: Troän_Phaân_Phoái(Temp, N, M, L) B7: L = 2*L B8: Laëp laïi B2 Bkt: Keát thuùc - Caøi ñaët thuaät toaùn hieäu chænh: Haøm StraightMergeSortModify coù prototype nhö sau: void StraightMergeSortModify(T M[], int N); Haøm thöïc hieän vieäc saép xeáp N phaàn töû coù kieåu döõ lieäu T treân maûng M theo thöù töï taêng döïa treân thuaät toaùn saép troän tröïc tieáp ñaõ hieäu chænh. Haøm söû duïng haøm MergeDistribute coù prototype vaø yù nghóa nhö sau: void MergeDistribute(T M[], int N, T Temp[], int L); Haøm thöïc hieän vieäc troän caùc caëp run coù chieàu daøi L ôû hai ñaàu daõy M thaønh moät run coù chieàu daøi 2L vaø phaân phoái luaân phieân caùc run coù chieàu daøi 2L naøy veà hai ñaàu daõy Temp. Noäi dung cuûa haøm nhö sau: void MergeDistribute(T M[], int N, T Temp[], int L) Trang: 51
  5. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD er er ! ! W W O O N N . y y bu bu to to Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät k k lic lic C C w w m m w w w w o o .c .c .d o .d o { int I1 = 0, I2 = N-1, J1 = 0, J2 = N-1, K1 = 0, K2 = 0, Head = 1; c u -tr a c k c u -tr a c k while (I1
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2