Một số vấn đề đáng chú ý trong môn Tin học - Phan Công Minh LTTK Education xin giới thiệu với bạn đọc Một số vấn đề đáng chú ý trong môn Tin học - Phan Công Minh để bạn đọc tham khảo học tập những điều bổ ích mà tài liệu này mang lại nhé! Chúc các em học tập thật tốt và mang lại nhiều kết quả khả quan cho bản thân nhé! ✪ ✪ ✪ ✪ ✪ Link tải tài liệu: LINK TẢI TÀI LIỆU Spoiler: Read me Một số vấn ðề ðáng chú ý trong môn tin học LỜI NÓI ðẦU Với mong muốn tổng hợp những thuật toán hay, các cách giải ðộc ðáo trong quá trình học tập ngôn ngữ lập trình Pascal. Nhóm tác giả Phan Công Minh : Học sinh chuyên Tin A2K35 Hồ Sỹ Việt Anh , Ngô Văn Hoàng , Bùi Minh Trí và Nguyễn Cảnh Toàn – Học sinh chuyên Tin khóa 36 ðã viết cuốn tài liệu “Một số vấn ðề ðáng chú ý trong môn tin học” . Trong phạm vi nội dung của tài liệu này không ðề cập ðến các kiến thức, thuật toán cơ bản mà tập trung vào các kĩ thuật, thuật toán mở rộng cũng như cách kếp hợp, ứng dụng chúng ðể giải quyết các bài toán tin, ðặc biệt là các dạng bài thường gặp trong các kì thi. Hi vọng cuốn tài liệu này có thể giúp ích cho bạn ðọc, nhất là các bạn học sinh trong ðội tuyển trong việc học tập , bồi dưỡng Tin học. Rất mong nhận ðược sự ðóng góp của các bạn ðể cuốn tài liệu hoàn thiện hơn. Thay mặt nhóm tác giả: Phan Công Minh Email: congminh91@yahoo.com MỤC LỤC Lời nói ðầu 2 Duyệt nhánh cận 3 Duyệt ưu tiên 8 Tìm kiếm chuỗi 12 Xử lý bit 15 Quy hoạch ðộng trạng thái 21 Quy hoạch ðộng vị trí cấu hình 26 Quy hoạch ðộng trên cây 35 Sắp xếp topo và ứng dụng 44 Phát hiện chu trình 49 Chu trình Euler 53 Chu trình âm và ứng dụng 56 Tô màu ðồ thị 71 Thuật tóan Ford Bellman kết hợp Queue vòng 81 Thuật toán Dijtra với các ðỉnh ảo 84 Một số ứng dụng thuật toán Dijtra 92 Luồng Mincost 99 Các công thức hình học 104 Một dạng bài Quy hoạch ñộng 107 Trie Tree và ứng dụng 117 Duyệt bằng cách chia ñôi tập hợp 123 Một số bài toán về cây khung 127 Tìm kiếm nhị phân và ứng dụng 133 Xếp lịch công việc 137 Xử lý số nguyên lớn và Hàm Mod 167 Heap và ứng dụng 173 Interval Tree 181 Binary Index Tree 190 Các lỗi trong Pascal Kinh nghiệm thi cử Một số vấn ðề ðáng chú ý trong môn tin học VẤN ðỀ: DUYỆT NHÁNH CẬN. Duyệt nhánh cận là phương pháp phổ biến sử dụng ðể giải quyết một số lượng lớn các bài toán tin, ðặc biệt là các bài toán thực tế. Cấu trúc của chương trình duyệt nhánh cận ðược mô tả sơ lược như sau: Chọn một nghiệm của bài toán làm cận (c) Thực hiện bước duyệt thứ i - Nếu i là bước sau bước cuối cùng thì kiểm tra nghiệm mới tìm ðược và cập nhật cận (c), ghi nhận một nghiệm tốt hơn của bài toán. - Sau bước duyệt thứ i, kiểm tra nghiệm sẽ tìm ðược có khả năng tốt hơn cận (c) hay không - gọi là ðiều kiện nhánh cận. Nếu có gọi thực hiện bước thứ i+1. còn không thì quay lại bước i-1. Hai yếu tố quan trọng của chương trình là cận (c) khởi tạo ban ðầu và ðiều kiện nhánh cận. Việc chọn một cận (c) và ðiều kiện kiểm tra nhánh cận tốt sẽ giúp bước duyệt tránh ði vào những hướng mà chắc chắn không tìm ra ðược kết quả tốt hơn. ðiều có ảnh ảnh hưởng trực tiếp ðến ðộ hiệu quả của chương trình. Dưới ðây ta xét một số cách kiểm tra nhánh cận hay dùng thông qua các bài toán cụ thể. Bài toán: Chu trình Hamilton nhỏ nhất. Cho ðồ thị vô hướng G. Mỗi cạnh ðược gán một trọng số nhất ðịnh (lớn hơn 0), tìm một chu trình ði qua tất cả các ðỉnh, mỗi ðỉnh một lần và có tổng trọng số nhỏ nhất. Gợi ý: Duyệt nhánh cận là phương pháp duy nhất ðể giải quyết bài toán nêu trên. Chu trình ði qua N ðỉnh sẽ bao gồm N cạnh. Giả sử tại bước thứ i, ðã ði qua k cạnh và còn n-k cạnh nữa cần phải ði qua thì ðiều kiện ðể ði tiếp bước thứ i+1 là s(k) + (n-k)*minc < smin Trong ðó: - s(k) là tổng chi phí của k cạnh ðã ði qua - minc là trọng số của cạnh nhỏ nhất trong số các cạnh còn lại chưa ðược ði qua của ðồ thị. - smin là tổng trọng số của một chu trình ðã tìm ðược nhưng chưa tối ưu. Có thể khởi tạo smin ban ðầu là một số vô cùng lớn. Bài toán: Xếp valy. Một va ly có thể chứa tối ða W ðơn vị trọng lượng. Có N loại ðồ vật, số lượng mỗi loại không hạn chế. Loại ðồ vật thứ i có trọng lượng Ai và có giá trị Ci. Hỏi nên chọn những loại ðồ vật nào và số lượng bao nhiêu ðể xếp vào va ly sao cho: - tổng trọng lượng của các vật không vượt quá giới hạn W của valy - tổng giá trị của các vật là lớn nhất Gợi ý: Với mỗi loại ðồ vật i, gọi Ti là giá trị riêng của nó: Ti = Ci / Ai. Sau ðó sắp các loại ðồ vật theo thứ tự giảm dần của Ti. Phương pháp duyệt nhánh cận tại mỗi bước duyệt loại ðồ vật i, ta lấy k ðồ vật loại này, khi ðó ðiều kiện ðể duyệt tiếp loại ðồ vật i+1 (ðiều kiện nhánh cận) là: 3 Một số vấn ðề ðáng chú ý trong môn tin học - k*Ai <= w - s(i) + k*Ci + (w - k*Ai)*Ti+1 > smax Trong ðó: - w là trọng lượng mà valy có thể chứa thêm sau bước duyệt loại ðồ vật i-1 - s(i) là tổng giá trị hiện ðang có của valy sau bước duyệt loại ðồ vật i-1 - smax là tổng giá trị valy của một các xếp ðã tìm ðược nhưng chưa tối ưu. Có thể khởi tạo smax ban ðầu bằng 0. Bài toán: Xâu ABC. Tìm một xâu chỉ gồm các ký tự A,B,C sao cho - Có ðộ dài N cho trước (N<=100) - Hai ðọan con bất kì liên nhau ðều khác nhau (ðoạn con là một dãy các ký tự liên tiếp của xâu). - Có ít ký tự C nhất Gợi ý: Ta có nhận xét trong 4 ký tự liên tiếp luôn có ít nhất một ký tự C. Do ðó ðiều kiện nhánh cận tại bước duyệt ký tự i của xâu là - xâu có i ký tự ðã tạo ðược không có 2 ðoạn con liên tiếp trùng nhau. - s(i) + (n-i) div 4 < smin Trong ðó - s(i) là số ký tự C ðã dùng ðể tạo xâu i ký tự - smin là số ký tự C của một xâu khác thỏa mãn 2 yêu cầu ðầu của ðề bài nhưng chưa tối ưu. Có thể khởi tạo smin ban ðầu là một số ðủ lớn. Luyện tập: Bài toán: Tour du lịch rẻ nhất (TOUR) Một khu thắng cảnh gồm n ðiểm ðánh số từ 1 tới n (n ≤ 100) và m ðường ði hai chiều giữa các cặp ðịa ðiểm ðó, chi phí ði trên các ðường ði là biết trước ( ≤ 10000). Một Tour du lịch là một hành trình xuất phát từ một ðịa ðiểm ði thăm ≥ 2 ðịa ðiểm khác và quay trở về ðiểm xuất phát, ngoại trừ ðịa ðiểm xuất phát, không ðịa ðiểm nào bị thăm tới hai lần. Chi phí của một Tour du lịch là tổng chi phí các quãng ðường ði qua. Yêu cầu: Hãy tìm Tour du lịch có chi phí rẻ nhất. Dữ liệu: TOUR.INP Dòng 1: Ghi hai số nguyên dương n, m m dòng tiếp theo mỗi dòng có dạng x y c. Cho biết có ðường ði trực tiếp nối ðịa ðiểm x với ðịa ðiểm y và chi phí ði quãng ðường ðó là c. Kết quả: TOUR.OUT Dòng 1: Ghi số 1 nếu như tồn tại hành trình theo yêu cầu, ghi số 0 nếu không tồn tại hành trình. Nếu dòng ðầu tiên ghi số 1: Dòng thứ 2 ghi chi phí của tour tìm ðược Dòng thứ 3 ghi số k là số ðịa ðiểm tới thăm 4 Một số vấn ðề ðáng chú ý trong môn tin học Dòng thứ 4 gồm k số, số thứ i là ðịa ðiểm tới thăm thứ i trong tour, quy ước ðịa ðiểm thăm ðầu tiên là ðịa ðiểm xuất phát, ðịa ðiểm thăm thứ k (ðịa ðiểm cuối cùng) là ðịa ðiểm mà từ ðó quay trở lại ðiểm xuất phát ðể kết thúc hành trình. Các số trên một dòng của Input/Output File ðược ghi cách nhau ít nhất một dấu cách. Theo LTTK Education
