Bài giảng chuyên đề Phân tích và thiết kế thuật toán - Chia để trị cung cấp cho người học các kiến thức: Ý tưởng chia để trị, lược đồ giản thuật, một số bài toán điển hình. | Chia để trị Bài giảng chuyên đề quot Phân tích thiết kế thuật toán quot Ngày 4 tháng 5 năm 2020 Chia để trị 1 20 Nôi dung 1 Ý tưởng chia để trị 2 Lược đồ giải thuật 3 Một số bài toán điển hình Chia để trị 2 20 Ý tưởng chia để trị Nội dung 1 Ý tưởng chia để trị 2 Lược đồ giải thuật 3 Một số bài toán điển hình Chia để trị 2 20 Ý tưởng chia để trị Ý tưởng Phương pháp thiết kế dựa trên hai thao tác chính Chia Divide phân rã bài toán ban đầu thành các bài toán con có kích thước nhỏ hơn có cùng cách giải. Trị Conquer giải từng bài toán con theo cách tương tự bài toán đầu - đệ qui rồi tổng hợp các lời giải để nhận kết quả của bài toán ban đầu. Việc phân rã được thực hiện trên miền dữ liệu chia miền dữ liệu thành các miền nhỏ hơn tương đương với một bài toán con Chia để trị 3 20 Lược đồ giải thuật Mô hình - Lược đồ giải thuật Mô hình Xét bài toán trên miền dữ liệu R D amp C R là hàm thể hiện cách giải bài toán trên miền dữ liệu R theo phương pháp chia để trị. Nếu R có thể phân rã thành n miền con R R1 R2 . Rn Lược đồ giải thuật D amp C R if R R0 Giải D amp C R0 else Chia miền R thành R1 R2 . Rn for i 1 i Một số bài toán điển hình Nội dung 1 Ý tưởng chia để trị 2 Lược đồ giải thuật 3 Một số bài toán điển hình Chia để trị 4 20 Một số bài toán điển hình Bài toán tìm kiếm nhị phân trên mảng được sắp Bài toán 1 Cho mảng a có n phần tử được sắp theo thứ tự tăng dần và một giá trị x bất kỳ. Kiểm tra xem phần tử x có trong mảng hay không Chia để trị 5 20 Một số bài toán điển hình Bài toán tìm kiếm nhị phân trên mảng được sắp Bài toán 1 Cho mảng a có n phần tử được sắp theo thứ tự tăng dần và một giá trị x bất kỳ. Kiểm tra xem phần tử x có trong mảng hay không Ý tưởng Chia đôi mảng mỗi lần so sánh phần tử giữa với x nếu phần tử x nhỏ hơn thì xét nửa trái ngược lại xét nửa phải Chia để trị 5 20 Một số bài toán điển hình Bài toán tìm kiếm nhị phân trên mảng được sắp Lược đồ thuật toán BinarySearch a x l r if l r x al l -1 else m m l 2 if x am return m else if x lt am BinarySearch a
