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á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 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ả 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[l m-1] Nếu x > a[m] thì tìm bên a[m+1 r]

pptx29 trang | Chia sẻ: thucuc2301 | Lượt xem: 697 | Lượt tải: 2download
Bạn đang xem trước 20 trang tài liệu 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Ths.Tôn Quang ToạiTonQuangToai@yahoo.comTPHCM, 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

Các file đính kèm theo tài liệu này:

  • pptxslide_co_so_lap_trinh_nang_cao_c6_7795_2051288.pptx