thiết kế và đánh giá thuật toán - trần tuấn minh -3

CHƯƠNG 2 : PHƯƠNG PHÁP CHIA ĐỂ TRỊ (Divide - and - conquer) I. Mở đầu 1. Ý tưởng Có lẽ quan trọng và áp dụng rộng rãi nhất là kỹ thuật thiết kế “Chia để trị” . Nó phân rã bài toán kích thước n thành các bài toán con nhỏ hơn mà việc tìm lời giải của chúng là cùng một cách. Lời giải của bài toán đã cho được xây dựng từ lời giải của các bài toán con này . Ta có thể nói vắn tắt ý tưởng chính của phương pháp này là : chia dữ liệu thành từng...
Nội dung trích xuất từ tài liệu:
thiết kế và đánh giá thuật toán - trần tuấn minh -3 Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 33 - CHÖÔNG 2 : PHÖÔNG PHAÙP CHIA ÑEÅ TRÒ (Divide - and - conquer) I. Môû ñaàu 1. YÙ töôûng Coù leõ quan troïng vaø aùp duïng roäng raõi nhaát laø kyõ thuaät thieát keá “Chia ñeå trò” . Noù phaân raõ baøi toaùn kích thöôùc n thaønh caùc baøi toaùn con nhoû hôn maø vieäc tìm lôøi giaûi cuûa chuùng laø cuøng moät caùch. Lôøi giaûi cuûa baøi toaùn ñaõ cho ñöôïc xaây döïng töø lôøi giaûi cuûa caùc baøi toaùn con naøy . Ta coù theå noùi vaén taét yù töôûng chính cuûa phöông phaùp naøy laø : chia döõ lieäu thaønh töøng mieàn ñuû nhoû, giaûi baøi toaùn treân caùc mieàn ñaõ chia roài toång hôïp keát quaû laïi. 2. Moâ hình Neáu goïi D&C(ℜ) - Vôùi ℜ laø mieàn döõ lieäu - laø haøm theå hieän caùch giaûi baøi toaùn theo phöông phaùp chia ñeå trò thì ta coù theå vieát : void D&C(ℜ) { If (ℜ ñuû nhoû) giaûi baøi toaùn; Else { Chia ℜ thaønh ℜ1 , …,ℜm ; for (i = 1; i Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 34 - ⎧1; x ∈ a Output : ⎨ ⎩0; x ∉ a Moâ taû : Tknp(a, x, Ñaàu, Cuoái) ≡ If (Ñaàu > Cuoái) return 0 ; {daõy troáng} Else { Giöõa = (Ñaàu + cuoái) / 2; If (x == a[Giöõa]) return 1; else if (x > a[Giöõa]) Tknp(a, x, Giöõa + 1, Cuoái) ; else Tknp(a, x, Ñaàu, Giöõa - 1) ; } 4. Ñoä phöùc taïp thôøi gian cuûa thuaät toaùn a) Tröôøng hôïp toát nhaát : töông öùng vôùi söï tìm ñöôïc x trong laàn so saùnh ñaàu tieân, töùc laø : a[Giöõa] == a[n/2] == x ( x naèm ôû vò trí giöõa maûng ). Ta coù : Ttoát (n) = O(1). b) Tröôøng hôïp xaáu nhaát : Ñoä phöùc taïp laø O(lg n). Thaät vaäy, Neáu goïi T(n) laø ñoä phöùc taïp cuûa thuaät toaùn , thì sau khi kieåm tra ñieàu kieän ( x == a[giöõa]) vaø sai thì goïi ñeä qui thuaät toaùn naøy vôùi döõ lieäu giaûm nöûa, neân thoûa maõn coâng thöùc truy hoài : T(n) = 1 + T[n/2] ; n ≥ 2 vaø T[1] = 0. 5. Caøi ñaët int tknp(int a[max],int x,int l, int r) { int mid; if ( l > r ) return 0; mid = (l+r)/2; if ( x == a[mid] ) return 1; if ( x > a[mid] ) return tknp(a,x,mid+1,r); return tknp(a,x,l,mid-1); } Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 35 - III. Baøi toaùn MinMax 1. Phaùt bieåu baøi toaùn Tìm giaù trò Min, Max trong ñoaïn a[l..r] cuûa maûng a[1..n]. 2. YÙ töôûng Taïi moãi böôùc, chia ñoâi ñoaïn caàn tìm roài tìm Min, Max cuûa töøng ñoaïn, sau ñoù toång hôïp laïi keát quaû. Neáu ñoaïn chia chæ coù 1 phaàn töû thì Min = Max vaø baèng phaàn töû ñoù. Minh hoïa : i 1 2 3 4 5 6 7 8 a[i] 10 1 5 0 9 3 15 19 Tìm giaù trò Min, Max trong ñoaïn a[2..7] cuûa maûng a[1..7] . Kyù hieäu : MinMax(a,l,r,Min,Max) cho Min vaø Max trong ñoaïn a[l..r]. MinMax(a,2,7,Min,Max) Cho Min = 0 vaø Max = 15 trong ñoaïn a[2..7] 3. Thuaät toaùn Input : a[l..r], ( l ≤ r ) Output : Min = Min (a[l],..,a[r]), Max = Max (a[l],..,a[r]). Moâ taû : MinMax(a,l, r, Min, Max) ≡ if (l == r) { Min = a[l]; Max = a[l]; } ...