BÀI GIẢNG GIẢI THUẬT VÀ LẬP TRÌNH - QUY HOẠCH ĐỘNG - LÊ MINH HOÀNG - 1

Ta đã trình bày phép tìm kiếm trong một tập hợp để tìm ra bản ghi mang khoá đúng bằng khoá tìm kiếm. Tuy nhiên, người ta có thể yêu cầu tìm bản ghi mang khoá lớn hơn hay nhỏ hơn khoá tìm kiếm, tìm bản ghi mang khoá nhỏ nhất mà lớn hơn khoá tìm kiếm, tìm bản ghi mang khoá lớn nhất mà nhỏ hơn khoá tìm kiếm v.v… Để cài đặt những thuật toán nêu trên cho những trường hợp này cần có một sự mềm dẻo nhất định. Cũng tương tự như sắp xếp, ...
Nội dung trích xuất từ tài liệu:
BÀI GIẢNG GIẢI THUẬT VÀ LẬP TRÌNH - QUY HOẠCH ĐỘNG - LÊ MINH HOÀNG - 1LÊ MINH HOÀNG Bài giảng chuyên đề Đại học Sư phạm Hà Nội, 1999-2002 Lời cảm ơnTôi muốn bày tỏ lòng biết ơn đối với những người thầy đã chỉ dạy tận tình trong những năm thángđầy khó khăn khi tôi mới bước vào học tin học và lập trình. Sự hiểu biết và lòng nhiệt tình của cácthầy không những đã cung cấp cho tôi những kiến thức quý báu mà còn là tấm gương sáng cho tôinoi theo khi tôi đứng trên bục giảng cũng với tư cách là một người thầy.Cuốn tài liệu này được viết dựa trên những tài liệu thu thập được từ nhiều nguồn khác nhau, bởicông sức của nhiều thế hệ thầy trò đã từng giảng dạy và học tập tại Khối Phổ thông chuyên Toán-Tin, Đại học Sư phạm Hà Nội, còn tôi chỉ là người tổng hợp lại. Qua đây, tôi muốn gửi lời cảm ơntới các đồng nghiệp đã đọc và đóng góp những ý kiến quí báu, cảm ơn các bạn học sinh - nhữngcon người đã trực tiếp làm nên cuốn sách này.Do thời gian hạn hẹp, một số chuyên đề tuy đã có nhưng chưa kịp chỉnh sửa và đưa vào tài liệu.Bạn đọc có thể tham khảo thêm trong phần tra cứu. Rất mong nhận được những lời nhận xét và gópý của các bạn để hoàn thiện cuốn sách này. Tokyo, 28 tháng 4 năm 2003 Lê Minh Hoàng i MỤC LỤCPHẦN 1. BÀI TOÁN LIỆT KÊ ................................................................................. 1 §1. NHẮC LẠI MỘT SỐ KIẾN THỨC ĐẠI SỐ TỔ HỢP......................................................................2 1.1. CHỈNH HỢP LẶP..............................................................................................................................................2 1.2. CHỈNH HỢP KHÔNG LẶP...............................................................................................................................2 1.3. HOÁN VỊ ...........................................................................................................................................................2 1.4. TỔ HỢP..............................................................................................................................................................3 §2. PHƯƠNG PHÁP SINH (GENERATION) ..........................................................................................4 2.1. SINH CÁC DÃY NHỊ PHÂN ĐỘ DÀI N .........................................................................................................5 2.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ ............................................................................................................6 2.3. LIỆT KÊ CÁC HOÁN VỊ ..................................................................................................................................8 §3. THUẬT TOÁN QUAY LUI ................................................................................................................12 3.1. LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI N..................................................................................................12 3.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ ..........................................................................................................13 3.3. LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K ....................................................................................15 3.4. BÀI TOÁN PHÂN TÍCH SỐ ...........................................................................................................................16 3.5. BÀI TOÁN XẾP HẬU .....................................................................................................................................18 §4. KỸ THUẬT NHÁNH CẬN.................................................................................................................24 4.1. BÀI TOÁN TỐI ƯU.........................................................................................................................................24 4.2. SỰ BÙNG NỔ TỔ HỢP ..................................................................................................................................24 4.3. MÔ HÌNH KỸ THUẬT NHÁNH CẬN...........................................................................................................24 4.4. BÀI TOÁN NGƯỜI DU LỊCH ........................................................................................................................25 4.5. DÃY ABC ....................................................................... ...