TAILIEUCHUNG - 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. nội dung chi tiết. | DATA STRUCTURE AND ALGORITHM Dynamic Programming CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Qui hoạch động Dr. Dao Nam Anh Data Structure and Algorithm 1 Resource - Reference Slides adapted from James B D Joshi, edit by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by 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ọc Sư Phạm, 2002 Data Structure and Algorithm 2 Divide and Conquer Chia và Trị • Một số chương trình đệ qui gọi chính nó cho hai tậ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ừng phần • • Chi phí thời gian: TN = Tk + TN-k + 1 Many 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 + 1 Data Structure and Algorithm 3 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị 2 317 Item 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 Algorithm 4 Find max- Divide and Conquer Tìm số lớn nhất – theo cách chia và trị 1 2 317 2 2 3 1 7 Item 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 .
đang nạp các trang xem trước