A. Python THCS – Tư duy & thuật toán
Tư duy giải thuật
Bài 1: Làm quen với tư duy giải quyết vấn đề- Phân tích bài toán & lập trình hướng cấu trúc
- Phân rã bài toán phức tạp thành các hàm con (modular decomposition)
- Mô hình hóa với sơ đồ khối / flowchart
- Biến đề bài tự nhiên thành code có cấu trúc rõ ràng
Bài 2: Tính tổng, đếm, tìm giá trị đặc trưng
- Đếm – Tổng – Điều kiện lồng sâu
- Xử lý dữ liệu đầu vào lớn (10^5 phần tử)
- Kỹ thuật prefix sum, bitmask điều kiện
- Đếm cặp số thỏa mãn điều kiện ràng buộc (như a[i] + a[j] ≡ 0 mod k)
Bài 3: Duyệt và xử lý mảng – tư duy cấu trúc dữ liệu cơ bản
- Dãy – Mảng – Đếm cấu trúc đặc biệt
- Tìm dãy con tăng dài nhất (LIS)
- Tính dãy con có tổng lớn nhất (Kadane’s Algorithm)
- Đếm dãy con thoả mãn điều kiện
Bài 4: Làm việc với chuỗi ký tự – xử lý dữ liệu văn bản
- Chuỗi – Kỹ thuật tiền xử lý
- Tách câu, đếm từ vựng không lặp
- Xây dựng hàm normalize() lọc bỏ dấu tiếng Việt
- Phát hiện mẫu chuỗi xuất hiện nhiều lần nhất (Sliding window + Dict)
- Phát hiện chuỗi đối xứng (palindrome);
- Làm sạch chuỗi: xóa dấu câu, chuẩn hóa chữ hoa/thường;
- Tìm từ không lặp;
- Phân tích chuỗi để đếm số từ, số số, chuỗi con trùng nhau.
Bài 5: Vòng lặp lồng nhau – xử lý bảng và hình học
- Học sinh học cách dùng vòng lặp lồng nhau để in bảng cửu chương, hình chữ nhật, tam giác bằng ký tự *.
- Nâng cao hơn, học sinh sẽ:
-
Quét một bảng
n x mđể tìm phần tử theo dòng/cột; -
Tính tổng đường chéo chính/phụ;
-
Kiểm tra bảng đối xứng;
-
Tính số hình vuông đơn sắc;
-
Áp dụng cho các bài toán kiểu lưới (như mê cung, bản đồ).
Bài 6: Dãy con, chuỗi con và cấu trúc đặc biệt
- Sau khi nắm vững mảng và chuỗi, học sinh được dẫn dắt vào tư duy về dãy con – chuỗi con – dãy tăng, dãy giảm, dãy có tổng đặc biệt.
- Ở mức độ học sinh giỏi, các kỹ thuật như:
-
Tìm dãy con tăng dài nhất (LIS);
-
Tính tổng dãy con lớn nhất (Kadane’s Algorithm);
-
Sinh tổ hợp các dãy con có ràng buộc;
được giới thiệu một cách trực quan và có bài tập thực hành đi kèm.
Bài 7: Tư duy tối ưu hóa – tiền xử lý – tư duy hàm hóa
- Ở cấp độ nâng cao cuối của phần này, học sinh không chỉ biết viết chương trình chạy đúng, mà còn biết cách:
-
Viết chương trình chạy nhanh (tối ưu độ phức tạp);
-
Tiền xử lý dữ liệu với mảng cộng dồn (
prefix sum) hoặcdictđể tăng tốc; -
Chia bài toán thành nhiều hàm con để tái sử dụng;
-
Viết chương trình có thể kiểm thử – mở rộng dễ dàng.
Thuật toán kinh điển
Bài 1: Kiểm tra tính chất số học – rèn tư duy logicHọc sinh được làm quen với các bài toán kinh điển như:
-
Kiểm tra số nguyên tố, số hoàn hảo, số chính phương;
-
Phân tích cấu trúc số bằng cách tách chữ số, dùng vòng lặp
for.
Khi nâng cao, các dạng số đặc biệt được mở rộng:
-
Số thuận nghịch (Palindrome số);
-
Số “đẹp”: có chữ số tăng dần, không lặp chữ số;
-
Kiểm tra số có đúng
kước; -
Ứng dụng tư duy logic kết hợp xử lý chuỗi + số.
Bài 2: Ước chung, bội chung – phân tích thừa số
Ở mức nền tảng, học sinh học:
-
Cách tìm ƯCLN (GCD) bằng thuật toán Euclid;
-
Cách tính BCNN (LCM) từ GCD;
-
Phân tích số nguyên dương thành tích các thừa số nguyên tố.
Khi nâng cao:
-
Áp dụng sàng nguyên tố để phân tích hàng loạt số;
-
Tìm số nhỏ nhất chia hết cho 1 đến
k; -
Giải bài toán tổ hợp số qua phân tích thừa số: kiểm tra số là tích của 3 số nguyên tố khác nhau, hoặc số có đúng 3 ước.
Bài 3: Thuật toán sắp xếp – từ lý thuyết đến ứng dụng
Cơ bản: học sinh được hướng dẫn các thuật toán:
-
Bubble sort (nổi bọt), Selection sort (chọn), Insertion sort (chèn);
-
Sắp xếp mảng tăng dần, giảm dần.
Khi lên mức nâng cao:
-
Tự viết các thuật toán mà không dùng
sort(); -
Sắp xếp theo tiêu chí đặc biệt: tổng chữ số, số chữ số, số lẻ/chẵn ưu tiên;
-
Sắp xếp mảng 2 chiều (danh sách tên – điểm), sắp xếp theo nhiều khóa;
-
So sánh hiệu suất giữa các thuật toán bằng cách đếm số phép so sánh.
Bài 4: Tìm kiếm nâng cao – từ tuyến tính đến nhị phân
Cơ bản:
-
Tìm kiếm tuyến tính: tìm phần tử đầu tiên bằng x;
-
Tìm kiếm nhị phân: tìm phần tử trong mảng đã sắp.
Nâng cao:
-
Tìm kiếm gần đúng: tìm phần tử gần nhất với
x; -
Tìm vị trí xuất hiện cuối cùng, hoặc đếm số lần xuất hiện;
-
Tư duy nhị phân trên đáp án: tìm độ dài dãy con thỏa điều kiện lớn nhất mà vẫn đúng bài toán (rất quan trọng trong lập trình thi đấu);
-
Tìm giá trị nhỏ nhất/lớn nhất thỏa điều kiện bằng binary search + check điều kiện.
Bài 5: Đệ quy – sinh – tổ hợp – quay lui đơn giản
Học sinh bắt đầu từ:
-
Giai thừa
n!, dãy Fibonacci; -
Tính tổng các chữ số bằng đệ quy.
Nâng cao hơn:
-
Sinh dãy nhị phân độ dài
n; -
Sinh hoán vị, tổ hợp, dãy có tổng đúng
k; -
Quay lui để tìm tất cả các cách chọn
kphần tử từn; -
Bài toán mê cung, sudoku mini – áp dụng quay lui;
-
Cắt nhánh bằng điều kiện dừng sớm (nhánh cận – branch and bound);
-
So sánh hiệu suất giữa đệ quy – vòng lặp – đệ quy có nhớ (memoization).
B. BÀI TẬP LUYỆN HSG THCS, TIN HỌC TRẺ
LÝ THUYẾT THAM KHẢO
Bài 1: Môi trường Python
Bài 2: Chương trình Python đơn giản
Chỉ thị gán và biểu thức số học
Các phép tính số học
Ví dụ về biểu thức số học
Có thể gán giá trị một biểu thức cho nhiều biến, ví dụ:
Gán một danh sách giá trị cho một danh sách biến, số lượng phần tử trong hai danh sách phải bằng nhau, các phần tử trong danh sách ghi cách nhau bởi dấu phẩy (,)
Ví dụ:
Các hàm toán học thường dùng
Ghi chú thích trong chương trình
