HƯỚNG DẪN VÀ GỢI Ý BỘ ĐỀ KIỂM TRA C++ CƠ BẢN–TRUNG BÌNH

1. Thông tin chung

• Số câu: 4 câu.
• Thời gian đề xuất: 90 phút.
• Ngôn ngữ: C++17.
• Tổng điểm: 100 điểm.
• Nội dung: chuỗi, vòng lặp, hàm, số nguyên tố, mảng một chiều, mảng hai chiều, set và map.

2. Quy tắc sử dụng tài liệu gợi ý

Tài liệu này chỉ định hướng cách phân tích bài toán, không cung cấp chương trình hoàn chỉnh. Học sinh cần tự viết phần nhập dữ liệu, xử lý và xuất kết quả.

Giáo viên có thể cung cấp gợi ý theo ba mức:

1. Gợi ý mức 1: Nhắc lại mục tiêu và kiến thức cần sử dụng.
2. Gợi ý mức 2: Gợi ý biến, cấu trúc dữ liệu và luồng xử lý.
3. Gợi ý mức 3: Cung cấp đoạn mã khung cho phần quan trọng nhất.

Câu 1. Xếp sách — 20 điểm

1.1. Mục tiêu

Cho một xâu chỉ gồm các ký tự T, V và A. Cần sắp xếp lại các ký tự theo thứ tự:

T → V → A

Ví dụ, với xâu:

VATATV

kết quả sau khi xếp lại là:

TTVVAA

1.2. Kiến thức được kiểm tra

• Khai báo và nhập một biến string.
• Duyệt từng ký tự trong xâu.
• Sử dụng vòng lặp for.
• Sử dụng câu lệnh if hoặc if...else.
• Đếm số lần xuất hiện của từng ký tự.

1.3. Phân tích

Xâu chỉ có ba loại ký tự. Vì vậy, không cần sử dụng thuật toán sắp xếp thông thường. Chỉ cần:

1. Đếm số lượng ký tự T.
2. Đếm số lượng ký tự V.
3. Đếm số lượng ký tự A.
4. In tất cả ký tự T, sau đó in V, cuối cùng in A.

Độ phức tạp của cách làm này là O(n), trong đó n là độ dài xâu.

1.4. Gợi ý mức 1

Tạo ba biến đếm:

long long demT = 0;
long long demV = 0;
long long demA = 0;

Duyệt từng ký tự trong xâu và tăng biến tương ứng.

1.5. Gợi ý mức 2

Có thể duyệt xâu bằng vòng lặp theo chỉ số:

for (int i = 0; i < s.size(); i++)
{
    // Kiểm tra s[i]
}

Hoặc sử dụng vòng lặp for theo phạm vi:

for (char c : s)
{
    // Kiểm tra c
}

Mỗi khi gặp ký tự nào, tăng biến đếm của ký tự đó.

1.6. Gợi ý mức 3

Sau khi đếm xong, có thể dùng ba vòng lặp để in kết quả:

for (int i = 0; i < demT; i++)
{
    cout << 'T';
}

Thực hiện tương tự với V và A, đúng theo thứ tự yêu cầu.

1.7. Mô phỏng

Với:

s = "VATATV"

Sau khi duyệt:

Vì vậy, chương trình in TT, tiếp theo VV, cuối cùng AA.

1.8. Lỗi thường gặp

• So sánh ký tự bằng "T" thay vì 'T'.
• In thêm dấu cách giữa các ký tự trong khi đề yêu cầu một xâu liên tục.
• In sai thứ tự, chẳng hạn A, T, V.
• Dùng sort() mặc định. Thứ tự mã ký tự không bảo đảm cho kết quả T, V, A.
• Quên khởi tạo biến đếm bằng 0.

1.9. Tự kiểm tra

Hãy thử chương trình với các trường hợp:

T

AAA

AVT

TVAATV

Câu 2. Số nguyên tố — 25 điểm

2.1. Mục tiêu

Bài yêu cầu xử lý các số nguyên tố trong một dãy. Tùy nội dung chính xác của đề gốc, học sinh có thể phải tìm số nguyên tố lớn nhất, lưu vị trí hoặc in kết quả theo yêu cầu.

Phần quan trọng nhất là xây dựng một hàm kiểm tra số nguyên tố chính xác và đủ nhanh.

2.2. Kiến thức được kiểm tra

• Khai báo và gọi hàm.
• Hàm trả về kiểu bool.
• Vòng lặp và phép chia lấy dư %.
• Duyệt mảng hoặc vector.
• Tìm giá trị lớn nhất và lưu vị trí.

2.3. Định nghĩa cần nhớ

Số nguyên tố là số nguyên dương:

• lớn hơn hoặc bằng 2;
• chỉ có đúng hai ước dương là 1 và chính nó.

Vì vậy:

• 0 không phải số nguyên tố;
• 1 không phải số nguyên tố;
• 2 là số nguyên tố nhỏ nhất.

2.4. Gợi ý mức 1

Chia bài thành hai nhiệm vụ:

1. Viết hàm kiểm tra một số có phải số nguyên tố không.
2. Duyệt dãy và cập nhật kết quả khi gặp số nguyên tố.

Khung hàm:

bool laSoNguyenTo(long long n)
{
    // Trả về true hoặc false
}

2.5. Gợi ý mức 2 — Kiểm tra số nguyên tố

Nếu n < 2, có thể kết luận ngay:

if (n < 2)
{
    return false;
}

Nếu n có một ước khác 1 và chính nó, ước đó phải có ít nhất một giá trị không vượt quá sqrt(n). Do đó, chỉ cần duyệt:

for (long long i = 2; i * i <= n; i++)
{
    if (n % i == 0)
    {
        return false;
    }
}

Nếu không tìm được ước nào thì trả về true.

2.6. Tại sao chỉ cần kiểm tra đến căn bậc hai?

Giả sử n = a × b. Nếu cả a và b đều lớn hơn sqrt(n) thì:

a × b > n

điều này mâu thuẫn với n = a × b. Vì vậy, nếu n là hợp số thì phải có ít nhất một ước không vượt quá sqrt(n).

2.7. Gợi ý mức 3 — Duyệt dãy

for (int i = 0; i < n; i++)
{
    if (laSoNguyenTo(a[i]))
    {
        // Cập nhật kết quả theo yêu cầu của đề
    }
}

Nếu đề yêu cầu tìm số nguyên tố lớn nhất và vị trí của nó, nên có các biến:

long long giaTriLonNhat;
int viTri;
bool daTimThay = false;

Biến daTimThay giúp xử lý trường hợp dãy không có số nguyên tố.

2.8. Những điều phải đọc kỹ trong đề

• Nếu không có số nguyên tố thì phải in gì?
• Vị trí được tính từ 0 hay từ 1?
• Nếu số nguyên tố lớn nhất xuất hiện nhiều lần, lấy vị trí đầu tiên hay cuối cùng?
• Đề yêu cầu in giá trị, vị trí hay cả hai?

Nếu đề tính vị trí từ 1, vị trí tương ứng của a[i] thường là i + 1.

2.9. Mô phỏng

Với dãy:

4 7 8 11 6

Nếu đề yêu cầu số nguyên tố lớn nhất thì kết quả cần lưu là 11.

2.10. Lỗi thường gặp

• Xem 0 hoặc 1 là số nguyên tố.
• Kiểm tra từ 2 đến n - 1, khiến chương trình chậm.
• Dùng điều kiện i < sqrt(n) và bỏ sót căn bậc hai.
• Không xử lý trường hợp không có số nguyên tố.
• Chỉ cập nhật giá trị nhưng quên cập nhật vị trí.
• Khởi tạo kết quả bằng 0 trong khi dãy có thể chứa số âm.
• Dùng int cho dữ liệu lớn và làm i * i bị tràn số.

2.11. Tự kiểm tra hàm

Hãy kiểm tra hàm với:

-5, 0, 1, 2, 3, 4, 9, 17, 25, 97

Kết quả đúng:

Câu 3. Tổng mảng hai chiều — 25 điểm

3.1. Mục tiêu

Cho một bảng số nguyên có m hàng và n cột. Hãy tính tổng các phần tử theo yêu cầu của đề.

Nếu đề yêu cầu tổng toàn bộ ma trận, cần cộng tất cả m × n phần tử.

3.2. Kiến thức được kiểm tra

• Khai báo mảng hai chiều.
• Sử dụng hai vòng lặp lồng nhau.
• Nhập và truy cập phần tử a[i][j].
• Tính tổng bằng kiểu dữ liệu phù hợp.

3.3. Cấu trúc của ma trận

Với ma trận m × n:

• m là số hàng;
• n là số cột;
• a[i][j] là phần tử tại hàng i, cột j.

Nếu chỉ số bắt đầu từ 0:

i chạy từ 0 đến m - 1
j chạy từ 0 đến n - 1

3.4. Gợi ý mức 1

Muốn duyệt toàn bộ ma trận, cần hai vòng lặp:

for (int i = 0; i < m; i++)
{
    for (int j = 0; j < n; j++)
    {
        // Xử lý phần tử tại hàng i, cột j
    }
}

3.5. Gợi ý mức 2 — Khai báo và nhập

Có thể sử dụng mảng tĩnh nếu giới hạn cho phép:

long long a[1005][1005];

Hoặc sử dụng vector:

vector<vector<long long>> a(m, vector<long long>(n));

Nhập từng phần tử:

for (int i = 0; i < m; i++)
{
    for (int j = 0; j < n; j++)
    {
        cin >> a[i][j];
    }
}

3.6. Gợi ý mức 3 — Tính tổng

Tạo biến tổng bên ngoài cả hai vòng lặp:

long long tong = 0;

Mỗi khi đọc hoặc duyệt một phần tử:

tong += a[i][j];

Sau khi duyệt hết ma trận, in biến tong.

3.7. Cách làm không cần lưu ma trận

Nếu đề chỉ yêu cầu tính tổng và không cần dùng lại các phần tử, có thể vừa nhập vừa cộng:

long long tong = 0;

for (int i = 0; i < m; i++)
{
    for (int j = 0; j < n; j++)
    {
        long long x;
        cin >> x;
        tong += x;
    }
}

Cách này chỉ dùng O(1) bộ nhớ phụ.

3.8. Mô phỏng

Với ma trận:

2 3
1 2 3
4 5 6

Quá trình cộng:

tong = 0
tong = 0 + 1
tong = 1 + 2
tong = 3 + 3
tong = 6 + 4
tong = 10 + 5
tong = 15 + 6

Kết quả cuối cùng là 21.

3.9. Phân biệt một số yêu cầu thường gặp

Học sinh cần đọc đúng yêu cầu đề, không tự thêm điều kiện khi đề chỉ yêu cầu tổng toàn bộ ma trận.

3.10. Lỗi thường gặp

• Đảo số hàng m và số cột n.
• Vòng ngoài chạy n lần, vòng trong chạy m lần không đúng với cách lưu dữ liệu.
• Khởi tạo tong = 0 bên trong vòng lặp làm tổng bị đặt lại.
• Chỉ cộng các phần tử trên đường chéo.
• Truy cập vượt phạm vi mảng.
• Dùng int khi tổng có thể vượt giới hạn khoảng 2,1 tỷ.
• Khai báo mảng cục bộ quá lớn và gây lỗi bộ nhớ ngăn xếp.

3.11. Tự kiểm tra

Nên thử các trường hợp:

• Ma trận 1 × 1.
• Ma trận chỉ có một hàng.
• Ma trận chỉ có một cột.
• Ma trận có số âm.
• Ma trận có tổng bằng 0.

Câu 4. Xâu chẵn — 30 điểm

4.1. Mục tiêu

Một xâu được gọi là xâu chẵn nếu số lần xuất hiện của từng ký tự trong xâu đều là số chẵn.

Ví dụ:

aabbcc

là xâu chẵn vì a, b và c đều xuất hiện hai lần.

Xâu:

aabcc

không phải xâu chẵn vì b xuất hiện một lần.

4.2. Kiến thức được kiểm tra

• Nhập và duyệt chuỗi.
• Đếm tần suất ký tự.
• Sử dụng map, set hoặc mảng đếm.
• Kiểm tra tính chẵn lẻ bằng % 2.
• Sử dụng biến kiểu bool.

4.3. Nhận xét quan trọng

Không thể chỉ kiểm tra độ dài xâu.

Ví dụ, xâu:

ab

có độ dài chẵn nhưng a và b đều xuất hiện một lần. Vì vậy đây không phải xâu chẵn.

Điều phải kiểm tra là tần suất của từng loại ký tự.

4.4. Cách 1 — Sử dụng map

Gợi ý mức 1

Dùng map<char, int> để lưu số lần xuất hiện:

map<char, int> dem;

Gợi ý mức 2

Duyệt xâu và đếm:

for (char c : s)
{
    dem[c]++;
}

Sau đó duyệt map:

for (auto p : dem)
{
    // p.first  là ký tự
    // p.second là số lần xuất hiện
}

Gợi ý mức 3

Nếu một tần suất là số lẻ:

p.second % 2 != 0

thì có thể kết luận xâu không phải xâu chẵn.

4.5. Cách 2 — Sử dụng mảng đếm

Nếu đề bảo đảm xâu chỉ gồm chữ cái thường từ a đến z, có thể khai báo:

int dem[26] = {};

Mỗi ký tự được chuyển thành chỉ số:

dem[c - 'a']++;

Ví dụ:

'a' - 'a' = 0
'b' - 'a' = 1
'c' - 'a' = 2

Sau khi đếm, duyệt các vị trí từ 0 đến 25. Nếu có dem[i] lẻ thì xâu không thỏa mãn.

Cách này có độ phức tạp O(n + 26), có thể xem là O(n).

4.6. Cách 3 — Sử dụng set

Có thể dùng set<char> để lưu những ký tự đang có số lần xuất hiện lẻ:

set<char> le;

Với mỗi ký tự c:

• Nếu c chưa có trong tập hợp, thêm c.
• Nếu c đã có trong tập hợp, xóa c.

Khung xử lý:

for (char c : s)
{
    if (le.count(c) == 0)
    {
        le.insert(c);
    }
    else
    {
        le.erase(c);
    }
}

Sau khi duyệt:

• le.empty() bằng true: mọi ký tự xuất hiện chẵn lần.
• Tập hợp không rỗng: còn ít nhất một ký tự xuất hiện lẻ lần.

4.7. Mô phỏng cách dùng set

Với xâu aabb:

Tập hợp cuối cùng rỗng nên đây là xâu chẵn.

Với xâu aab:

Tập hợp còn ký tự b, vì vậy xâu không chẵn.

4.8. So sánh các cách làm

4.9. Lỗi thường gặp

• Chỉ kiểm tra s.size() % 2 == 0.
• Cho rằng set.count(c) trả về số lần ký tự xuất hiện. Với set, kết quả chỉ là 0 hoặc 1.
• Dùng map nhưng quên tăng tần suất.
• In sai chính tả hoặc sai chữ hoa/chữ thường. Nếu đề yêu cầu Yes và No, cần in đúng hoàn toàn.
• In Yes trước khi kiểm tra hết các ký tự.
• Không dừng hoặc không dùng biến đánh dấu khi đã phát hiện một tần suất lẻ.

4.10. Tự kiểm tra

5. Gợi ý phân bổ thời gian

6. Danh sách kiểm tra trước khi nộp

Trước khi nộp mỗi bài, học sinh nên tự kiểm tra:

• Đã nhập đúng thứ tự và đúng số lượng dữ liệu chưa?
• Vòng lặp có chạy đúng giới hạn không?
• Có truy cập vượt giới hạn mảng hoặc chuỗi không?
• Biến đếm và biến tổng đã được khởi tạo chưa?
• Có cần dùng long long thay cho int không?
• Kết quả có đúng chữ hoa, chữ thường và dấu cách theo đề không?
• Đã xử lý trường hợp nhỏ nhất chưa?
• Đã thử trường hợp không có phần tử thỏa mãn chưa?
• Chương trình có in thêm nội dung không được yêu cầu không?

7. Gợi ý tiêu chí chấm

Câu 1 — 20 điểm

Câu 2 — 25 điểm

Câu 3 — 25 điểm

Câu 4 — 30 điểm

8. Kết luận

Bộ đề đánh giá khả năng phối hợp nhiều kiến thức C++ cơ bản–trung bình. Học sinh không chỉ cần nhớ cú pháp mà còn phải biết:

• chia bài toán thành các bước nhỏ;
• lựa chọn cấu trúc dữ liệu phù hợp;
• kiểm tra các trường hợp đặc biệt;
• đọc chính xác yêu cầu dữ liệu vào và dữ liệu ra;
• tự tạo test để phát hiện lỗi trước khi nộp.