Bài giảng Cơ sở lập trình nâng cao - Chương 6: Phương pháp thiết kế thuật toán Chia để trị - Tôn Quang Toại

CƠ SỞ LẬP TRÌNH NÂNG CAO 
Biên soạn: Ths.Tôn Quang Toại 
TonQuangToai@yahoo.com 
TPHCM, NĂM 2013 
TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCM 
KHOA CÔNG NGHỆ THÔNG TIN 
PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − CHIA ĐỂ TRỊ − 
Chương 6 
Nội dung 
Giới thiệu 
Phương pháp 
Sơ đồ cài đặt 
Các ví dụ 
Hình ảnh 
Giới thiệu 
Chia để trị là phương pháp thiết kế thuật toán từ trên xuống dưới (top – down) với ý tưởng: 
Chia bài toán lớn thành những bài toán nhỏ hơn có dạng giống bài toán ban đầu 
Các bài toán nhỏ hơn được chia thành những bài toán nhỏ hơn nữa 
với hy vọng rằng các bài toán nhỏ dễ giải hơn 
Phương pháp 
Phương pháp Chia để trị gồm 3 bước: 
Bước 1 [ Divide ] – Chia bài toán thành các phần. 
Bước 2 [ Solve ] – Giải quyết các phần 
Bước 3 [ Combine ] – Kết hợp các lời giải của các phần thành lời giải của bài toán 
Phương pháp 
Nhận xét quan trọng: 
Các bài toán con (các phần) nhận được trong quá trình phân chia sẽ cùng dạng với bài toán ban đầu, chỉ khác nhau về kích thước 
Có thể có một số bài toán con không cùng dạng với bài toán lớn 
Các bài toán con Không được giao nhau 
Sơ đồ cài đặt 
Cài đặt bằng phương pháp Đệ qui 
void DivideConquer(A, x){	 if (A du nho) Solve(A)	 else 	{	- Phan chia A thanh A 0 , A 1 , , A n-1 	- for (i=0; i<n; i++)	DivideConquer(A i , x i )	- Ket hop cac nghiem x i de duoc nghiem x	}} 
Các ví dụ 
Ví dụ 1 [Sorting 1]: Cho dãy a 1 , a 2 , , a n . Hãy xây dựng thuật toán sắp xếp dãy trên tăng dần. 
n-1 
Phần tử cuối 
Bước 1: Divide 
Các ví dụ 
Bước 2: Solve 
Sorted 
Bước 3: Combine 
Các ví dụ 
Thuật toán Insertion sort 1 [Đệ quy – từ trên xuống]: Giả sử cần sắp xếp dãy a 1 , a 2 , , a i 
Bước 1: Sắp xếp dãy a 1 , a 2 , a i-1 tăng dần 
Bước 2: Tìm vị trí thích hợp trong dãy để chèn a i vào sao cho a 1 , a 2 , , a i tăng dần 
Các ví dụ 
cài đặt 
void InsertionSort1( int a[], int i){} 
Các ví dụ 
Thuật toán Insertion sort 2 [Vòng lặp – từ dưới lên] 
a 1 đã được sắp xếp 
Giả sử dãy a 1 , a 2 , , a i-1 đã tăng dần 
Tìm vị trí thích hợp trong dãy để chèn a i vào sao cho a 1 , a 2 , , a i tăng dần 
Các ví dụ 
cài đặt 
void InsertionSort2( int a[], int i){} 
Các ví dụ 
Ví dụ 2 [Sorting 2]: Cho dãy a 1 , a 2 , , a n . Hãy xây dựng thuật toán sắp xếp dãy trên tăng dần. 
Bước 1: Divide 
Chia thành 2 phần “bằng nhau” 
Bước 2: Solve 
Sắp xếp mỗi phần tăng dần 
Các ví dụ 
Bước 3: Combine 
Kết hợp 2 phần đã sắp xếp thành 1 phần được sắp xếp 
Sorted 
Sorted 
Sorted 
Các ví dụ 
Phương pháp trộn 2 dãy đã được sắp xếp thành 1 dãy được sắp xếp 
A 
B 
C 
Các ví dụ 
Phương pháp trộn 2 dãy đã được sắp xếp thành 1 dãy được sắp xếp 
A 
B 
C 
Các ví dụ 
Thuật toán Merge sort 
Bước 1: Tính k = n div 2 
Bước 2: Sắp xếp a[1k] 
Bước 3: Sắp xếp a[(k+1)n] 
Bước 4: Trộn 2 dãy đã sắp xếp a[1k] và a[(k+1)n] thành dãy a[1n] được sắp xếp 
Các ví dụ 
cài đặt 
void MergeSort( int a[], int i, int j){} 
Các ví dụ 
Ví dụ 3 [Sorting 3]: Cho dãy a 1 , a 2 , , a n . Hãy xây dựng thuật toán sắp xếp dãy trên tăng dần. 
Bước 1: Divide 
Chia thành 2 phần 
x 
y 
left 
right 
x < y 
Các ví dụ 
Bước 2: Solve 
Sắp xếp phần bên trái và phần bên phải 
x 
y 
left 
right 
sorted 
sorted 
Bước 3: Combine 
Đặt 2 phần kề nhau 
Các ví dụ 
Thuật toán Quick sort 
Bước 1: Chọn phần tử trung tâm p 
Bước 2: Chia làm 2 phần 
Phần bên trái: Gồm những phần tử nhỏ hơn p 
Phần bên phải: Gồm những phần tử lớn hơn hay bằng p 
Bước 3: Sắp xếp phần bên trái và phần bên phải một cách đệ quy 
Các ví dụ 
cài đặt 
void QuickSort( int a[], int left, int right){} 
Các ví dụ 
Ví dụ 4: [Tìm kiếm nhị phân] 
Bài toán: Cho dãy đã được sắp xếp tăng. Hãy kiểm tra xem x có trong dãy hay không 
Bước 1: Divide 
left 
right 
y 
Các ví dụ 
Bước 2: Solve 
Kiểm tra x với y: 
x = y Tìm thấy 
x < y: Tìm bên left 
x > y: Tìm bên right 
Bước 3: Combine 
Không làm gì cả 
Các ví dụ 
Thuật toán Binary search: Tìm kiếm x có trong dãy a[l r] 
Bước 1: Nếu l>r thì không tìm thấy 
Bước 2: Tính m = (l+r)/2 
Bước 3: 
Nếu x = a[m] thì tìm thấy 
Nếu x < a[m] thì tìm bên a[lm-1] 
Nếu x > a[m] thì tìm bên a[m+1r] 
Các ví dụ 
cài đặt 
int BinarySearch( int a[], int left, int right, int x){} 
HẾT CHƯƠNG 6