Chương 6 Phương pháp thiết kế thuật toán − Chia để trị −

Click to edit Master text styles Second level Third level Fourth level Fifth level Click to editMaster title style ‹#› 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 A0, A1, …, An-1  - for (i=0; i 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[m+1…r] Các ví dụ cài đặt int BinarySearch(int a[], int left, int right, int x){} Tóm tắt chương 6