Bài học

Bài toán sách giáo khoa và bài toán nâng cao cùng chủ đề

Mục tiêu bài học

Học xong bài này, em đọc một đề Tin học và trả lời được ngay câu hỏi: đây là một bài luyện tập bình thường, hay đây đã là một bài toán đòi hỏi cách nghĩ khác? Đây là bài mở đầu cả lộ trình, nên trước khi bàn thuật toán nào cả, ta cần thống nhất với nhau: nâng cao khác sách giáo khoa ở chỗ nào.

Cần trước khi học bài này (prior-grade review): vòng lặp for, hàm range, phép chia lấy dư %, và cách viết một hàm Python nhận tham số, trả về giá trị bằng return. Nếu những thứ này còn chưa chắc, hãy ôn lại trước — bài học không nhắc lại cú pháp cơ bản.

**Cần trước khi học bài này (prior-grade review):** vòng lặp `for`, hàm `range`, phép chia lấy dư `%`, và cách viết một hàm Python nhận tham số, trả về giá trị bằng `return`. Nếu những thứ này còn chưa chắc, hãy ôn lại trước — bài học không nhắc lại cú pháp cơ bản.

Một bài quen thuộc, để làm mốc so sánh

Ta bắt đầu bằng một bài không ai thấy khó: tính tổng các số từ 1 đến n. Sách giáo khoa lớp 10 dạy đúng như vậy — một vòng lặp, một biến cộng dồn, xong.

Ví dụ

Bài chuẩn — tính tổng từ 1 đến n

1
Cho số nguyên dương $n$ . Tính $S = 1 + 2 + \cdots + n$ .
Cho số nguyên dương $n$. Tính $S = 1 + 2 + \cdots + n$.

def sum_to_n(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

3
Vòng lặp chạy đúng $n$ lần, mỗi lần một phép cộng — độ phức tạp $O(n)$ . Với $n$ cỡ vài triệu, hàm này vẫn chạy gần như tức thời. Không có gì để bàn thêm: đọc đề, viết vòng lặp, xong bài.
Vòng lặp chạy đúng $n$ lần, mỗi lần một phép cộng — độ phức tạp $O(n)$. Với $n$ cỡ vài triệu, hàm này vẫn chạy gần như tức thời. Không có gì để bàn thêm: đọc đề, viết vòng lặp, xong bài.

Đổi một chi tiết nhỏ của đề — ví dụ chỉ tính tổng các số CHẴN từ 1 đến n — code vẫn giữ nguyên cấu trúc, chỉ thêm một điều kiện if i % 2 == 0 trong thân vòng lặp. Bài chuẩn luôn có đặc điểm này: đổi một chi tiết, cấu trúc thuật toán gần như không đổi, độ phức tạp vẫn $O(n)$ .

Đổi một chi tiết nhỏ của đề — ví dụ chỉ tính tổng các số CHẴN từ 1 đến n — code vẫn giữ nguyên cấu trúc, chỉ thêm một điều kiện `if i % 2 == 0` trong thân vòng lặp. Bài chuẩn luôn có đặc điểm này: đổi một chi tiết, cấu trúc thuật toán gần như không đổi, độ phức tạp vẫn $O(n)$.

Cùng chủ đề, nhưng đề bài đã đổi khác

Bây giờ đổi đề, vẫn nằm trong mạch số học quen thuộc: đếm số lượng số nguyên tố trong đoạn từ 1 đến $10^6$ . Nghe thì vẫn là một bài đếm, không có gì lạ. Nhưng thử viết theo phản xạ đầu tiên xem sao.

Bây giờ đổi đề, vẫn nằm trong mạch số học quen thuộc: **đếm số lượng số nguyên tố trong đoạn từ 1 đến $10^6$.** Nghe thì vẫn là một bài đếm, không có gì lạ. Nhưng thử viết theo phản xạ đầu tiên xem sao.

Ví dụ

Bài nâng cao — đếm số nguyên tố đến

10^6

, cách viết theo phản xạBài nâng cao — đếm số nguyên tố đến $10^6$, cách viết theo phản xạ

1
Với mỗi số $x$ từ 2 đến $10^6$ , kiểm tra $x$ có phải số nguyên tố không bằng cách thử chia cho mọi số từ 2 đến $\sqrt{x}$ , rồi đếm.
Với mỗi số $x$ từ 2 đến $10^6$, kiểm tra $x$ có phải số nguyên tố không bằng cách thử chia cho mọi số từ 2 đến $\sqrt{x}$, rồi đếm.

def is_prime(x):
    if x < 2:
        return False
    if x < 4:
        return True
    if x % 2 == 0:
        return False
    i = 3
    while i * i <= x:
        if x % i == 0:
            return False
        i += 2
    return True

def count_primes_trial(limit):
    return sum(1 for x in range(2, limit + 1) if is_prime(x))

3
Trên máy tác giả, count_primes_trial(1_000_000) trả về đúng 78498 — con số này là chính xác, có thể tra cứu độc lập. Vấn đề không phải là đúng hay sai, mà là chạy mất khoảng 0,9 giây chỉ cho MỘT lần gọi. Một đề Tin học thường chấm hàng chục test, mỗi test một giới hạn thời gian khoảng 1 giây — 0,9 giây cho một test đã là quá sát, chưa kể nhiều đề còn đòi hỏi xử lý nhiều truy vấn trên cùng một đoạn số.
Trên máy tác giả, `count_primes_trial(1_000_000)` trả về đúng **78498** — con số này là chính xác, có thể tra cứu độc lập. Vấn đề không phải là đúng hay sai, mà là **chạy mất khoảng 0,9 giây** chỉ cho MỘT lần gọi. Một đề Tin học thường chấm hàng chục test, mỗi test một giới hạn thời gian khoảng 1 giây — 0,9 giây cho một test đã là quá sát, chưa kể nhiều đề còn đòi hỏi xử lý nhiều truy vấn trên cùng một đoạn số.

Để thấy rõ khoảng cách, ta đo cùng bài toán bằng một cách làm khác — sàng Eratosthenes, đánh dấu hợp số một lần cho cả đoạn thay vì kiểm tra riêng từng số. Cách làm cụ thể của sàng sẽ học kỹ ở khóa số học; ở đây ta chỉ cần thấy con số.

Đo trên cùng một máy, cùng đếm số nguyên tố trong đoạn

[1, 10^6]

, cả hai cách đều cho đúng 78498 số. Con số mili giây thực tế phụ thuộc máy chạy, nhưng tỉ lệ khoảng ba mươi lần nhanh hơn thì luôn đúng hướng.Đo trên cùng một máy, cùng đếm số nguyên tố trong đoạn $[1, 10^6]$, cả hai cách đều cho đúng 78498 số. Con số mili giây thực tế phụ thuộc máy chạy, nhưng tỉ lệ khoảng ba mươi lần nhanh hơn thì luôn đúng hướng.

Đây chính là chỗ khác nhau giữa bài chuẩn và bài nâng cao: không phải đề khó hiểu hơn, câu chữ của đề đếm số nguyên tố còn ngắn hơn cả đề tính tổng. Cái khác là ràng buộc dữ liệu buộc ta phải chọn thuật toán tốt hơn cách nghĩ đầu tiên.

Ý chính: dấu hiệu nâng cao nằm ở ràng buộc, không nằm ở câu chữ

Mở rộng dành cho HSG

Khái niệm ràng buộc dữ liệu (constraint) và ngân sách thời gian chạy không nằm trong yêu cầu cần đạt thông thường của Tin học 10 — SGK chủ yếu quan tâm code có chạy đúng hay không. Ta giới thiệu sớm vì đây là kỹ năng sống còn của mọi đề HSG Tin: đọc đề mà không để ý giới hạn N thì code đúng vẫn có thể bị chấm sai do quá thời gian (Time Limit Exceeded).

Một học sinh giỏi không đọc đề rồi viết code ngay. Việc đầu tiên là hỏi: N lớn cỡ nào? Đây không phải kỹ thuật cao siêu gì — chỉ là một thói quen, giống như đọc đề Toán phải để ý điều kiện của biến trước khi giải. Bỏ qua thói quen này có giá cụ thể: một bài chấm tự động không trừ điểm vì code "xấu", nó chỉ báo một trong hai trạng thái — Accepted (đúng và kịp giờ) hoặc không. Code đúng logic nhưng chạy quá giờ nhận kết quả Time Limit Exceeded, bị chấm sai y hệt như code sai logic, dù người viết biết chắc thuật toán của mình "đúng". Ba dấu hiệu hay gặp nhất trong một đề đã vượt mức luyện tập thông thường:

Một học sinh giỏi không đọc đề rồi viết code ngay. Việc đầu tiên là hỏi: *N lớn cỡ nào?* Đây không phải kỹ thuật cao siêu gì — chỉ là một thói quen, giống như đọc đề Toán phải để ý điều kiện của biến trước khi giải. Bỏ qua thói quen này có giá cụ thể: một bài chấm tự động không trừ điểm vì code "xấu", nó chỉ báo một trong hai trạng thái — Accepted (đúng và kịp giờ) hoặc không. Code đúng logic nhưng chạy quá giờ nhận kết quả **Time Limit Exceeded**, bị chấm sai y hệt như code sai logic, dù người viết biết chắc thuật toán của mình "đúng". Ba dấu hiệu hay gặp nhất trong một đề đã vượt mức luyện tập thông thường:

Con số giới hạn N lớn — ví dụ $N \le 10^6$ thay vì $N \le 100$ .
Giới hạn thời gian chạy được ghi rõ — thường 1 giây mỗi test.
Số lượng test lớn — bài chấm hàng chục, hàng trăm bộ dữ liệu, không chỉ một ví dụ mẫu.

- **Con số giới hạn N lớn** — ví dụ $N \le 10^6$ thay vì $N \le 100$. - **Giới hạn thời gian chạy được ghi rõ** — thường 1 giây mỗi test. - **Số lượng test lớn** — bài chấm hàng chục, hàng trăm bộ dữ liệu, không chỉ một ví dụ mẫu.

Học cách phân biệt hai nhóm này trước khi đặt bút — nhầm một chi tiết trình bày với một dấu hiệu ràng buộc dữ liệu là lỗi hay gặp ở học sinh mới làm quen đề HSG.

Cách dùng thực tế: đọc đề, gạch chân mọi con số và điều kiện xuất hiện, rồi xếp từng chi tiết vào một trong hai nhóm trên. Nếu nhóm bên trái có ít nhất một chi tiết, coi bài đó là nâng cao ngay từ đầu — không đợi code chạy chậm rồi mới nhận ra.

Bẫy thường gặp

Chạy đúng trên ví dụ mẫu của đề (thường n nhỏ, vài chục) rồi yên tâm nộp bài. Ví dụ mẫu luôn nhỏ để người đọc dễ hiểu đề, không phản ánh test thật. Luôn nhìn dòng ghi giới hạn N, không nhìn ví dụ, để đoán tốc độ cần có.

Luyện tập có hướng dẫn

Luyện tập độc lập

Kiểm tra nhanh

Tóm tắt

Một bài toán trở thành nâng cao không phải vì câu chữ khó đọc, mà vì ràng buộc dữ liệu (N lớn, thời gian chặt, nhiều test) buộc phải chọn thuật toán tốt hơn phản xạ đầu tiên. Việc đầu tiên khi đọc bất kỳ đề nào — trước cả khi nghĩ đến cách giải — là tìm dòng ghi giới hạn N.

Bài tiếp theo: biết một bài đã "nâng cao" chỉ là bước một. Bước hai là biến đề bài chữ đó thành một thuật toán cụ thể trước khi viết bất kỳ dòng Python nào — đó là nội dung của bài sau.