Bài giảng Thuật toán ứng dụng - Chương 4: Chia để trị - Phạm Quang Dũng

Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn THUẬT TOÁN ỨNG DỤNG 1 CHIA ĐỂ TRỊ NộI dung  Tổng quan chia để trị  Ví dụ minh họa  Độ phức tạp chia để trị  Giảm để trị 2 Tổng quan chia để trị  Chia bài toán cần giải ban đầu thành các bài toán con độc lập nhau  Giải (trị) các bài toán con  Tổng hợp lời giải của các bài toán con để dẫn ra lời giải của bài toán xuất phát 3 Ví dụ minh họa  Bài toán dãy con dài nhất: cho dãy số nguyên a = a1, a2, , an. Tìm dãy con gồm một số liên tiếp các phần tử có tổng lớn nhất  Phân chia: ký hiệu P(i, j) là lời giải của bài toán tìm dãy con liên tiếp của dãy ai, ai+1,, aj có tổng cực đại  Tổng hợp lời giải  Ký hiệu PL(i, j) là lời giải của bài toán tìm dãy con liên tiếp của dãy ai, ai+1,, aj sao cho phần tử cuối cùng là aj có tổng cực đại  Ký hiệu PR(i, j) là lời giải của bài toán tìm dãy con liên tiếp của dãy ai, ai+1,, aj sao cho phần tử đầu tiên là ai có tổng cực đại 4 Ví dụ minh họa  Xét đoạn [l,l+1,...,r]. Ký hiệu m = (l+r)/2  P(l,r) = MAX{P(l, m), P(m+1,r), PL(l,m) + PR(m+1,r)} 5 l rm m+1P(l,m) P(m+1,r) PL(l,m) PR(m+1,r) Ví dụ minh họa #include using namespace std; #define INF 1e9 #define MAX 1000000 int a[MAX]; int n; void input(){ cin >> n; for(int i = 0; i > a[i]; } 6 Ví dụ minh họa int PL(int l, int r){ int rs = -INF; int s = 0; for(int i = r; i >= l; i--){ s += a[i]; rs = max(rs,s); } return rs; } int PR(int l, int r){ int rs = -INF; int s = 0; for(int i = l; i <= r; i++){ s += a[i]; rs = max(rs,s); } return rs; } 7 Ví dụ minh họa int P(int l, int r){ if(l == r) return a[r]; int m = (l+r)/2; return max(max(P(l,m),P(m+1,r)), PL(l,m)+PR(m+1,r)); } void solve(){ cout << P(0,n-1); } int main(){ input(); solve(); } 8 Độ phức tạp tính toán 9  Chia bài toán xuất phát thành a bài toán con, mỗi bài toán con kích thước n/b  T(n): thời gian của bài toán kích thước n  Thời gian phân chia (dòng 4): D(n)  Thời gian tổng hợp lời giải (dòng 6): C(n)  Công thức truy hồi: T = Q 1 , ≤ 0 + + , > 0 procedure D-and-C(n) { 1. if(n  n0) 2. xử lý trực tiếp 3. else{ 4. chia bài toán xuất phát thành a bài toán con kích thước n/b 5. gọi đệ quy a bài toán con 6. tổng hợp lời giải 7. } } Độ phức tạp tính toán 10  Độ phức tạp của thuật toán chia để trị (định lí thợ)  Công thức truy hồi: T(n) = aT(n/b) + cnk, với các hằng số a  1, b > 1, c > 0  Nếu a > bk thì T(n) = Q()  Nếu a = bk thì T(n) = Q() với logn =  Nếu a < bk thì T(n) = Q() Độ phức tạp tính toán 11  Độ phức tạp của thuật toán chia để trị (định lí thợ)  Công thức truy hồi: T(n) = aT(n/b) + cnk, với các hằng số a  1, b > 1, c > 0  Nếu a > bk thì T(n) = Q()  Nếu a = bk thì T(n) = Q() với logn =  Nếu a < bk thì T(n) = Q()  Thuật toán chia để trị giải bài toán tổng con cực đại có độ phức tạp là O(nlogn) Sắp xếp trộn 12  Phân chia: Chia dãy a1, , an thành 2 dãy con có độ dài bằng nhau  Trị đệ quy: Sắp xếp 2 dãy con bằng thuật toán sắp xếp trộn  Tổng hợp: Trộn 2 dãy con đã được sắp với nhau để thu được dãy ban đầu được sắp thứ tự Sắp xếp trộn 13  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 i j ta a k Sắp xếp trộn 14  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 i j 1ta a k Sắp xếp trộn 15  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 i j 1 3ta a k Sắp xếp trộn 16  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 i j 1 3 4ta a k Sắp xếp trộn 17  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 i j 1 3 4 5ta a k Sắp xếp trộn 18  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 i j 1 3 4 5 8ta a k Sắp xếp trộn 19  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 i j 1 3 4 5 8 9ta a k Sắp xếp trộn 20  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 i j 1 3 4 5 8 9 10ta a k Sắp xếp trộn 21  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 i j 1 3 4 5 8 9 10 11ta a k Sắp xếp trộn 22  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 j 1 3 4 5 8 9 10 11 20 23ta a k Sắp xếp trộn 23  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 8 9 20 4 5 10 11 23 1 3 4 5 8 9 10 11 20 23ta a copy Sắp xếp trộn 24  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp 1 3 4 5 8 9 10 11 20 23 1 3 4 5 8 9 10 11 20 23ta a Sắp xếp trộn 25 #include using namespace std; #define MAX 1000000 int a[MAX]; int n; int ta[MAX]; void input(){ cin >> n; for(int i = 0; i > a[i]; } void print(){ for(int i = 0; i < n; i++) cout << a[i] << " "; } Sắp xếp trộn 26 void merge(int b, int m, int e){ int i = b; int j = m+1; for(int k = b; k <= e; k++){ if(i > m){ ta[k] = a[j]; j++; } else if(j > e){ta[k] = a[i]; i++;} else{ if(a[i] > a[j]){ta[k] = a[j]; j++;} else{ta[k] = a[i]; i++;} } } for(int k = b; k <= e; k++) a[k] = ta[k]; } Sắp xếp trộn 27 void mergeSort(int b, int e){ if(b == e) return; int m = (b+e)/2; mergeSort(b,m); mergeSort(m+1,e); merge(b,m,e); } int main(){ input(); mergeSort(0,n-1); print(); return 0; } Giảm để trị 28  Chia bài toán (chia theo dữ liệu) xuất phát thành các bài toán con  Giải 1 bài toán con và dẫn ra lời giải của bài toán xuất phát (các bài toán con khác không cần giải  tránh dư thừa)  Tìm kiếm nhị phân  Tính lũy thừa Tìm kiếm nhị phân 29 Mã giả bSearch(a,left, right, x){ if left = right then{ if a[left] = x return left; else return NOT_FOUND; } mid = (left + right)/2; if a[mid] = x then return mid; if a[mid] < x return bSearch(a,mid+1, right, x); else return bSearch(a,left, mid-1, x); } Độ phức tạp O(logn), với n là độ dài dãy từ chỉ số left đến chỉ số right Tính xn 30 Mã giả exp(x,n){ if n = 1 then return x; n2 = n/2; a = exp(x,n2); if n mod 2 = 0 then return a*a; else return a*a*x; } Độ phức tạp O(logn) Bài tập ví dụ 31  EXPMOD  Cho số nguyên dương x và N, hãy tính xN mod 109+7  TRIPLE  Cho dãy N số nguyên dương a1, a2, , aN và số nguyên dương K. Hãy đếm xem có bao nhiêu bộ chỉ số (i,j,k) sao cho 1 ≤ i < j < k ≤ N và ai + aj + ak = K