Bài giảng Thuật toán ứng dụng: Đệ quy-Quay lui-Nhánh cận cung cấp cho người học những kiến thức như: Đệ quy; Đệ quy có nhớ; Nhị phân; Tập con; Hoán vị; Phân tích; Đặt hậu; Bài toán người bán hàng (TSP – Traveling Salesman Problem). Mời các bạn cùng tham khảo! | THUẬT TOÁN ỨNG DỤNG Đệ quy Quay lui Nhánh cận Nội dung 1. Đệ quy Đệ quy Đệ quy có nhớ 2. Quay lui Nhị phân Tập con Hoán vị Phân tích Đặt hậu 3. Nhánh cận Bài toán người bán hàng TSP Traveling Salesman Problem 4. Bài tập TRƯƠNG XUÂN NAM 2 Phần 1 Đệ quy TRƯƠNG XUÂN NAM 3 Đệ quy khái niệm Hàm đệ quy Hàm có lợi gọi lại chính nó trong quá trình thực hiện Đệ quy trực tiếp gọi lại chính nó ngay trong thân hàm Đệ quy gián tiếp gọi lại chính nó thực hiện trong các hàm con in các số nguyên từ 1 đến n viết đệ quy void print int n if n gt 1 print n-1 cout Đệ quy đặc điểm Đơn giản Đệ quy phù hợp với tiếp cận từ trên xuống chia bài toán lớn thành các bài toán nhỏ Mã ngắn gọn dễ hiểu thể hiện chính xác tiếp cận top-down Chậm Chi phí thời gian cho việc gọi hàm đệ quy Một hàm có thể bị gọi lại nhiều lần Chuyển về vòng lặp khử đệ quy hầu hết các hàm đệ quy đơn single recursion hàm đệ quy chỉ gọi chính nó một lần đều có thể chuyển về vòng lặp khá đơn giản Mọi hàm đệ quy đều có thể chuyển về vòng lặp vấn đề là việc chuyển như vậy đơn giản hay phức tạp mà thôi TRƯƠNG XUÂN NAM 5 Đệ quy có nhớ Các tiếp cận đệ quy đôi khi làm cho việc gọi hàm con bùng nổ tổ hợp int fibo int n if n lt 2 return n return fibo n-1 fibo n-2 TRƯƠNG XUÂN NAM 6 Đệ quy có nhớ Giải quyết dùng bộ nhớ lưu lại kết quả để dùng lại int fibo int n if n lt 2 return n nếu chưa tính hàm fibo n thì tính và lưu vào f n if f n -1 f n fibo n-1 fibo n-2 return f n TRƯƠNG XUÂN NAM 7 Đệ quy có nhớ nguyên tắc triển khai Sử dụng bộ nhớ để lưu kết quả Tính toán những trường hợp nhỏ ghi vào bộ nhớ Những phần chưa được tính toán thì đánh dấu lại chẳng hạn như ghi tạm giá trị là -1 Khi thực hiện đệ quy Tìm trong bộ nhớ xem đã có kết quả chưa nếu có rồi thì trả ngay về kết quả đã có Nếu chưa có thì thực hiện đệ quy như bình thường lưu lại kết quả tính được vào bộ nhớ Trả về kết quả vừa tính được Chú ý không phải lúc nào cũng có thể dùng bộ nhớ để lưu lại kết quả tính toán TRƯƠNG XUÂN NAM 8 Đệ quy có nhớ ví dụ triển khai include const .
