Giải Thuật Và Lập Trình (Lê Minh Hoàng)

https://thuviensach.vn

Lời cảm ơn

Tô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ác

thầ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ôi

noi 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ởi

cô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 ơn

tớ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ững

con 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

https://thuviensach.vn

] i ^

MỤC LỤC

PHẦ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 …