Cấu trúc dữ liệu và giải thuật - Chương 2: Đệ quy và Giải thuật đệ quy

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT BÀI GIẢNG Trần Đăng Hưng Khoa CNTT - ĐHSPHN Nội dung 1 September 2015 CTDL> - Trần Đăng Hưng 2  Chương 1: Giới thiệu  Chương 2: Đệ quy và Giải thuật đệ quy  Chương 3: Quy hoạch động  Chương 4: Danh sách móc nối  Chương 5: Stack và Queue  Chương 6: Cây và Ứng dụng  Chương 7: Đồ thị và Ứng dụng  Chương 8: Các thuật toán sắp xếp  Chương 9: Các thuật toán tìm kiếm Nội dung 1 September 2015 CTDL> - Trần Đăng Hưng 3  Chương 1: Giới thiệu  Chương 2: Đệ quy và Giải thuật đệ quy  Chương 3: Quy hoạch động  Chương 4: Danh sách móc nối  Chương 5: Stack và Queue  Chương 6: Cây và Ứng dụng  Chương 7: Đồ thị và Ứng dụng  Chương 8: Các thuật toán sắp xếp  Chương 9: Các thuật toán tìm kiếm Đệ quy 1 September 2015 CTDL> - Trần Đăng Hưng 4  Môt đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng khác cùng dạng với chính nó  Ví dụ: Hình ảnh phát thanh viên ngồi trên màn hình,  Trong toán học gặp nhiều công thức dạng đệ quy  Ví dụ: Tính N!, Tìm USCLN, Giải thuật đệ quy 1 September 2015 CTDL> - Trần Đăng Hưng 5  Lời giải của bài toán P được gọi là đệ quy nếu nó được thực hiện thông qua lời giải của bài toán P’ cùng dạng với nó  P’ thường nhỏ hơn P và việc giải P’ không cần dùng đến P  Hàm đệ quy gồm hai phần:  Phần neo: Được thực hiện khi lời giải đơn giản, có thể tìm được ngay mà không cần đến bài toán con nào  Phần đệ quy: Khi bài toán chưa giải được bằng phần neo, thì xác định các bài toán con và gọi đệ quy giải các bài toán con này, khi đã có lời giải các bài toán con thì phối hợp lại để được lời giải.  Phần đệ quy thể hiện tính quy nạp, phần neo thể hiện sự hữu hạn của giải thuật. Sau một số lần gọi đệ quy sẽ tiến đến phần neo. Ví dụ giải thuật đệ quy (1/2) 1 September 2015 CTDL> - Trần Đăng Hưng 6  Tìm ước số chung lớn nhất của 2 số nguyên dương  Tính giai thừa: Ví dụ giải thuật đệ quy (2/2) 1 September 2015 CTDL> - Trần Đăng Hưng 7  Dãy số fibonaxi (bài toán sinh sản của Thỏ) Trò chơi Tháp Hà Nội (1/2) 1 September 2015 CTDL> - Trần Đăng Hưng 8  Có n chiếc đĩa, và 3 cái cọc, ban đầu tất cả đĩa xếp trên 1 cọc, cần di chuyển số đĩa này sang 1 cọc khác theo nguyên tắc: Trò chơi Tháp Hà Nội (2/2) 1 September 2015 CTDL> - Trần Đăng Hưng 9 Đệ quy hỗ tương 1 September 2015 CTDL> - Trần Đăng Hưng 10  Việc gọi hàm không chỉ là tự gọi nó mà còn có gọi đến hàm khác, và hàm kia có khả năng gọi lại hàm ban đầu  Cứ như vậy tạo vòng lặp xen kẽ nhau, và tất nhiên dù là lặp dạng nào thì cũng cần có điểm dừng  Ví dụ: Nhận xét 1 September 2015 CTDL> - Trần Đăng Hưng 11  Đệ quy là một công cụ mạnh để giải các bài toán  Thiết kế giải thuật đệ quy thường đơn giản, dễ viết  Tuy nhiên, nhược điểm là tốn bộ nhớ khi phải gọi đệ quy nhiều lần, và thường không làm việc được với dữ liệu lớn  Một số thuật toán có thể khử đệ quy bằng cách sử dụng các vòng lặp  Đệ quy và quy nạp toán học quan hệ chặt chẽ, nên những bài toán có tính chất quy nạp thì có thể giải bằng đệ quy  Thường chỉ dùng đệ quy khi không còn phương án nào khác ĐỆ QUY QUAY LUI (Backtracking) 1 September 2015 CTDL> - Trần Đăng Hưng 12 Giới thiệu 1 September 2015 CTDL> - Trần Đăng Hưng 13  Thực tế có nhiều bài toán cần trả lời các câu hỏi dạng  Có bao nhiêu khả năng?  Có tồn tại hay không một khả năng?  .  Kỹ thuật quay lui là một kỹ thuật được sử dụng để tìm nghiệm của các bài toán có không gian nghiệm lớn bằng cách thử-sai và loại bỏ các khả năng.  Thông thường, ứng viên nghiệm của các bài toán này có dạng x = (x1, x2, x3,, xn); trong đó xi là thành phần thứ i.  Ý tưởng cơ bản của các thuật toán quay lui: sinh ra tất cả các khả năng có thể có của nghiệm và kiểm tra mỗi khả năng xem nó có thoả mãn các điều kiện của bài toán không Thuật toán quay lui 1 September 2015 CTDL> - Trần Đăng Hưng 14  G/s nghiệm của bài toán có dạng véc-tơ: x = (x1, x2,,xn)  Ý tưởng xây dựng nghiệm: mỗi véc-tơ nghiệm được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử lần lượt các khả năng có thể của phần tử đó.  Cụ thể, các bước thực hiện:  Xét tất cả các giá trị của x1 có thể nhận, thử cho x1 nhận lần lượt các giá trị đó, với mỗi giá trị thử gán cho x1 thì:  Xét tất cả các giá trị của x2 có thể nhận, thử cho x2 nhận lần lượt các giá trị đó, với mỗi giá trị thử gán cho x2 thì:  o Xét tất cả các giá trị của xn có thể nhận, thử cho xn nhận lần lượt các giá trị đó, kiểm tra xem bộ nghiệm (x1, x2,, xn) hiện thời có thỏa mãn các ràng buộc không. Nếu có thì thông báo nghiệm. Mô hình của thuật toán quay lui 1 September 2015 CTDL> - Trần Đăng Hưng 15 MỘT SỐ VÍ DỤ KINH ĐIỂN 1 September 2015 CTDL> - Trần Đăng Hưng 16 Bài toán liệt kê dãy nhị phân 1 September 2015 CTDL> - Trần Đăng Hưng 17  Hãy liệt kê tất cả các dãy nhị phân có độ dài n.  Ví dụ: n = 3 000 001 010 011 100 101 110 111 x[i] được nhận các giá trị 0, 1 đưa dãy x ra màn hình. Bài toán liệt kê hoán vị 1 September 2015 CTDL> - Trần Đăng Hưng 18  Liệt kê tất cả các hoán vị độ dài n.  Ví dụ: n = 3 123 132 213 231 312 321 Lưu ý: ngoài mảng x để lưu cấu hình hiện tại, cần thêm mảng C để đánh dấu các số đã được chọn. Vì các mảng để chỉ số từ 0, nên lời gọi của thủ tục là Try(0). Bài toán liệt kê tổ hợp 1 September 2015 CTDL> - Trần Đăng Hưng 19  Liệt kê các tổ hợp chập k của n phần tử.  Ví dụ: n = 5, k = 3 123 124 125 234 235 245 345 Nhận xét: vì x[1] < x[2] < x[3] << x[k], nên: x[k]  n x[k-1]  x[k] – 1  n – 1 . x[i]  n – k + i x[1]  n – k + 1 Vậy x[i-1] + 1  x[i]  n – k + i (1  i  k) Bài toán xếp hậu 1 September 2015 CTDL> - Trần Đăng Hưng 20  Trong bàn cờ kích thước n x n, cần xếp n con hậu vào các ô của bàn cờ sao cho không con nào ăn được con nào  Bài toán xếp hậu 1 September 2015 CTDL> - Trần Đăng Hưng 21  Mỗi con hậu được xếp vào 1 hàng (vì chúng ăn được theo hàng ngang)  Nên công việc chính là trên mỗi hàng cần tìm cách đặt hậu trên cột nào đó mà không bị ăn bởi các con hậu đã có  Khi đặt 1 con hậu thì các ô dưới đây bị khống chế  Cùng hàng  Cùng cột  Cùng đường chéo (có 2 đường chéo)  Các ô trên đường chéo loại 1: tổng chỉ số hàng và cột = C (2  C  2n)  Các ô trên đường chéo loại 2: hiệu chỉ số hàng và cột = C (1-n  C  n-1)  Vấn đề là khi đặt 1 con hậu lên bàn cờ, cần nhận biết các ô đã bị khống chế Bài toán xếp hậu 1 September 2015 CTDL> - Trần Đăng Hưng 22 Bài toán xếp hậu 1 September 2015 CTDL> - Trần Đăng Hưng 23  Cần sử dụng 3 mảng để đánh dấu, ghi nhận việc các ô đã bị khống chế hay chưa  A[1...n] – trong đó A[i] = true, nếu cột i chưa bị khống chế, ngược lại A[i] = false  B[2..2n] – trong đó B[i] = true, nếu đường chéo thứ i (loại 1) chưa bị khống chế, ngược lại B[i] = false  C[1-n..n-1] – trong đó C[i] = true nếu đường chéo thứ i (loại 2) chưa bị khống chế, ngược lại C[i] = false  Khởi đầu cả 3 mảng này đều có giá trị true (chưa ô nào bị khống chế) Bài toán xếp hậu 1 September 2015 CTDL> - Trần Đăng Hưng 24  Thuật toán Bài toán xếp hậu 1 September 2015 CTDL> - Trần Đăng Hưng 25