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

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

1. 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
2. Chương 6 PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − CHIA ĐỂ TRỊ −
3. Nội dung • Giới thiệu • Phương pháp • Sơ đồ cài đặt • Các ví dụ
4. Hình ảnh
5. 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
6. 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
7. 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
8. 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 A0, A1, , An-1 - for (i=0; i<n; i++) DivideConquer(Ai, xi) - Ket hop cac nghiem xi de duoc nghiem x } }
9. Các ví dụ • Ví dụ 1 [Sorting 1]: Cho dãy a1, a2, , an. 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 Phần tử cuối n-1
10. Các ví dụ – Bước 2: Solve Sorted • Bước 3: Combine
11. 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 a1, a2, , ai – Bước 1: Sắp xếp dãy a1, a2, ai-1 tăng dần – Bước 2: Tìm vị trí thích hợp trong dãy để chèn ai vào sao cho a1, a2, , ai tăng dần
12. Các ví dụ void InsertionSort1(int a[], int i) { }
13. Các ví dụ • Thuật toán Insertion sort 2 [Vòng lặp – từ dưới lên] – a1 đã được sắp xếp – Giả sử dãy a1, a2, , ai-1 đã tăng dần – Tìm vị trí thích hợp trong dãy để chèn ai vào sao cho a1, a2, , ai tăng dần
14. Các ví dụ void InsertionSort2(int a[], int i) { }
15. Các ví dụ • Ví dụ 2 [Sorting 2]: Cho dãy a1, a2, , an. 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
16. 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
17. 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
18. 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
19. 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[1 k] – Bước 3: Sắp xếp a[(k+1) n] – Bước 4: Trộn 2 dãy đã sắp xếp a[1 k] và a[(k+1) n] thành dãy a[1 n] được sắp xếp
20. Các ví dụ void MergeSort(int a[], int i, int j) { }
21. Các ví dụ • Ví dụ 3 [Sorting 3]: Cho dãy a1, a2, , an. 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 x < y left right
22. 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
23. 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
24. Các ví dụ void QuickSort(int a[], int left, int right) { }
25. 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 y left right
26. 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 right – Bước 3: Combine • Không làm gì cả
27. 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[m+1 r]
28. Các ví dụ int BinarySearch(int a[], int left, int right, int x) { }