Cấu trúc dữ liệu ( chương 17)

Chia sẻ: Nguyễn Thị Giỏi | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

109
lượt xem 33
download

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

Ứng dụng này minh họa sự sử dụng cả hai loại danh sách: danh sách tổng quát và DSLK trong mảng liên tục. Ứng dụng này có sinh ra n! cách hoán vị

Chủ đề:

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

Lưu

Nội dung Text: Cấu trúc dữ liệu ( chương 17)

Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò Chöông 17 – ÖÙNG DUÏNG SINH CAÙC HOAÙN VÒ ÖÙng duïng naøy minh hoïa söï söû duïng caû hai loaïi danh saùch: danh saùch toång quaùt vaø DSLK trong maûng lieân tuïc. ÖÙng duïng naøy seõ sinh ra n! caùch hoaùn vò cuûa n ñoái töôïng moät caùch hieäu quaû nhaát. Chuùng ta goïi caùc hoaùn vò cuûa n ñoái töôïng khaùc nhau laø taát caû caùc phöông aùn thieát laäp chuùng theo moïi thöù töï coù theå coù. Chuùng ta coù theå choïn baát kyø ñoái töôïng naøo trong n ñoái töôïng ñaët taïi vò trí ñaàu tieân, sau ñoù coù theå choïn baát kyø trong n-1 ñoái töôïng coøn laïi ñaët taïi vò trí thöù hai, vaø cöù theá tieáp tuïc. Caùc choïn löïa naøy ñoäc laäp nhau neân toång soá caùch choïn löïa laø: n x (n-1) x (n-2) x ... x 2 x 1 = n! Hình 17.1- Sinh caùc hoaùn vò cho {1, 2, 3, 4} 17.1. YÙ töôûng Chuùng ta xaùc ñònh caùc hoaùn vò qua caùc nuùt treân caây. Ñaàu tieân chæ coù 1 ôû goác caây. Chuùng ta coù hai hoaùn vò cuûa {1, 2} baèng caùch ghi 2 beân traùi, sau ñoù beân phaûi cuûa 1. Töông töï, saùu hoaùn vò cuûa {1, 2, 3} coù ñöôïc töø (2, 1) vaø (1, 2) baèng caùch theâm 3 vaøo caû ba vò trí coù theå (traùi, giöõa, phaûi). Nhö vaäy caùc hoaùn vò cuûa {1, 2, ..., k} coù ñöôïc nhö sau: Ñoái vôùi moãi hoaùn vò cuûa {1, 2, ..., k-1} chuùng ta ñöa caùc phaàn töû vaøo moät list. Sau ñoù cheøn k vaøo moïi vò trí coù theå trong list ñoù ñeå coù ñöôïc k hoaùn vò khaùc nhau cuûa {1, 2, ..., k}. Giaûi thuaät naøy minh hoïa vieäc söû duïng ñeä quy ñeå hoaøn thaønh caùc coâng vieäc ñaõ taïm hoaõn. Chuùng ta seõ vieát moät haøm, ñaàu tieân laø theâm 1 vaøo moät danh saùch roãng, Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 395
Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò sau ñoù goïi ñeä quy ñeå theâm laàn löôït caùc soá khaùc töø 2 ñeán n vaøo danh saùch. Laàn goïi ñeä quy ñaàu tieân seõ theâm 2 vaøo danh saùch chæ chöùa coù 1, giaû söû theâm 2 beân traùi cuûa 1, vaø trì hoaõn caùc khaû naêng theâm khaùc (nhö laø theâm 2 beân phaûi cuûa 1), ñeå goïi ñeä quy tieáp. Cuoái cuøng, laàn goïi ñeä quy thöù n seõ theâm n vaøo danh saùch. Baèng caùch naøy, baét ñaàu töø moät caáu truùc caây, chuùng ta phaùt trieån moät giaûi thuaät trong ñoù caây naøy trôû thaønh moät caây ñeä quy. 17.2. Tinh cheá Chuùng ta seõ phaùt trieån giaûi thuaät treân cuï theå hôn. Haøm theâm caùc soá töø 1 ñeán n ñeå sinh n! hoaùn vò seõ ñöôïc goïi nhö sau: permute(1, n) Giaû söû ñaõ coù k-1 soá ñaõ ñöôïc theâm vaøo danh saùch, haøm sau seõ theâm caùc soá coøn laïi töø k ñeán n vaøo danh saùch: void permute(int k,int n) /* pre: Töø 1 ñeán k - 1 ñaõ coù trong danh saùch caùc hoaùn vò; post: Cheøn caùc soá nguyeân töø k ñeán n vaøo danh saùch caùc hoaùn vò. */ { for // vôùi moãi vò trí trong k vò trí coù theå trong danh saùch. { // Cheøn k vaøo vò trí naøy. if (k == n) process_permutation; else permute(k + 1, n); // Laáy k ra khoûi vò trí vöøa cheøn. } } Khi coù ñöôïc moät hoaùn vò ñaày ñuû cuûa {1, 2, ..., n}, chuùng ta coù theå in keát quaû, hoaëc gôûi keát quaû nhö laø thoâng soá vaøo cho moät baøi toaùn naøo khaùc, ñoù laø nhieäm vuï cuûa haøm process_permutation. 17.3. Thuû tuïc chung Ñeå chuyeån giaûi thuaät thaønh chöông trình C++, chuùng ta coù caùc teân bieán nhö sau: danh saùch caùc soá nguyeân permutation chöùa hoaùn vò cuûa caùc soá; new_entry, thay cho k, laø soá nguyeân seõ ñöôïc theâm vaøo; vaø degree, thay cho n, laø soá caùc phaàn töû caàn hoaùn vò. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 396
Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò void permute(int new_entry, int degree, List &permutation) /* pre: permutation chöùa 1 hoaùn vò vôùi caùc phaàn töû töø 1 ñeán new_entry - 1. post: Moïi hoaùn vò cuûa degree phaàn töû ñöôïc taïo neân töø hoaùn vò ñaõ coù vaø seõ ñöôïc xöû lyù trong haøm process_permutation. uses: haøm permute moät caùch ñeä quy, haøm process_permutation, vaø caùc haøm cuûa List. */ { for (int current = 0; current < permutation.size() + 1; current++) { permutation.insert(current, new_entry); if (new_entry == degree) process_permutation(permutation); else permute(new_entry + 1, degree, permutation); permutation.remove(current, new_entry); } } Haøm treân ñaây coù theå söû duïng vôùi baát kyø hieän thöïc naøo cuûa danh saùch maø chuùng ta ñaõ laøm quen (DSLK söû duïng con troû, danh saùch lieân tuïc, DSLK trong maûng lieân tuïc). Vieäc xaây döïng öùng duïng ñaày ñuû ñeå sinh caùc hoaùn vò xem nhö baøi taäp. Tuy nhieân chuùng ta seõ thaáy raèng öu ñieåm cuûa DSLK trong maûng lieân tuïc raát thích hôïp ñoái vôùi baøi toaùn naøy trong phaàn tieáp theo döôùi ñaây.o3 17.4. Toái öu hoùa caáu truùc döõ lieäu ñeå taêng toác ñoä cho chöông trình sinh caùc hoaùn vò n! taêng raát nhanh khi n taêng. Do ñoù soá hoaùn vò coù ñöôïc seõ raát lôùn. ÖÙng duïng treân laø moät trong caùc öùng duïng maø söï toái öu hoùa ñeå taêng toác ñoä chöông trình raát ñaùng ñeå traû giaù, ngay caû khi aûnh höôûng ñeán tính deã ñoïc cuûa chöông trình. Chuùng ta seõ duøng DSLK trong maûng lieân tuïc coù keøm moät chuùt caûi tieán cho baøi toaùn treân. Chuùng ta haõy xem xeùt moät vaøi caùch toå chöùc döõ lieäu theo höôùng laøm taêng toác ñoä chöông trình caøng nhanh caøng toát. Chuùng ta söû duïng moät danh saùch ñeå chöùa caùc soá caàn hoaùn vò. Moãi laàn goïi ñeä quy ñeàu phaûi caäp nhaät caùc phaàn töû trong danh saùch. Do chuùng ta phaûi thöôøng xuyeân theâm vaø loaïi phaàn töû cuûa danh saùch, DSLK toû ra thích hôïp hôn danh saùch lieân tuïc. Maët khaùc, do toång soá phaàn töû trong danh saùch khoâng bao giôø vöôït quaù n, chuùng ta neân söû duïng DSLK trong maûng lieân tuïc thay vì DSLK trong boä nhôù ñoäng. Hình 17.2 minh hoïa caùch toå chöùc caáu truùc döõ lieäu. Hình treân cuøng laø DSLK cho hoaùn vò (3, 2, 1, 4). Hình beân döôùi bieåu dieãn hoaùn vò naøy trong DSLK trong maûng lieân tuïc. Ñaëc bieät trong hình naøy, chuùng ta nhaän thaáy, trò cuûa phaàn töû ñöôïc theâm vaøo cuõng chính baèng chæ soá cuûa phaàn töû trong array, neân vieäc löu caùc trò naøy khoâng caàn thieát nöõa. (Chuùng ta chuù yù raèng, trong giaûi thuaät ñeä quy, caùc soá ñöôïc theâm vaøo danh saùch theo thöù töï taêng daàn, neân moãi phaàn töû seõ chieám vò trí trong maûng ñuùng baèng trò cuûa noù; caùc hoaùn vò khaùc nhau cuûa caùc phaàn töû naøy ñöôïc phaân Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 397
Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò bieät bôûi thöù töï cuûa chuùng trong danh saùch, ñoù chính laø söï khaùc nhau veà caùch noái caùc tham chieáu). Cuoái cuøng chæ coøn caùc tham chieáu laø caàn löu trong maûng (hình döôùi cuøng trong hình 17.2). Node 0 duøng ñeå chöùa ñaàu vaøo cuûa DSLK trong maûng lieân tuïc. Trong chöông trình döôùi ñaây chuùng ta vieát laïi caùc coâng vieäc theâm vaø loaïi phaàn töû trong danh saùch thay vì goïi caùc phöông thöùc cuûa danh saùch ñeå taêng hieäu quaû toái ña. (entry) (next) Hình 17.2 – Caáu truùc döõ lieäu chöùa hoaùn vò 17.5. Chöông trình Chuùng ta coù haøm permute ñaõ ñöôïc caûi tieán: void permute(int new_entry, int degree, int *permutation) /* pre: permutation chöùa 1 hoaùn vò vôùi caùc phaàn töû töø 1 ñeán new_entry - 1. post: Moïi hoaùn vò cuûa degree phaàn töû ñöôïc taïo neân töø hoaùn vò ñaõ coù vaø seõ ñöôïc xöû lyù trong haøm process_permutation. uses: haøm permute moät caùch ñeä quy, haøm process_permutation. */ { int current = 0; do { permutation[new_entry] = permutation[current]; permutation[current] = new_entry; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 398
Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò if (new_entry == degree) process_permutation(permutation); else permute(new_entry + 1, degree, permutation); permutation[current] = permutation[new_entry]; current = permutation[current]; } while (current != 0); } Chöông trình chính thöïc hieän caùc khai baùo vaø khôûi taïo: main() /* pre: Ngöôøi söû duïng nhaäp vaøo degree laø soá phaàn töû caàn hoaùn vò. post: Moïi hoaùn vò cuûa degree phaàn töû ñöôïc in ra. */ { int degree; int permutation[max_degree + 1]; cout > degree; if (degree < 1 || degree > max_degree) cout
Chöông 17 – ÖÙng duïng sinh caùc hoaùn vò Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 400