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 ứng dụng nguyên lý thuật toán hiệu chỉnh trong đường chạy lập trình p1

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

Thêm vào BST
Báo xấu
76
lượt xem 3
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 ứng dụng nguyên lý thuật toán hiệu chỉnh trong đường chạy lập trình p1', kỹ thuật - công nghệ, điện - điện tử phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình phân tích ứng dụng nguyên lý thuật toán hiệu chỉnh trong đường chạy lập trình p1

  1. h a n g e Vi h a n g e Vi XC XC e e F- F- w w PD PD Giáo trình phân tích ứng dụng nguyên lý thuật toán er er ! ! W W O O N N y y bu bu hiệu chỉnh trong đườngvaø Giaûi Thuaät trình Giaùo trình: Caáu Truùc Döõ Lieäu chạy lập to to k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k } else { Temp[J2] = M[I1] J2--; } Head = 0-Head; K1 = K2 = 0; break; } } } return; } //======================================================== void StraightMergeSortModify(T M[], int N) { int L = 1 ; T * Temp = new T[N]; if (Temp == NULL) return; while (L < N) { MergeDistribute(M, N, Temp, L); L = 2*L; if (L >= N) { for (int I = 0; I < N; I++) M[I] = Temp[I]; break; } MergeDistribute(Temp, N, M, L); L = 2*L; } delete Temp; return; } - Phaân tích thuaät toaùn hieäu chænh: + Trong thuaät giaûi naøy chuùng ta luoân thöïc hieän log2(N) laàn troän - phaân phoái caùc run. + Moãi laàn troän-phaân phoái chuùng ta phaûi thöïc hieän: N pheùp gaùn vaø N+N/2+N/2=2N pheùp so saùnh. + Trong moïi tröôøng hôïp: Soá pheùp gaùn: G = N×Log2(N) Soá pheùp so saùnh: S = 2N×Log2(N) Soá pheùp hoaùn vò: Hmin = 0 + Nhö vaäy thuaät giaûi troän thaúng hieäu chænh vöøa tieát kieäm boä nhôù, vöøa thöïc hieän nhanh hôn thuaät giaûi troän thaúng ban ñaàu. + Tuy nhieân, trong thuaät giaûi troän thaúng chuùng ta ñaõ thöïc hieän vieäc phaân phoái vaø troän caùc caëp ñöôøng chaïy coù chieàu daøi coá ñònh maø trong thöïc teá treân daõy caùc ñöôøng Trang: 53
  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 chaïy coù theå coù chieàu daøi lôùn hôn. Ñieàu naøy seõ giaûm bôùt soá laàn phaân phoái vaø troän c u -tr a c k c u -tr a c k caùc caëp ñöôøng chaïy cho chuùng ta. Thuaät giaûi troän töï nhieân ñöôïc trình baøy sau ñaây seõ loaïi boû ñöôïc nhöôïc ñieåm naøy cuûa thuaät giaûi troän thaúng. b. Thuaät toaùn saép xeáp troän töï nhieân (Natural Merge Sort): - Tö töôûng: Taän duïng caùc ñöôøng chaïy töï nhieân coù saün treân daõy, tieán haønh troän töông öùng caùc caëp ñöôøng chaïy töï nhieân naèm hai ñaàu daõy M thaønh moät ñöôøng chaïy môùi vaø phaân phoái luaân phieân caùc ñöôøng chaïy môùi naøy veà hai ñaàu daõy phuï Temp. Sau ñoù laïi tieáp tuïc troän töông öùng töøng caëp run ôû hai ñaàu daõy phuï Temp thaønh moät run môùi vaø phaân phoái luaân phieân run môùi naøy veà hai ñaàu daõy M. Cöù tieáp tuïc nhö vaäy cho ñeán khi treân M hoaëc treân Temp chæ coøn laïi 01 run thì keát thuùc. - Thuaät toaùn Troän – Phaân phoái caùc caëp ñöôøng chaïy töï nhieân: 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: IF (I1 > I2) // Ñaõ troän vaø phaân phoái heát caùc run Thöïc hieän Bkt B7: IF (M[I1] ≤ M[I2]) // M[I1] ñöùng tröôùc M[I2] treân Temp B7.1: If (Head = True) B7.1.1: Temp[J1] = M[I1] B7.1.2: J1++ B7.2: Else B7.2.1: Temp[J2] = M[I1] B7.2.2: J2-- B7.3: I1++ B7.4: If (I1 > I2) Thöïc hieän Bkt B7.5: If (M[I1] < M[I1-1]) //Ñaõ duyeät heát 1 run phía ñaàu trong M Thöïc hieän B9 B7.6: Laëp laïi B7 B8: ELSE // M[I2] ñöùng tröôùc M[I1] treân Temp B8.1: If (Head = True) B8.1.1: Temp[J1] = M[I2] B8.1.2: J1++ B8.2: Else B8.2.1: Temp[J2] = M[I2] B8.2.2: J2-- B8.3: I2-- B8.4: If (I1 > I2) Thöïc hieän Bkt Trang: 54
  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 B8.5: If (M[I2] < M[I2+1]) //Ñaõ duyeät heát 1 run phía sau trong M c u -tr a c k c u -tr a c k Thöïc hieän B15 B8.6: Laëp laïi B7 //Cheùp phaàn run coøn laïi ôû phía sau trong M veà Temp B9: IF (M[I2] < M[I2+1]) //Ñaõ cheùp heát phaàn run coøn laïi ôû phía sau trong M veà Temp B9.1: Head = Not(Head) B9.2: Laëp laïi B6 B10: IF (Head = True) B10.1: Temp[J1] = M[I2] B10.2: J1++ B11: ELSE B11.1: Temp[J2] = M[I2] B11.2: J2-- B12: I2-- B13: IF (I1> I2) Thöïc hieän Bkt B14: Laëp laïi B9 //Cheùp phaàn run coøn laïi ôû phía tröôùc trong M veà Temp B15: IF (M[I1]< M[I1-1]) //Ñaõ cheùp heát phaàn run coøn laïi phía tröôùc trong M veà Temp B15.1: Head = Not(Head) B15.2: Laëp laïi B6 B16: IF (Head = True) B16.1: Temp[J1] = M[I1] B16.2: J1++ B17: ELSE B17.1: Temp[J2] = M[I1] B17.2: J2-- B18: I1++ B19: IF (I1> I2) Thöïc hieän Bkt B20: Laëp laïi B15 Bkt: Keát thuùc - Thuaät toaùn saép xeáp troän töï nhieân: B1: L = 1 //Khôûi taïo chieàu daøi ban ñaàu cuûa run ñaàu tieân //Tìm chieàu daøi ban ñaàu cuûa run ñaàu tieân B2: IF (N < 2) B2.1: L=N B2.2: Thöïc hieän Bkt B3: IF (M[L] ≤ M[L+1] And L < N) B3.1: L++ B3.2: Laëp laïi B3 B4: IF (L = N) //Daõy chæ coøn 01 run Thöïc hieän Bkt B5: Troän_Phaân_Phoái(M, N, Temp, L) B6: IF (L = N) Trang: 55
  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 // Cheùp caùc phaàn töû töø Temp veà M c u -tr a c k c u -tr a c k B6.1: I = 1 B6.2: If (I > N) Thöïc hieän Bkt B6.3: M[I] = Temp[I] B6.4: I++ B6.5: Laëp laïi B6.2 B7: Troän_Phaân_Phoái(Temp, N, M, L) B8: Laëp laïi B4 Bkt: Keát thuùc - Caøi ñaët thuaät toaùn troän töï nhieân: Haøm NaturalMergeSort coù prototype nhö sau: void NaturalMergeSort(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 töï nhieân. Haøm söû duïng haøm NaturalMergeDistribute coù prototype vaø yù nghóa nhö sau: void NaturalMergeDistribute(T M[], int N, T Temp[], int &L); Haøm thöïc hieän vieäc troän caùc caëp run ôû hai ñaàu daõy M maø run ñaàu tieân coù chieàu daøi L thaønh moät run môùi chieàu daøi lôùn hôn hoaëc baèng L vaø phaân phoái luaân phieân run môùi naøy veà hai ñaàu daõy Temp. Noäi dung cuûa haøm nhö sau: void NaturalMergeDistribute(T M[], int N, T Temp[], int &L) { int I1 = 0, I2 = N-1, J1 = 0, J2 = N-1, Head = 1, FirstPair = 1; while (I1 < I2) { while (M[I1]
  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 I2--; c u -tr a c k c u -tr a c k } if (Head == 1) { Temp[J1] = M[I2]; J1++; If (FirstPair == 1) L++; } else { Temp[J2] = M[I2]; J2--; } I2--; FirstPair = 0; if (I1 > I2) return; Head = 0 – Head; break; } } if (I1 == I2) { Temp[J1] = M[I1]; if (I1 == N-1) L = N; return; } while (M[I2]
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí
65 tài liệu
2428 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

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