Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Trần Đăng Hưng

Nội dung chương 2 của Bài giảng Cấu trúc dữ liệu và giải thuật cung cấp cho sinh viên các kiến thức về đệ quy và giải thuật đệ quy. Tham khảo nội dung bài giảng để nắm bắt 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: Chương 2 - Trần Đăng Hưng BÀI GIẢNGCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Trần Đăng Hưng Khoa CNTT - ĐHSPHN Nội dung  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ếm2 CTDL> - Trần Đăng Hưng 1 September 2015 Nội dung  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ếm3 CTDL> - Trần Đăng Hưng 1 September 2015 Đệ quy  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,…4 CTDL> - Trần Đăng Hưng 1 September 2015 Giải thuật đệ quy  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.5 CTDL> - Trần Đăng Hưng 1 September 2015 Ví dụ giải thuật đệ quy (1/2)  Tìm ước số chung lớn nhất của 2 số nguyên dương  Tính giai thừa:6 CTDL> - Trần Đăng Hưng 1 September 2015 Ví dụ giải thuật đệ quy (2/2)  Dãy số fibonaxi (bài toán sinh sản của Thỏ)7 CTDL> - Trần Đăng Hưng 1 September 2015 Trò chơi Tháp Hà Nội (1/2) 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:8 CTDL> - Trần Đăng Hưng 1 September 2015 Trò chơi Tháp Hà Nội (2/2)9 CTDL> - Trần Đăng Hưng 1 September 2015 Đệ quy hỗ tương  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ụ:10 CTDL> - Trần Đăng Hưng 1 September 2015 Nhận xét  Đệ 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ác11 CTDL> - Trần Đăng Hưng 1 September 2015 ĐỆ QUY QUAY LUI (Backtracking)12 CTDL> - Trần Đăng Hưng 1 September 2015 Giới thiệu  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ông13 CTDL> - Trần Đăng Hưng 1 September 2015 Thuật toán quay lui  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 ...