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 CAOBiên soạn: Ths.Tôn Quang Toạ[email protected], NĂM 2013TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCMKHOA CÔNG NGHỆ THÔNG TINPHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − CHIA ĐỂ TRỊ −Chương 6Nội dungGiới thiệuPhương pháp Sơ đồ cài đặtCác ví dụHình ảnhGiới thiệuChia để 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 đầuCác bài toán nhỏ hơn được chia thành những bài toán nhỏ hơn nữavới hy vọng rằng các bài toán nhỏ dễ giải hơnPhương phápPhươ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ầnBướ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ánPhương phápNhậ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ướcCó thể có một số bài toán con không cùng dạng với bài toán lớnCác bài toán con Không được giao nhauSơ đồ cài đặtCài đặt bằng phương pháp Đệ quivoid 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 rightBước 3: CombineKhô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ấyBước 2: Tính m = (l+r)/2Bước 3: Nếu x = a[m] thì tìm thấyNếu x a[m] thì tìm bên a[m+1r]Các ví dụcài đặtint BinarySearch(int a[], int left, int right, int x){}HẾT CHƯƠNG 6