Cấu trúc dữ liệu - Phần 6

Tài liệu tham khảo bài giảng môn Cấu trúc dữ liệu - Phần 6 Chia để trị
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu - Phần 6Phương pháp chia để trị (devide and conquer) GVGD: Trương Phước HảiNội dung 1. Phương pháp chia để trị 2. Tìm kiếm nhị phân 3. Bài toán tìm cực trị của dãy 4. Merge Sort 5. Quick Sort 2 Phương pháp chia để trị Tư tưởng Chia nhỏ bài toán lớn thành những bài toán con dễ giải  quyết hơn Để giải bài toán kích thước N Chia bài toán thành các bài toán con có kích thước nhỏ hơn.  Có thể sử dụng kỹ thuật chia để trị để tiếp tục chia nhỏ bài toán con Giải các bài toán con rồi tổng hợp lại để được lời giải cho  bài toán ban đầu 3 Phương pháp chia để trị Mô hình tổng quát của kỹ thuật chia để trị problem P … … Bài toán cơ sở p1 p2 pk (base problem) 4 Phương pháp chia để trị Các bước tiếp cận phương pháp chia để trị Bước 1: chia (divide) bài toán thành 2 hay nhiều bài toán  con nhỏ hơn Bước 2: trị (conquer) (giải) các bài toán con theo phương  pháp này một cách đệ quy Bước 3: gộp (combine) lời giải các bài toán con để tạo  thành lời giải cho bài toán ban đầu 5 Phương pháp chia để trị Giải thuật tổng quát DAC(P) If (P đủ nhỏ) Then return LờiGiải(P) Else Chia P thành các thể hiện p1, p2, ..pk Áp dụng chia để trị cho từng thể hiện pi Kết Hợp (DAC(p1), DAC(p2), ..., DAC(pk)) End If Cuối DAC 6Nội dung 1. Phương pháp chia để trị 2. Tìm kiếm nhị phân 3. Bài toán tìm cực trị của dãy 4. Merge Sort 5. Quick Sort 8 Tìm kiếm nhị phân Cho dãy A gồm N phần tử được sắp thứ tự không giảm. Cho biết phần tử x có tồn tại trong dãy A hay không, nếu có chỉ ra vị trí xuất hiện Input: A[0…N-1], x  Output  index = -1, nếu x không tồn tại trong A  index ≥ 0 nếu A[index] = x  9 Tìm kiếm nhị phân Giải thuật chia để trị cho bài toán Chia: chia dãy A thành 2 nửa dãy con  m x Trị: dựa vào tính chất có thứ tự của A để xác định nên tìm  x trong nửa dãy con nào Gộp: không cần vì tìm ngay trên dãy A  10 Tìm kiếm nhị phân Giải thuật chia để trị áp dụng cho Binary Search BinSearch(A[], l, r, x) If (l > r) Then return -1 Else m = [(l + r)/2] If (A[m] = x) Then return m Else If (x < A[m]) Then return BinSearch(A, l, m-1, x) Else return BinSearch(A, m+1, r, x) Cuối If Cuối If Cuối BinSearch 11 Tìm kiếm nhị phân Cài đặt ngôn ngữ int BinSearch(int A[], int l, int r, int x) { if (l > r) return -1 else { int m = (l + r)/2; if (A[m] == x) return m; else if (x < A[m]) return BinSearch(A, l, m – 1, x); else return BinSearch(A, m + 1, r, x); } } 12Nội dung 1. Phương pháp chia để trị 2. Tìm kiếm nhị phân 3. Bài toán tìm cực trị của dãy 4. Merge Sort 5. Quick Sort 13 Bài toán tìm cực trị của dãy Bài toán Cho dãy A gồm N phần tử, tìm giá trị lớn nhất của dãy A  Tư tưởng chia để trị Chia dãy thành 2 dãy con và tìm giá trị lớn nhất trên từng  dãy con So sánh các giá trị lớn nhất của mỗi dãy con để tìm ra giá  trị lớn nhất của dãy ban đầu 14 Bài toán tìm cực trị của dãy Minh họa tìm giá trị max của dãy bằng phương pháp chia để trị Max = 41 10, 16, 7, 39, 3, 24, 17, 41 39 41 10, 16, 7, 39 3, 24, 17, 41 39 24 41 16 10, 16 7, 39 3, 24 17, 41 10 16 7 39 3 24 17 41 15 Bài toán tìm cực trị của dãy Chia để trị cho bài toán tìm max của dãy Chia: chia dãy A[l..r] thành 2 dãy con A[l..m] và A[m+1..r]  với m = (l + r) div 2 Trị: tìm max của mỗi dãy con một cách đệ quy. Đặt left là  max của dãy A[l..m], right là max của dãy A[m+1..r] Gộp: so sánh giá trị của left và right để tìm max cho dãy  ban đầu ...