Tải về
pass giải nén: chuyentin.pro
Cuốn sách Giải thuật và lập trình của thầy Lê Minh Hoàng tổng hợp gần như đầy đủ các thuật toán, giải thuật và các kiến thức từ cơ bản tới chuyên sâu dành cho mọi đối tượng lập trình viên. Chi tiết nội dung các chương của cuốn sách, các bạn xem ở ngay dưới đây. Để tải ebook, các bạn kéo xuống cuối bài viết nhé.
Có thể bạn cũng quan tâm: Lộ trình ôn thi Olympic tin học & ACM-ICPC
Nội dung cuốn Giải thuật và Lập trình
PHẦN 1 – BÀI TOÁN LIỆT KÊ
1-Nhắc lại một số kiến thức đại số tổ hợp
2-Phương pháp sinh
3-Thuật toán quay lui
4-Kỹ thuật nhánh cận
PHẦN 2 – CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
1-Các bước cơ bản khi tiến hành giải các bài toán tin học
2-Phân tích thời gian thực hiện giải thuật
3-Đệ quy và giải thuật đệ quy
4-Cấu trúc dữ liệu biểu diễn danh sách
5-Ngăn xếp và hàng đợi
6-Cây
7-Ký pháp tiền tố, trung tố và hậu tố
8-Sắp xếp
9-Tìm kiếm
PHẦN 3 – QUY HOẠCH ĐỘNG
1-Công thức truy hồi
2-Phương pháp quy hoạch động
3-Một số bài toán quy hoạch động
PHẦN 4 – CÁC THUẬN TOÁN TRÊN ĐỒ THỊ
1-Các khái niệm cơ bản
2-Biểu diễn đồ thị trên máy tính
3-Các thuật toán tìm kiếm trên đồ thị
4-Tính liên thông của đồ thị
5-Vài ứng dụng của các thuật toán tìm kiếm trên đồ thị
6-Chu trình Euler, đường euler, đồ thị euler
7-Chu trình Hamilton, đường đi Hamilton, Đồ thị Hamilton
8-Bài toán đường đi ngắn nhất
9-Bài toán cây khung nhỏ nhất
10-Bài toán luồng cực đại trên mạng
11-Bài toán tìm bộ ghép cực đại trên đồ thị hai phía
12-Bài toán tìm bộ ghép cực đại với trọng số cực tiểu trên đồ thị hai phía – thuật toán Hungari
13-Bài toán tìm bộ ghép cực đại trên đồ thị
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 CẬN.......24 4.4. BÀI TOÁN NGƯỜI DU L ỊCH ........25 4.5. DÃY ABC ..........28 PHẦN 2. CẤU TRÚC DỮ LIỆU VÀ GIẢI Thuật ... 33 §1. CÁC BƯỚC CƠ BẢN KHI TIẾN HÀNH GIẢI CÁC BÀI TOÁN TIN HỌC..34 1.1. XÁC ĐỊNH BÀI TOÁN.........34 1.2. TÌM CẤU TRÚC DỮ LIỆU BIỂU DIỄN BÀI TOÁN ......34 1.3. TÌM Thuật TOÁN .........35 1.4. L ẬP TRÌNH ..........37 1.5. KI ỂM TH Ử ..........37 1.6. TỐI ƯU CH ƯƠNG TRÌNH ........38 §2. PHÂN TÍCH TH ỜI GIAN THỰC HIỆN GIẢI Thuật.....40 2.1. ĐỘ PHỨC TẠP TÍNH TOÁN CỦA GIẢI Thuật ......40 2.2. XÁC ĐỊNH ĐỘ PHỨC TẠP TÍNH TOÁN CỦA GIẢI Thuật.....40 2.3. ĐỘ PHỨC TẠP TÍNH TOÁN V ỚI TÌNH TR ẠNG DỮ LIỆU VÀO....43 2.4. CHI PHÍ THỰC HIỆN Thuật TOÁN.......43 §3. ĐỆ QUY VÀ GIẢI Thuật ĐỆ QUY...... 45 3.1. KHÁI NI ỆM V Ề ĐỆ QUY........ 45 3.2. GIẢI Thuật ĐỆ QUY ......... 45 3.3. VÍ D Ụ V Ề GIẢI Thuật ĐỆ QUY ....... 46 3.4. HI ỆU L ỰC CỦA ĐỆ QUY ........ 50 §4. CẤU TRÚC DỮ LIỆU BIỂU DIỄN DANH SÁCH..... 52 4.1. KHÁI NI ỆM DANH SÁCH ........ 52 4.2. BIỂU DIỄN DANH SÁCH TRONG MÁY TÍNH ...... 52 §5. NG ĂN XẾP VÀ HÀNG ĐỢI....... 58 5.1. NG ĂN XẾP (STACK)......... 58 5.2. HÀNG ĐỢI (QUEUE)......... 60 §6. CÂY (TREE)......... 64 6.1. ĐỊNH NGH ĨA .......... 64 6.2. CÂY NHỊ PHÂN (BINARY TREE) ....... 65 6.3. BIỂU DIỄN CÂY NHỊ PHÂN ........ 67 6.4. PHÉP DUY ỆT CÂY NHỊ PHÂN........ 69 6.5. CÂY K_PHÂN ......... 70 6.6. CÂY TỔNG QUÁT......... 71 §7. KÝ PHÁP TI ỀN T Ố, TRUNG T Ố VÀ HẬU T Ố..... 74 7.1. BI ỂU THỨC D ƯỚI D ẠNG CÂY NHỊ PHÂN ...... 74 7.2. CÁC KÝ PHÁP CHO CÙNG M ỘT BI ỂU THỨC...... 74 7.3. CÁCH TÍNH GIÁ TR Ị BI ỂU THỨC....... 75 7.4. CHUY ỂN T Ừ D ẠNG TRUNG T Ố SANG D ẠNG HẬU T Ố..... 78 7.5. XÂY D ỰNG CÂY NHỊ PHÂN BIỂU DIỄN BI ỂU THỨC..... 80 §8. SẮP XẾP (SORTING) ........ 82 8.1. BÀI TOÁN SẮP XẾP......... 82 8.2. Thuật TOÁN SẮP XẾP KIỂU CH ỌN (SELECTIONSORT)..... 84 8.3. Thuật TOÁN SẮP XẾP N ỔI B ỌT (BUBBLESORT)...... 85 8.4. Thuật TOÁN SẮP XẾP KIỂU CHÈN....... 85 8.5. SHELLSORT.......... 87 8.6. Thuật TOÁN SẮP XẾP KIỂU PHÂN ĐO ẠN (QUICKSORT)..... 88 8.7. Thuật TOÁN SẮP XẾP KIỂU VUN ĐỐNG (HEAPSORT) ..... 92 8.8. SẮP XẾP B ẰNG PHÉP ĐẾM PHÂN PH ỐI (DISTRIBUTION COUNTING) ... 95 8.9. TÍNH ỔN ĐỊNH CỦA Thuật TOÁN SẮP XẾP (STABILITY) ..... 96 8.10. Thuật TOÁN SẮP XẾP B ẰNG C Ơ số (RADIXSORT)..... 97 8.11. Thuật TOÁN SẮP XẾP TR ỘN (MERGESORT)...... 102 8.12. CÀI ĐẶT .......... 105 8.13. ĐÁNH GIÁ, NH ẬN XÉT........ 112 §9. TÌM kiếm (SEARCHING)....... 116 iii 9.1. BÀI TOÁN TÌM kiếm.........116 9.2. TÌM kiếm TU ẦN T Ự (SEQUENTIAL SEARCH) ......116 9.3. TÌM kiếm NHỊ PHÂN (BINARY SEARCH) ......116 9.4. CÂY NHỊ PHÂN TÌM kiếm (BINARY SEARCH TREE - BST) ....117 9.5. PHÉP B ĂM (HASH).........122 9.6. KHOÁ số V ỚI BÀI TOÁN TÌM kiếm .......122 9.7. CÂY TÌM kiếm số HỌC (DIGITAL SEARCH TREE - DST).....123 9.8. CÂY TÌM kiếm C Ơ số (RADIX SEARCH TREE - RST) .....126 9.9. NH ỮNG NH ẬN XÉT CU ỐI CÙNG .......131 PHẦN 3. QUY HO ẠCH ĐỘNG ..... 133 §1. CÔNG THỨC TRUY HỒI.......134 1.1. VÍ D Ụ..........134 1.2. CẢI TIẾN THỨ nhất.........135 1.3. CẢI TIẾN THỨ HAI.........137 1.4. CÀI ĐẶT ĐỆ QUY .........137 §2. PH ƯƠNG PHÁP QUY HO ẠCH ĐỘNG ......139 2.1. BÀI TOÁN QUY HO ẠCH ........139 2.2. PH ƯƠNG PHÁP QUY HO ẠCH ĐỘNG.......139 §3. M ỘT số BÀI TOÁN QUY HO ẠCH ĐỘNG ......143 3.1. DÃY CON ĐƠN ĐI ỆU TĂNG DÀI nhất.......143 3.2. BÀI TOÁN CÁI TÚI.........148 3.3. BI ẾN ĐỔI XÂU.........150 3.4. DÃY CON CÓ TỔNG CHIA hết CHO K.......154 3.5. PHÉP NHÂN TỔ HỢP DÃY MA TR ẬN.......159 3.6. BÀI TẬP LUY ỆN TẬP.........163 PHẦN 4. CÁC Thuật TOÁN TRÊN ĐỒ THỊ .... 169 §1. CÁC KHÁI NI ỆM CƠ BẢN .......170 1.1. ĐỊNH NGH ĨA ĐỒ THỊ (GRAPH)........170 1.2. CÁC KHÁI NI ỆM.........171 §2. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH......173 2.1. MA TR ẬN LI ỀN K Ề (MA TR ẬN K Ề) .......173 2.2. DANH SÁCH CẠNH.........174 2.3. DANH SÁCH K Ề.........175 2.4. NH ẬN XÉT..........176 §3. CÁC Thuật TOÁN TÌM kiếm TRÊN ĐỒ THỊ.....177 3.1. BÀI TOÁN ..........177 3.2. Thuật TOÁN TÌM kiếm THEO chiều SÂU (DEPTH FIRST SEARCH)...178 3.3. Thuật TOÁN TÌM kiếm THEO chiều rộng (BREADTH FIRST SEARCH) ...184 3.4. ĐỘ PHỨC TẠP TÍNH TOÁN CỦA BFS VÀ DFS ...... 189 §4. TÍNH LIÊN THÔNG CỦA ĐỒ THỊ ...... 190 4.1. ĐỊNH NGH ĨA ......... 190 4.2. TÍNH LIÊN THÔNG TRONG ĐỒ THỊ VÔ HƯỚNG...... 191 4.3. ĐỒ THỊ ĐẦY ĐỦ VÀ Thuật TOÁN WARSHALL ...... 191 4.4. CÁC THÀNH PHẦN LIÊN THÔNG M ẠNH ...... 195 §5. VÀI ỨNG D ỤNG CỦA CÁC Thuật TOÁN TÌM kiếm TRÊN ĐỒ THỊ .. 205 5.1. XÂY D ỰNG CÂY KHUNG CỦA ĐỒ THỊ ....... 205 5.2. TẬP CÁC CHU TRÌNH CƠ BẢN CỦA ĐỒ THỊ ...... 208 5.3. ĐỊNH chiều ĐỒ THỊ VÀ BÀI TOÁN LIỆT KÊ C ẦU..... 208 5.4. LIỆT KÊ KH ỚP ......... 214 §6. CHU TRÌNH EULER, ĐƯỜNG ĐI EULER, ĐỒ THỊ EULER.... 218 6.1. BÀI TOÁN 7 CÁI C ẦU ........ 218 6.2. ĐỊNH NGH ĨA ......... 218 6.3. ĐỊNH LÝ.......... 218 6.4. Thuật TOÁN FLEURY TÌM CHU TRÌNH EULER...... 219 6.5. CÀI ĐẶT .......... 220 6.6. Thuật TOÁN T ỐT HƠN ........ 222 §7. CHU TRÌNH HAMILTON, ĐƯ ỜNG ĐI HAMILTON, ĐỒ THỊ HAMILTON .. 225 7.1. ĐỊNH NGH ĨA ......... 225 7.2. ĐỊNH LÝ.......... 225 7.3. CÀI ĐẶT .......... 226 §8. BÀI TOÁN ĐƯ ỜNG ĐI NG ẮN nhất ...... 230 8.1. ĐỒ THỊ CÓ TR ỌNG SỐ........ 230 8.2. BÀI TOÁN ĐƯ ỜNG ĐI NG ẮN nhất ....... 230 8.3. TR ƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH ÂM - Thuật TOÁN FORD BELLMAN. 232 8.4. TR ƯỜNG HỢP TR ỌNG số TRÊN CÁC CUNG KHÔNG ÂM - Thuật TOÁN DIJKSTRA.. 234 8.5. Thuật TOÁN DIJKSTRA VÀ CẤU TRÚC HEAP...... 237 8.6. TR ƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH - THỨ T Ự TÔ PÔ .... 240 8.7. ĐƯ ỜNG ĐI NG ẮN nhất GI ỮA M ỌI C ẶP ĐỈNH - Thuật TOÁN FLOYD... 242 8.8. NH ẬN XÉT.......... 245 §9. BÀI TOÁN CÂY KHUNG NH Ỏ nhất...... 247 9.1. BÀI TOÁN CÂY KHUNG NH Ỏ nhất....... 247 9.2. Thuật TOÁN KRUSKAL (JOSEPH KRUSKAL - 1956) ..... 247 9.3. Thuật TOÁN PRIM (ROBERT PRIM - 1957)...... 252 §10. BÀI TOÁN LU ỒNG C ỰC ĐẠI TRÊN M ẠNG..... 256 10.1. BÀI TOÁN .......... 256 10.2. LÁT C ẮT, ĐƯ ỜNG tăng LU ỒNG, ĐỊNH LÝ FORD - FULKERSON.... 256 10.3. CÀI ĐẶT .......... 258 10.4. Thuật TOÁN FORD - FULKERSON (L.R.FORD & D.R.FULKERSON - 1962)...262 §11. BÀI TOÁN TÌM B Ộ GHÉP C ỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA...266 11.1. ĐỒ THỊ HAI PHÍA (BIPARTITE GRAPH)......266 11.2. BÀI TOÁN GHÉP ĐÔI KHÔNG TR ỌNG VÀ CÁC KHÁI NI ỆM....266 11.3. Thuật TOÁN ĐƯ ỜNG M Ở........267 11.4. CÀI ĐẶT..........268 §12. BÀI TOÁN TÌM B Ộ GHÉP C ỰC ĐẠI V ỚI TR ỌNG số C ỰC TI ỂU TRÊN ĐỒ THỊ HAI PHÍA - Thuật TOÁN HUNGARI .......273 12.1. BÀI TOÁN PHÂN CÔNG ........273 12.2. PHÂN TÍCH..........273 12.3. Thuật TOÁN .........274 12.4. CÀI ĐẶT..........278 12.5. BÀI TOÁN TÌM B Ộ GHÉP C ỰC ĐẠI V ỚI TR ỌNG số C ỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA .284 12.6. NÂNG C ẤP..........284 §13. BÀI TOÁN TÌM B Ộ GHÉP C ỰC ĐẠI TRÊN ĐỒ THỊ ....290 13.1. CÁC KHÁI NI ỆM.........290 13.2. Thuật TOÁN EDMONDS (1965) .......291 13.3. PH ƯƠNG PHÁP LAWLER (1973).......293 13.4. CÀI ĐẶT..........295 13.5. ĐỘ PHỨC TẠP TÍNH TOÁN ........299 TÀI LIỆU ĐỌC THÊM...... 301 HÌNH V Ẽ Hình 1: Cây tìm kiếm quay lui trong bài toán LIỆT kê dãy NHỊ phân...... 13 Hình 2: XẾP 8 quân HẬU trên bàn c ờ 8x8........ 19 Hình 3: Đư ờng chéo ĐB-TN mang ch ỉ số 10 và đư ờng chéo ĐN-TB mang ch ỉ số 0 .... 19 Hình 4: L ưu đồ thuật GIẢI (Flowchart)........ 36 Hình 5: Tháp Hà N ội.......... 49 Hình 6: CẤU trúc nút CỦA danh sách n ối đơn........ 53 Hình 7: Danh sách n ối đơn......... 53 Hình 8: CẤU trúc nút CỦA danh sách n ối kép........ 55 Hình 9: Danh sách n ối kép ......... 55 Hình 10: Danh sách n ối vòng m ột Hướng........ 55 Hình 11: Danh sách n ối vòng hai Hướng........ 56 Hình 12: Dùng danh sách vòng mô t ả Queue........ 61 Hình 13: Di chuy ển toa tàu......... 63 Hình 14: Di chuy ển toa tàu (2)......... 63 Hình 15: Cây ........... 64 Hình 16: M ức CỦA các nút trên cây......... 65 Hình 17: Cây BIỂU DIỄN bi ểu THỨc......... 65 Hình 18: Các d ạng cây nhị phân suy bi ến ........ 66 Hình 19: Cây NHỊ phân hoàn CHỈNH và cây NHỊ phân đầy đủ ...... 66 Hình 20: Đánh số các nút CỦA cây NHỊ phân đầy đủ để BIỂU DIỄN b ằng m ảng..... 67 Hình 21: Nh ược đi ểm CỦA ph ương pháp BIỂU DIỄN cây b ằng m ảng...... 68 Hình 22: CẤU trúc nút CỦA cây NHỊ phân ........68 Hình 23: BIỂU DIỄN cây b ằng CẤU trúc liên k ết........ 69 Hình 24: Đánh số các nút CỦA cây 3_phân để BIỂU DIỄN b ằng m ảng...... 71 Hình 25: BIỂU DIỄN cây TỔng quát b ằng m ảng ........ 72 Hình 26: CẤU trúc nút CỦA cây TỔng quát ........ 73 Hình 27: Bi ểu THỨc d ưới d ạng cây NHỊ phân........ 74 Hình 28: Vòng LẶP trong CỦA QuickSort........ 89 Hình 29: Tr ạng thái trước khi g ọi đệ quy........ 90 Hình 30: Heap ........... 92 Hình 31: Vun đống.......... 93 Hình 32: Đảo giá tr ị k 1 cho k n và xét PHẦN còn l ại....... 93 Hình 33: Vun PHẦN còn l ại thành đống r ồi l ại đảo tr ị k 1 cho k n-1 ...... 94 Hình 34: Đánh số các bit .......... 97 Hình 35: Thuật toán SẮP XẾP tr ộn ......... 102 Hình 36: Cài đặt các Thuật toán SẮP XẾP v ới DỮ LIỆU l ớn....... 114 Hình 37: Cây NHỊ phân tìm kiếm ......... 118 Hình 38: Xóa nút lá ở cây BST ......... 119 Hình 39. Xóa nút ch ỉ có m ột nhánh con trên cây BST....... 120 Hình 40: Xóa nút có c ả hai nhánh con trên cây BST thay b ằng nút c ực ph ải CỦA cây con trái ...120 Hình 41: Xóa nút có c ả hai nhánh con trên cây BST thay b ằng nút c ực trái CỦA cây con ph ải ...120 Hình 42: Đánh số các bit..........123 Hình 43: Cây tìm kiếm số Học.........124 Hình 44: Cây tìm kiếm c ơ số .........126 Hình 45: V ới độ dài dãy bit z = 3, cây tìm kiếm c ơ số g ồm các khoá 2, 4, 5 và sau khi thêm giá tr ị 7 ..127 Hình 46: RST ch ứa các khoá 2, 4, 5, 7 và RST sau khi lo ại b ỏ giá tr ị 7 .....128 Hình 47: Cây tìm kiếm c ơ số a) và Trie tìm kiếm c ơ số b) ......130 Hình 48: Hàm đệ quy tính số Fibonacci........141 Hình 49: Tính toán và truy v ết .........144 Hình 50: Truy v ết..........153 Hình 51: Ví d ụ v ề mô hình đồ THỊ .........170 Hình 52: Phân lo ại đồ THỊ .........171 Hình 53 ...........174 Hình 54 ...........175 Hình 55: Đồ THỊ và đường đi .........177 Hình 56: Cây DFS..........180 Hình 57: Cây BFS..........184 Hình 58: Thuật toán loang .........187 Hình 59: Đồ THỊ G và các thành PHẦN liên thông G1, G2, G3 CỦA nó .....190 Hình 60: Kh ớp và c ầu ..........190 Hình 61: Liên thông m ạnh và liên thông y ếu........191 Hình 62: Đồ THỊ đầy đủ..........192 Hình 63: Đơn đồ THỊ vô Hướng và bao đóng CỦA nó .......192 Hình 64: Ba d ạng cung ngoài cây DFS........196 Hình 65: Thuật toán Tarjan "b ẻ" cây DFS ........198 Hình 66: Đánh số l ại, đảo chiều các cung và duy ệt BFS v ới cách ch ọn các đỉnh xu ất phát ng ược l ại v ới THỨ t ự duy ệt xong (THỨ t ự 11, 10… 3, 2, 1)........204 Hình 67: Đồ THỊ G và m ột số ví d ụ cây khung T1, T2, T3 CỦA nó......207 Hình 68: Cây khung DFS (a) và cây khung BFS (b) (M ũi tên ch ỉ chiều đi th ăm các đỉnh)...207 Hình 69: Phép định chiều DFS.........210 Hình 70: Phép đánh số và ghi nh ận cung ng ược lên cao nhất......212 Hình 71 Duy ệt DFS, xác định cây DFS và các cung ng ược......215 Hình 72: Mô hình đồ THỊ CỦA bài toán b ảy cái c ầu.......218 Hình 73 ...........219 Hình 74 ...........219 Hình 75 ...........225 Hình 76: Phép đánh l ại ch ỉ số theo THỨ t ự tôpô .......240 Hình 77: Hai cây g ốc r và cây m ới khi HỢP nhất chúng ......248 Hình 78: M ạng v ới các kh ả n ăng thông qua (1 phát, 6 thu) và m ột lu ồng CỦA nó v ới giá tr ị 7 ...256 Hình 79: M ạng G, lu ồng trên các cung (1 phát, 6 thu) và đồ THỊ tăng lu ồng t ương ứng....257 Hình 80: Lu ồng trên m ạng G tr ước và sau khi tăng.......258 Hình 81: Đồ THỊ hai phía.......... 266 Hình 82: Đồ THỊ hai phía và b ộ ghép M........ 267 Hình 83: Mô hình lu ồng CỦA bài toán tìm b ộ ghép c ực đại trên đồ THỊ hai phía .... 271 Hình 84: Phép xoay tr ọng số CẠNH......... 274 Hình 85: Thuật toán Hungari......... 277 Hình 86: Cây pha "m ọc" l ớn Hơn sau m ỗi l ần xoay tr ọng số CẠNH và tìm đường.... 285 Hình 87: Đồ THỊ G và m ột b ộ ghép M........ 290 Hình 88: Phép CHẬP Blossom ......... 292 Hình 89: N ở Blossom để dò đư ờng xuyên qua Blossom...... 292 CH ƯƠNG TRÌNH P_1_02_1.PAS * Thuật toán sinh LIỆT kê các dãy NHỊ phân độ dài n......6 P_1_02_2.PAS * Thuật toán sinh LIỆT kê các TẬP con k PHẦN TỬ......8 P_1_02_3.PAS * Thuật toán sinh LIỆT kê hoán v ị.......9 P_1_03_1.PAS * Thuật toán quay lui LIỆT kê các dãy NHỊ phân độ dài n.....12 P_1_03_2.PAS * Thuật toán quay lui LIỆT kê các TẬP con k PHẦN TỬ......14 P_1_03_3.PAS * Thuật toán quay lui LIỆT kê các CHỈNH HỢP không LẶP CHẬP k.....15 P_1_03_4.PAS * Thuật toán quay lui LIỆT kê các cách phân tích SỐ......17 P_1_03_5.PAS * Thuật toán quay lui GIẢI bài toán XẾP HẬU ......21 P_1_04_1.PAS * K ỹ thuật nhánh CẬN dùng cho bài toán NGƯỜI du l ịch.....26 P_1_04_2.PAS * Dãy ABC .........28 P_2_07_1.PAS * Tính giá tr ị bi ểu THỨc RPN........76 P_2_07_2.PAS * Chuy ển bi ểu THỨc trung t ố sang d ạng RPN......79 P_2_08_1.PAS * Các Thuật toán s ăp XẾP ........105 P_3_01_1.PAS * Đếm số cách phân tích số n .......135 P_3_01_2.PAS * Đếm số cách phân tích số n .......136 P_3_01_3.PAS * Đếm số cách phân tích số n .......136 P_3_01_4.PAS * Đếm số cách phân tích số n .......137 P_3_01_5.PAS * Đếm số cách phân tích số n dùng đệ quy......137 P_3_01_6.PAS * Đếm số cách phân tích số n dùng đệ quy......138 P_3_03_1.PAS * Tìm dãy con đơn đi ệu tăng dài nhất.......144 P_3_03_2.PAS * CẢI TIẾN Thuật toán tìm dãy con đơn đi ệu tăng dài nhất.....146 P_3_03_3.PAS * Bài toán cái túi.........149 P_3_03_4.PAS * Bi ến đổi xâu.........153 P_3_03_5.PAS * Dãy con có TỔng chia hết cho k.......156 P_3_03_6.PAS * Dãy con có TỔng chia hết cho k.......158 P_3_03_7.PAS * Nhân TỐI ưu dãy ma tr ận ........162 P_4_03_1.PAS * Thuật toán tìm kiếm theo chiều sâu .......178 P_4_03_2.PAS * Thuật toán tìm kiếm theo chiều sâu không đệ quy .....181 P_4_03_3.PAS * Thuật toán tìm kiếm theo chiều rộng dùng hàng đợi .....185 P_4_03_4.PAS * Thuật toán tìm kiếm theo chiều rộng dùng ph ương pháp loang ....187 P_4_04_1.PAS * Thuật toán Warshall LIỆT kê các thành PHẦN liên thông .....194 P_4_04_2.PAS * Thuật toán Tarjan LIỆT kê các thành PHẦN liên thông m ạnh .....201 P_4_05_1.PAS * Phép định chiều DFS và LIỆT kê c ầu .......213 P_4_05_2.PAS * LIỆT kê các kh ớp CỦA đồ THỊ........216 P_4_06_1.PAS * Thuật toán Fleury tìm chu trình Euler.......220 P_4_06_2.PAS * Thuật toán hi ệu qu ả tìm chu trình Euler ......223 P_4_07_1.PAS * Thuật toán quay lui LIỆT kê chu trình Hamilton ......226 P_4_08_1.PAS * Thuật toán Ford-Bellman........233 P_4_08_2.PAS * Thuật toán Dijkstra ........235 P_4_08_3.PAS * Thuật toán Dijkstra và CẤU trúc Heap .......237 P_4_08_4.PAS * Đư ờng đi ng ắn nhất trên đồ THỊ không có chu trình ..... 241 P_4_08_5.PAS * Thuật toán Floyd........ 243 P_4_09_1.PAS * Thuật toán Kruskal........ 249 P_4_09_2.PAS * Thuật toán Prim......... 252 P_4_10_1.PAS * Thuật toán tìm lu ồng c ực đại trên m ạng ...... 259 P_4_10_2.PAS * Thuật toán Ford-Fulkerson........ 262 P_4_11_1.PAS * Thuật toán đư ờng m ở tìm b ộ ghép c ực đại ...... 269 P_4_12_1.PAS * Thuật toán Hungari ........ 280 P_4_12_2.PAS * Cài đặt ph ương pháp Kuhn-Munkres O(n3) ...... 286 P_4_13_1.PAS * Ph ương pháp Lawler áp d ụng cho Thuật toán Edmonds..... 296
Không có nhận xét nào:
Đăng nhận xét
Lưu ý: Chỉ thành viên của blog này mới được đăng nhận xét.