Phân tích và thiết kế thuật toán - Lecture 13: Generating method

2/2/2017 1 Lecture 13 Generating Method Lecturer: Ha Dai Duong duonghd@mta.edu.vn Analysis and Design of Algorithms 2/2/2017 1 Nội dung 1. Lược đồ chung 2. Bài toán chuỗi 3 ký tự 3. Liệt kê tập con của tập N phần tử 4. Bài toán tập con K phần tử 5. Hoán vị tập N phần tử 2/2/2017 2 Nội dung 1. Lược đồ chung 2. Bài toán chuỗi 3 ký tự 3. Liệt kê tập con của tập N phần tử 4. Bài toán tập con K phần tử 5. Hoán vị tập N phần tử 2/2/2017 3 2/2/2017 2 Bài toán tổ hợp 2/2/2017 4 Ví dụ 1 2/2/2017 5 Ví dụ 2 2/2/2017 6 2/2/2017 3 Bài toán tổ hợp 2/2/2017 7 Lược đồ chung 2/2/2017 8 Thứ tự từ điển Thứ tự từ điển ngược (ngược lại với thứ tự từ điển) 2/2/2017 9 2/2/2017 4 Ví dụ 2/2/2017 10 Lược đồ chung 2/2/2017 11 Nội dung 1. Lược đồ chung 2. Bài toán chuỗi 3 ký tự 3. Liệt kê tập con của tập N phần tử 4. Bài toán tập con K phần tử 5. Hoán vị tập N phần tử 2/2/2017 12 2/2/2017 5 Bài toán 2/2/2017 13 Cài đặt 2/2/2017 14 2/2/2017 15 2/2/2017 6 Minh họa 2/2/2017 16 Nội dung 1. Lược đồ chung 2. Bài toán chuỗi 3 ký tự 3. Liệt kê tập con của tập N phần tử 4. Bài toán tập con K phần tử 5. Hoán vị tập N phần tử 2/2/2017 17 Bài toán 2/2/2017 18 2/2/2017 7 Ví dụ 2/2/2017 19 Cộng 1 đơn vị 2/2/2017 20 Cài đặt 2/2/2017 21 2/2/2017 8 Cài đặt 2/2/2017 22 Minh họa 2/2/2017 23 Nội dung 1. Lược đồ chung 2. Bài toán chuỗi 3 ký tự 3. Liệt kê tập con của tập N phần tử 4. Bài toán tập con K phần tử 5. Hoán vị tập N phần tử 2/2/2017 24 2/2/2017 9 Bài toán 2/2/2017 25 Bài toán 2/2/2017 26 Ý tưởng 2/2/2017 27 2/2/2017 10 Ý tưởng 2/2/2017 28 Cài đặt 2/2/2017 29 Cài đặt 2/2/2017 30 2/2/2017 11 Nội dung 1. Lược đồ chung 2. Bài toán chuỗi 3 ký tự 3. Liệt kê tập con của tập N phần tử 4. Bài toán tập con K phần tử 5. Hoán vị tập N phần tử 2/2/2017 31 Bài toán 2/2/2017 32 2/2/2017 33 2/2/2017 12 Ý tưởng 2/2/2017 34 Cài đặt 2/2/2017 35 Cài đặt 2/2/2017 36 2/2/2017 13 Cài đặt 2/2/2017 37 Kết quả 2/2/2017 38 Bài tập 1. Liệt kê các tập con của tập {a,b,c,d,e,f}. 2. Liệt kê các tập con 3, 4, 5 phần tử từ tập 6 phần tử. 3. Liệt kê các hoán vị của tập 3,4,5 phần tử 2/2/2017 39