tailieunhanh - Bài giảng Thuật toán ứng dụng: Đệ quy-Quay lui-Nhánh cận - Trương Xuân Nam

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 .

• Cơ sở dữ liệu
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Hàm đệ quy
• Quy tắc xây dựng phần tử
• Nhánh cận
• Chiến lược tìm kiếm tối ưu tổ hợp
• Phân tích Thuật toán
• Quy hoạch động
• Cài đặt thuật toán
• Thuật toán Tham lam
• Ý tưởng tham lam
• Bài toán lập lịch
• Tiếp cận tham lam
• Toán ứng dụng
• Bài giảng Toán ứng dụng
• Biểu diễn đồ thị
• Thuật toán tìm kiếm
• Bài toán đường đi ngắn nhất
• Thuật toán Floyd
• Tiếp cận chia để trị
• Bài toán tháp Hà Nội
• Bài toán tính giá trị đa thức
• Bài toán đếm số dãy con
• Bài giảng Ma trận
• Khái niệm thuật toán
• Thuật toán trong tin học
• Phương pháp biểu diễn thuật toán
• Cấu trúc dữ liệu
• Chương trình nhân hai số nguyên
• Kỹ năng phân loại bài toán
• Kỹ năng phân tích thuật toán
• Quay lui đệ qui
• Bài toán quy hoạch động
• Thuật toán quay lui
• Liệt kê nhị phân
• Đệ quy quay lui
• Bài toán liệt kê xâu nhị phân
• Phương trình tuyến tính
• Thuật toán nhánh và cận
• Chu trình Euler
• Thuật toán Dijkstra
• Thuật toán Kruskal
• Disjoint set structure
• Bài toán xếp ba lô
• Bài toán dãy con chung dài nhất
• Phân tích về quy hoạch động
• Biểu diễn đồ thị trong máy tính
• Thuật toán Floyd Warshall
• Đồ thị phẳng
• Thư viện cấu trúc dữ liệu
• Cấu trúc dữ liệu mở
• Thuật toán Dequeue
• Chia để trị
• Thuật toán chia để trị
• Công thức truy hồi
• Tìm kiếm nhị phân
• Thuật toán Tarjan DFS
• Duyệt theo chiều sâu
• Cấu trúc dữ liệu duy trì
• Cấu trúc dữ liệu trừu tượng
• Giải thuật tìm kiếm
• Cài đặt tìm kiếm ở thư viện
• Danh sách tuyến tính
• Quan hệ tuyến tính
• Ngăn xếp dữ liệu
• Dãy con cực đại
• Dãy con tăng dần dài nhất
• Dãy con chung dài nhất
• Thuật toán nâng cao
• Bài giảng Thuật toán nâng cao
• Thuật toán quay lui tổng quát
• Ứng dụng của thuật toán quay lui
• Chuỗi nhị phân
• Bài giảng Lý thuyết tài chính ứng dụng
• Lý thuyết tài chính ứng dụng
• Kế toán doanh nghiệp
• Bản chất cuả tài chính
• Chức năng của tài chính
• Vai trò của tín dụng
• Tài chính doanh nghiệp
• Bài giảng Tin học 10 bài 8
• Bài giảng điện tử Tin học 10
• Bài giảng lớp 10 Tin học
• Bài giảng điện tử lớp 10
• Quy trình quản lý tin học
• Giải các bài toán khoa học kĩ thuật
• Những ứng dụng của tin học
• Bài giảng Kỹ thuật điện tử
• Kỹ thuật điện tử
• Vi mạch khuếch đại thuật toán
• Vi mạch thuật toán
• Thông số kỹ thuật vi mạch thuật toán
• Ứng dụng vi mạch thuật toán
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Cấu trúc dữ liệu và thuật toán
• Ứng dụng cây gia phả
• Ứng dụng cây thư mục
• Thiết kế thuật toán
• Bài giảng Phân tích thuật toán
• Thuật toán hoán vị
• Số nghịch thế
• Bảng nghịch thế
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Thuật toán tìm kiếm theo chiều sâu
• Thuật toán tìm kiếm theo chiều rộng
• Ứng dụng thuật toán tìm kiếm đồ thị