Thiết kế thuật toán 2

Chia sẻ: Le Quang Duan Duan | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

126
lượt xem 36
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo thiết kế thuật toán - môn Khoa học máy tính

Chủ đề:

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

Lưu

Nội dung Text: Thiết kế thuật toán 2

Thi t k thu t toán Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT ð i H c Công Ngh - ðHQGHN Email: vinhioi@yahoo.com
Chia ñ tr (Divide and Conquer) • Chia bài toán l n thành các bài toán nh cùng d ng v i bài toán l n nhưng có kích thư c nh hơn. • Gi i quy t các bài toán nh ñ c l p • K t h p nghi m c a nh ng bài toán nh ñ thu ñư c bài toán l n
Ví d : Merge sort ð s p x p m t m ng A[start…end], ta chia m ng A thành 2 m ng con A1 và A2. S p x p A1 và A2, sau ñó hòa nh p chúng thành m t ñ ñư c mang A ñã s p x p. void MergeSort( Item A[ ], int start, int end) { if (start < end) { int mid = (start + end)/2; MergeSort ( A, start, mid ); MergeSort ( A, mid+1, end); Merge ( A, start, mid, end); } }
Ví d : Quick sort Tư tư ng c a Quick sort: Phân chia danh sách d li u c n s p x p ra thành hai ph n “ph n bên trái” và “ph n bên ph i” sao cho các ph n t ph n bên trái nh hơn ho c b ng các ph n t ph n bên ph i. Sau khi phân chia, ti p t c th c hi n “quick sort trên hai ph n d li u trên. Void quickSort (Item A[], int start, int end) { if (start < end) { pivotLocation = partition (A, start, end); quickSort (A, start, pivotLocation – 1); quickSort (A, pivotLocation + 1, end) } }
Binary search BinarySearch (lookingData, items, start, end) { if (start > end) return (-1) else { mid = (start + end) / 2; if (items[mid] == lookingData) return mid else if (items[mid] > lookingData) BinarySearch (lookingData, items, start, mid -1) else BinarySearch (lookingData, items, mid + 1, end) } }
Tìm ph n t l n nh t trong danh sách findMax (int start, int end, items) { if (start == end) return items[start] else { int med = (start + end) / 2; Item max1 = findMax (start, med, items); Item max2 = findMax (med + 1, end, items); return Max (max1, max2); } }
Chi n lư c vét c n (Backtracking) L n lư t duy t qua t t c các tr ng thái có th trong không gian tìm ki m • A = (a0, a1,..an-1): Là m t tr ng thái g m N thành ph n, n u tr ng thái A th a mãn các yêu c u c a bài toán thì g i là vector nghi m. Trong ñó ai ∈ Si • ð li t kê ñư c t t c các tr ng thái A có th , ta ti n hành g i ñ quy qua N vòng, t i bư c th i s l n lư t ti n hành th t t c các ai ∈ Si
Chi n lư c vét c n (Backtracking) Backtracking (A, i) { for ai ∈ Si { A = A ⋃ ai ; if (i < N) Backtracking (A, i+1) else CheckConfiguration (A); A = A – {ai} } }
Ví d : Li t kê t t c xâu nh phân ñ dài N Void Binary (A, i) { for (int v = 0; v < 2; v ++) { A[i] = v; if (i < N) Binary (A, i+1) else A.print (); A[i] = -1; } }
Ví d : Li t kê t t c hoán v ñ dài N Void Permutation (A, dd, i) { for (int v = 1; v
Tìm ñư ng ñi ng n nh t qua t t c các ñ nh c a ñ th
Bài toán cái ba lô Có N ñ v t, ñ v t i có kh i lư ng wi và giá tr ti. M t tên tr m có 1 chi c ba lô có th mang ñư c không qúa M kg. Hãy tìm cách mang m t s ñ v t ñ t ng giá tr l y ñư c là l n nh t.