intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Cấu trúc dữ liệu - Phần 6

Chia sẻ: Nguyen Nguyen | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
127
lượt xem 23
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo bài giảng môn Cấu trúc dữ liệu - Phần 6 Chia để trị

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cấu trúc dữ liệu - Phần 6

  1. Phương pháp chia để trị (devide and conquer) GVGD: Trương Phước Hải
  2. Nội dung 1. Phương pháp chia để trị 2. Tìm kiếm nhị phân 3. Bài toán tìm cực trị của dãy 4. Merge Sort 5. Quick Sort 2
  3. Phương pháp chia để trị  Tư tưởng Chia nhỏ bài toán lớn thành những bài toán con dễ giải  quyết hơn  Để giải bài toán kích thước N Chia bài toán thành các bài toán con có kích thước nhỏ hơn.  Có thể sử dụng kỹ thuật chia để trị để tiếp tục chia nhỏ bài toán con Giải các bài toán con rồi tổng hợp lại để được lời giải cho  bài toán ban đầu 3
  4. Phương pháp chia để trị  Mô hình tổng quát của kỹ thuật chia để trị problem P … … Bài toán cơ sở p1 p2 pk (base problem) 4
  5. Phương pháp chia để trị  Các bước tiếp cận phương pháp chia để trị Bước 1: chia (divide) bài toán thành 2 hay nhiều bài toán  con nhỏ hơn Bước 2: trị (conquer) (giải) các bài toán con theo phương  pháp này một cách đệ quy Bước 3: gộp (combine) lời giải các bài toán con để tạo  thành lời giải cho bài toán ban đầu 5
  6. Phương pháp chia để trị  Giải thuật tổng quát DAC(P) If (P đủ nhỏ) Then return LờiGiải(P) Else Chia P thành các thể hiện p1, p2, ..pk Áp dụng chia để trị cho từng thể hiện pi Kết Hợp (DAC(p1), DAC(p2), ..., DAC(pk)) End If Cuối DAC 6
  8. Nội dung 1. Phương pháp chia để trị 2. Tìm kiếm nhị phân 3. Bài toán tìm cực trị của dãy 4. Merge Sort 5. Quick Sort 8
  9. Tìm kiếm nhị phân  Cho dãy A gồm N phần tử được sắp thứ tự không giảm. Cho biết phần tử x có tồn tại trong dãy A hay không, nếu có chỉ ra vị trí xuất hiện Input: A[0…N-1], x  Output  index = -1, nếu x không tồn tại trong A  index ≥ 0 nếu A[index] = x  9
  10. Tìm kiếm nhị phân  Giải thuật chia để trị cho bài toán Chia: chia dãy A thành 2 nửa dãy con  m x Trị: dựa vào tính chất có thứ tự của A để xác định nên tìm  x trong nửa dãy con nào Gộp: không cần vì tìm ngay trên dãy A  10
  11. Tìm kiếm nhị phân  Giải thuật chia để trị áp dụng cho Binary Search BinSearch(A[], l, r, x) If (l > r) Then return -1 Else m = [(l + r)/2] If (A[m] = x) Then return m Else If (x < A[m]) Then return BinSearch(A, l, m-1, x) Else return BinSearch(A, m+1, r, x) Cuối If Cuối If Cuối BinSearch 11
  12. Tìm kiếm nhị phân  Cài đặt ngôn ngữ int BinSearch(int A[], int l, int r, int x) { if (l > r) return -1 else { int m = (l + r)/2; if (A[m] == x) return m; else if (x < A[m]) return BinSearch(A, l, m – 1, x); else return BinSearch(A, m + 1, r, x); } } 12
  13. Nội dung 1. Phương pháp chia để trị 2. Tìm kiếm nhị phân 3. Bài toán tìm cực trị của dãy 4. Merge Sort 5. Quick Sort 13
  14. Bài toán tìm cực trị của dãy  Bài toán Cho dãy A gồm N phần tử, tìm giá trị lớn nhất của dãy A   Tư tưởng chia để trị Chia dãy thành 2 dãy con và tìm giá trị lớn nhất trên từng  dãy con So sánh các giá trị lớn nhất của mỗi dãy con để tìm ra giá  trị lớn nhất của dãy ban đầu 14
  15. Bài toán tìm cực trị của dãy  Minh họa tìm giá trị max của dãy bằng phương pháp chia để trị Max = 41 10, 16, 7, 39, 3, 24, 17, 41 39 41 10, 16, 7, 39 3, 24, 17, 41 39 24 41 16 10, 16 7, 39 3, 24 17, 41 10 16 7 39 3 24 17 41 15
  16. Bài toán tìm cực trị của dãy  Chia để trị cho bài toán tìm max của dãy Chia: chia dãy A[l..r] thành 2 dãy con A[l..m] và A[m+1..r]  với m = (l + r) div 2 Trị: tìm max của mỗi dãy con một cách đệ quy. Đặt left là  max của dãy A[l..m], right là max của dãy A[m+1..r] Gộp: so sánh giá trị của left và right để tìm max cho dãy  ban đầu 16
  17. Bài toán tìm cực trị của dãy  Giải thuật tìm max theo phương pháp chia để trị Max(A[], l, r) If (l = r) Then return A[l] Cuối If m = (l + r) div 2 left = Max(A, l, m) right = Max(A, m + 1, r) return (left> right)?left:right Cuối Max 17
  18. Bài toán tìm cực trị của dãy  Cài đặt ngôn ngữ int Max(int A[], int l, int r) { if (l == r) return A[l]; int m = (l + r)/2; int maxL = Max(A, l, m); int maxR = Max(A, m + 1, r); return (maxL > maxR)? maxL: maxR; } 18
  19. Nội dung 1. Phương pháp chia để trị 2. Tìm kiếm nhị phân 3. Bài toán tìm cực trị của dãy 4. Merge Sort 5. Quick Sort 19
  20. Merge Sort  Ý tưởng phương pháp trộn tự nhiên Tách và phân phối luân phiên các đường chạy trên A vào 2  dãy B và C Trộn lần lượt từng cặp đường chạy trên B và C vào A với  mục đích giảm dần số đường chạy trên A Dãy được sắp thứ tự nếu chỉ tồn tại 1 đường chạy  20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2