Bài giảng Cấu trúc dữ liệu và giải thuật: Quy hoạch động - TS. Đào Nam Anh

Bài giảng Cấu trúc dữ liệu và giải thuật: Quy hoạch động cung cấp cho người học các kiến thức về chia để trị, tìm số lớn nhất – theo cách chia và trị, quy hoạch động, bài toán cái túi. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Quy hoạch động - TS. Đào Nam AnhDATA STRUCTURE AND ALGORITHMDynamic ProgrammingCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTQui hoạch độngDr. Dao Nam AnhData Structure and Algorithm1Resource - ReferenceSlides adapted from James B D Joshi,edit by Dao Nam Anh.Major Reference:•Robert Sedgewick, and Kevin Wayne,“Algorithms” Princeton University, 2011, AddisonWesley•Algorithm in C (Parts 1-5 Bundle)- Third Editionby Robert Sedgewick, Addison-Wesley••Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường.Giải thuật và lập trình, Lê Minh Hoàng, Đại HọcSư Phạm, 2002Data Structure and Algorithm2Divide and ConquerChia và Trị•Một số chương trình đệ qui gọi chính nó cho haitập dữ liệu có kích thước ½ Chia vấn đề này thành 2 phần và thực hiện từngphần••Chi phí thời gian: TN = Tk + TN-k + 1Many recursive programs use recursive calls on two subsets of inputs(two halves usually) Divide the problem and solve them – divide and conquer paradigm Complexity: TN = Tk + TN-k + 1Data Structure and Algorithm3Find max- Divide and ConquerTìm số lớn nhất – theo cách chia và trị2 317Item max(Item a[], int l, int r){ Item u, v;int m = (l+r)/2;if (l == r) return a[l];u = max(a, l, m);v = max(a, m+1, r);if (u > v) return u;else return v;}Data Structure and Algorithm4Find max- Divide and ConquerTìm số lớn nhất – theo cách chia và trị12 31722 31 7Item max(Item a[], int l, int r){ Item u, v;int m = (l+r)/2;if (l == r) return a[l];u = max(a, l, m);v = max(a, m+1, r);if (u > v) return u;else return v;}Data Structure and Algorithm5