Bài 29.2: Chuẩn hóa tên và tách từ trong C++
Bài 29.2: Chuẩn hóa tên và tách từ trong C++
Trong quá trình làm việc với dữ liệu, đặc biệt là dữ liệu dạng văn bản như tên, địa chỉ, hoặc các câu văn, chúng ta thường xuyên gặp phải những chuỗi không "sạch": chúng có thể chứa khoảng trắng thừa, định dạng không nhất quán (chữ hoa/chữ thường lẫn lộn), hoặc các ký tự không mong muốn. Để xử lý hiệu quả và chính xác những dữ liệu này, việc chuẩn hóa (normalization) và tách từ (tokenization) là cực kỳ quan trọng.
Bài viết này sẽ hướng dẫn bạn cách thực hiện hai kỹ thuật này trong C++, tận dụng các công cụ mạnh mẽ từ thư viện chuẩn như string và stringstream.
Hành trình dọn dẹp dữ liệu: Chuẩn hóa chuỗi trong C++
Chuẩn hóa là quá trình biến đổi dữ liệu văn bản sang một định dạng nhất quán và sạch sẽ. Với các chuỗi thông thường hoặc tên, các bước chuẩn hóa phổ biến bao gồm:
- Loại bỏ khoảng trắng thừa ở đầu và cuối chuỗi (Trimming): Đây là vấn đề thường gặp nhất khi dữ liệu được nhập từ người dùng hoặc đọc từ các nguồn không đồng nhất.
- Giảm số lượng khoảng trắng giữa các từ: Biến đổi "Hello World" thành "Hello World".
- Chuyển đổi định dạng chữ (Case Conversion): Đưa tất cả về chữ thường ("hello world") hoặc chữ hoa ("HELLO WORLD"), hoặc viết hoa chữ cái đầu của mỗi từ ("Hello World").
Hãy xem cách chúng ta có thể thực hiện những điều này trong C++.
Ví dụ 1: Loại bỏ khoảng trắng đầu và cuối (Trim)
Để loại bỏ khoảng trắng (hoặc các ký tự trắng khác như tab, newline) ở đầu và cuối chuỗi, chúng ta có thể sử dụng các thuật toán của thư viện <algorithm> kết hợp với <cctype>.
#include <iostream>
#include <string>
#include <algorithm> // For find_if_not
#include <cctype> // For isspace
// Hàm kiểm tra xem một ký tự có phải là khoảng trắng hay không
bool is_space(char c) {
// isspace cần unsigned char để hoạt động đúng với mọi giá trị char
return isspace(static_cast<unsigned char>(c));
}
// Hàm loại bỏ khoảng trắng đầu và cuối chuỗi
string trim(const string& str) {
// Tìm ký tự không phải khoảng trắng đầu tiên từ đầu chuỗi
auto first_char = find_if_not(str.begin(), str.end(), is_space);
// Nếu chuỗi chỉ toàn khoảng trắng hoặc rỗng
if (first_char == str.end()) {
return ""; // Trả về chuỗi rỗng
}
// Tìm ký tự không phải khoảng trắng đầu tiên từ cuối chuỗi (sử dụng reverse_iterator)
auto last_char = find_if_not(str.rbegin(), str.rend(), is_space);
// .base() trên reverse_iterator trả về iterator tương ứng trong chuỗi gốc
// Iterator này trỏ tới VỊ TRÍ SAU ký tự mà reverse_iterator trỏ tới
auto last_char_base = last_char.base();
// Trả về chuỗi con từ first_char đến last_char_base
return string(first_char, last_char_base);
}
int main() {
string s1 = " Hello, C++ World! ";
string s2 = trim(s1);
cout << "Original: \"" << s1 << "\"" << endl;
cout << "Trimmed: \"" << s2 << "\"" << endl; // Output: "Hello, C++ World!"
string s3 = " \t\n ";
string s4 = trim(s3);
cout << "Original: \"" << s3 << "\"" << endl;
cout << "Trimmed: \"" << s4 << "\"" << endl; // Output: ""
string s5 = "";
string s6 = trim(s5);
cout << "Original: \"" << s5 << "\"" << endl;
cout << "Trimmed: \"" << s6 << "\"" << endl; // Output: ""
return 0;
}
Giải thích:
- Hàm
trimsử dụngfind_if_notđể tìm vị trí của ký tự đầu tiên không phải khoảng trắng từ đầu chuỗi (str.begin()) và ký tự cuối cùng không phải khoảng trắng từ cuối chuỗi (str.rbegin()). isspace(c)từ<cctype>là hàm kiểm tra ký tựccó phải là khoảng trắng (bao gồm cả space, tab, newline, carriage return, form feed, vertical tab) hay không.reverse_iterator(str.rbegin(),str.rend()) giúp duyệt chuỗi từ cuối lên đầu. Khi sử dụngfind_if_nottrên reverse iterator, nó sẽ tìm ký tự không phải khoảng trắng đầu tiên từ cuối chuỗi..base()chuyển đổireverse_iteratortrở lại thànhiteratorthông thường. Điều quan trọng cần nhớ làbase()của một reverse iterator luôn trỏ tới phần tử ở VỊ TRÍ SAU phần tử mà reverse iterator gốc trỏ tới. Do đó,last_char.base()sẽ là điểm cuối (exclusive) của chuỗi con mà chúng ta muốn trích xuất.- Cuối cùng, chúng ta tạo chuỗi con bằng constructor
string(iterator_start, iterator_end).
Ví dụ 2: Giảm khoảng trắng giữa các từ
Sau khi đã loại bỏ khoảng trắng ở hai đầu, chúng ta có thể muốn đảm bảo rằng giữa các từ chỉ có một khoảng trắng duy nhất.
#include <iostream>
#include <string>
#include <cctype>
// Hàm giảm nhiều khoảng trắng liên tiếp thành một
string reduce_multiple_spaces(const string& str) {
string result;
bool last_char_was_space = false;
for (char c : str) {
if (isspace(static_cast<unsigned char>(c))) {
// Nếu ký tự hiện tại là khoảng trắng VÀ ký tự trước đó không phải khoảng trắng,
// thì mới thêm MỘT khoảng trắng vào kết quả.
// Điều này ngăn chặn việc thêm nhiều khoảng trắng liên tiếp.
if (!last_char_was_space) {
result += ' ';
last_char_was_space = true;
}
} else {
// Nếu ký tự không phải khoảng trắng, thêm nó vào kết quả
result += c;
last_char_was_space = false;
}
}
// Lưu ý: Hàm này chưa xử lý khoảng trắng đầu/cuối.
// Cần kết hợp với hàm trim hoặc chuẩn hóa đầy đủ.
return result;
}
int main() {
string s1 = "Xin chao the gioi!";
string s2 = reduce_multiple_spaces(s1);
cout << "Original: \"" << s1 << "\"" << endl;
cout << "Reduced: \"" << s2 << "\"" << endl; // Output: "Xin chao the gioi!"
string s3 = " multiple spaces here "; // Vẫn còn khoảng trắng đầu cuối
string s4 = reduce_multiple_spaces(s3);
cout << "Original: \"" << s3 << "\"" << endl;
cout << "Reduced: \"" << s4 << "\"" << endl; // Output: " multiple spaces here " (Khoảng trắng đầu cuối vẫn còn)
return 0;
}
Giải thích:
- Chúng ta duyệt qua từng ký tự của chuỗi gốc.
- Biến
last_char_was_spaceđóng vai trò như một "bộ nhớ" nhỏ, ghi lại trạng thái của ký tự ngay trước đó. - Nếu gặp một ký tự khoảng trắng (
isspace), chúng ta chỉ thêm một khoảng trắng vào chuỗi kết quả (result) nếu ký tự trước đó không phải là khoảng trắng. Lần khoảng trắng tiếp theo (nếu có) sẽ bị bỏ qua vìlast_char_was_spaceđã làtrue. - Nếu gặp một ký tự không phải khoảng trắng, chúng ta luôn thêm nó vào
resultvà đặtlast_char_was_spacethànhfalse. - Phương pháp này hiệu quả trong việc giảm khoảng trắng giữa các ký tự, nhưng cần kết hợp với trimming để loại bỏ khoảng trắng ở hai đầu.
Ví dụ 3: Chuyển đổi định dạng chữ (Case Conversion)
Đôi khi, chúng ta muốn đưa tất cả văn bản về một dạng chữ nhất quán, ví dụ, tất cả là chữ thường. Điều này rất hữu ích khi so sánh chuỗi mà không quan tâm đến chữ hoa/thường.
#include <iostream>
#include <string>
#include <algorithm> // For transform
#include <cctype> // For tolower
// Hàm chuyển đổi chuỗi sang chữ thường
string to_lower(const string& str) {
string lower_str = str; // Tạo bản sao để thay đổi
transform(lower_str.begin(), lower_str.end(), lower_str.begin(),
[](unsigned char c){ return tolower(c); });
return lower_str;
}
// Hàm chuyển đổi chuỗi sang chữ hoa
string to_upper(const string& str) {
string upper_str = str; // Tạo bản sao để thay đổi
transform(upper_str.begin(), upper_str.end(), upper_str.begin(),
[](unsigned char c){ return toupper(c); });
return upper_str;
}
int main() {
string s1 = "Hello World C++";
string s2 = to_lower(s1);
string s3 = to_upper(s1);
cout << "Original: " << s1 << endl;
cout << "Lowercase: " << s2 << endl; // Output: hello world c++
cout << "Uppercase: " << s3 << endl; // Output: HELLO WORLD C++
return 0;
}
Giải thích:
- Hàm
transformtừ thư viện<algorithm>là công cụ lý tưởng cho việc áp dụng một phép biến đổi (ở đây làtolowerhoặctoupper) lên từng phần tử của một dãy (ở đây là các ký tự trong chuỗi). - Nó nhận các iterator đầu và cuối của dãy nguồn (
lower_str.begin(),lower_str.end()), iterator bắt đầu của dãy đích (cũng làlower_str.begin()để thay đổi trực tiếp trên bản sao), và hàm biến đổi ([](unsigned char c){ return tolower(c); }). - Chúng ta sử dụng lambda function để gói gọn cuộc gọi đến
tolowerhoặctoupper. Việc ép kiểu sangunsigned charlà cần thiết vì các hàm này trong<cctype>thường nhậninthoặcunsigned charvà hành vi vớicharcó thể không xác định nếucharlà kiểu signed và có giá trị âm.
Phân rã dữ liệu: Tách từ (Tokenization) trong C++
Sau khi đã có một chuỗi được chuẩn hóa, bước tiếp theo là chia nó thành các đơn vị nhỏ hơn có ý nghĩa, thường là các từ hoặc token. Quá trình này gọi là tách từ (tokenization). Ví dụ, chúng ta có thể muốn tách câu "Day la mot cau don gian" thành các từ "Day", "la", "mot", "cau", "don", "gian".
Trong C++, stringstream là một trong những công cụ phổ biến và tiện lợi nhất để thực hiện việc tách chuỗi dựa trên các ký tự phân cách.
Ví dụ 4: Tách chuỗi bằng khoảng trắng sử dụng stringstream
stringstream cho phép chúng ta xử lý một chuỗi như thể nó là một luồng nhập (giống như cin). Chúng ta có thể sử dụng toán tử >> để đọc từng "từ" một cách dễ dàng.
#include <iostream>
#include <string>
#include <sstream> // For stringstream
#include <vector> // To store the tokens
// Hàm tách chuỗi thành vector các từ dựa trên khoảng trắng
vector<string> split_by_space(const string& str) {
stringstream ss(str); // Khởi tạo stringstream với chuỗi đầu vào
string word;
vector<string> tokens;
// Toán tử >> đọc các phần tử được phân cách bởi khoảng trắng
while (ss >> word) {
tokens.push_back(word);
}
return tokens;
}
int main() {
string sentence = "Day la mot cau don gian";
vector<string> words = split_by_space(sentence);
cout << "Chuoi ban dau: \"" << sentence << "\"" << endl;
cout << "Cac tu da tach:" << endl;
for (const auto& w : words) {
cout << "- \"" << w << "\"" << endl;
}
// Minh họa tầm quan trọng của chuẩn hóa trước khi tách từ
string messy_sentence = " Day la mot cau don gian ";
// Tách trực tiếp chuỗi "bẩn"
vector<string> messy_words = split_by_space(messy_sentence);
cout << "\n--- Tach tu chuoi 'ban' ---" << endl;
for (const auto& w : messy_words) {
cout << "- \"" << w << "\"" << endl; // Output: "Day", "la", "mot", "cau", "don", "gian" - OK vi >> tu dong xu ly nhieu khoang trang giua!
}
// Tuy nhien, hay ket hop chuan hoa de dam bao tot hon:
string normalized_sentence = normalize_spaces(messy_sentence); // Su dung ham normalize_spaces tu truoc (can them dinh nghia o day hoac trong file header)
vector<string> normalized_words = split_by_space(normalized_sentence);
cout << "\n--- Tach tu chuoi da chuan hoa ---" << endl;
cout << "Chuoi da chuan hoa truoc khi tach: \"" << normalized_sentence << "\"" << endl;
for (const auto& w : normalized_words) {
cout << "- \"" << w << "\"" << endl; // Output: "Day", "la", "mot", "cau", "don", "gian" - OK
}
// Lưu ý: `>>` tự động bỏ qua khoảng trắng đầu và xử lý nhiều khoảng trắng giữa.
// Nhưng hàm `normalize_spaces` đảm bảo chuỗi sạch sẽ tổng thể hơn cho các mục đích khác.
return 0;
}
Giải thích:
- Chúng ta tạo một đối tượng
stringstreamvà truyền chuỗi cần tách vào constructor của nó. - Vòng lặp
while (ss >> word)là điểm mấu chốt. Toán tử>>khi được sử dụng vớistringstreamvà một biến kiểustringsẽ tự động đọc các ký tự từ luồng cho đến khi gặp một ký tự trắng (space, tab, newline...). Nó bỏ qua các ký tự trắng trước khi đọc và dừng lại trước ký tự trắng tiếp theo. Đoạn ký tự không phải trắng được đọc sẽ lưu vào biếnword. - Vòng lặp tiếp tục cho đến khi không còn ký tự không phải trắng nào để đọc từ
stringstream(luồngsstrở thànhfalse). - Mỗi
wordđọc được là một token và được thêm vào vectortokens. - Trong ví dụ thứ hai, bạn thấy
stringstreamxử lý khá tốt các khoảng trắng thừa giữa các từ. Tuy nhiên, việc chuẩn hóa toàn diện (bao gồm trimming) vẫn là cần thiết cho các trường hợp phức tạp hơn hoặc khi bạn muốn đảm bảo đầu vào luôn ở định dạng sạch trước khi xử lý.
Ví dụ 5: Tách chuỗi bằng ký tự phân cách tùy chỉnh
Đôi khi, chúng ta cần tách chuỗi dựa trên một ký tự khác ngoài khoảng trắng, ví dụ như dấu phẩy, dấu chấm phẩy, hoặc dấu gạch ngang. Hàm getline là công cụ thích hợp cho trường hợp này.
#include <iostream>
#include <string>
#include <sstream> // For stringstream
#include <vector> // To store the tokens
// Hàm tách chuỗi thành vector các token dựa trên một ký tự phân cách tùy chỉnh
vector<string> split_by_delimiter(const string& str, char delimiter) {
stringstream ss(str);
string segment;
vector<string> tokens;
// getline đọc chuỗi cho đến khi gặp ký tự phân cách
while (getline(ss, segment, delimiter)) {
tokens.push_back(segment);
}
return tokens;
}
int main() {
string data = "Apple,Banana,Orange,Grape";
char delimiter = ',';
vector<string> fruits = split_by_delimiter(data, delimiter);
cout << "Chuoi ban dau: \"" << data << "\"" << endl;
cout << "Cac token da tach (phan cach boi '" << delimiter << "'):" << endl;
for (const auto& f : fruits) {
cout << "- \"" << f << "\"" << endl;
}
// Output: Apple, Banana, Orange, Grape
string messy_data = " Item 1 ; Item 2 ;Item 3 ";
char another_delimiter = ';';
vector<string> items = split_by_delimiter(messy_data, another_delimiter);
cout << "\nChuoi ban dau: \"" << messy_data << "\"" << endl;
cout << "Cac token da tach (phan cach boi '" << another_delimiter << "'):" << endl;
for (const auto& item : items) {
// LƯU Ý QUAN TRỌNG: Khi dùng getline với delimiter KHÔNG phải khoảng trắng,
// khoảng trắng thừa ở đầu và cuối MỖI token sẽ KHÔNG bị loại bỏ tự động.
cout << "- \"" << item << "\"" << endl;
}
// Output: " Item 1 ", " Item 2 ", "Item 3 " -> Cần chuẩn hóa từng token con!
// Minh họa chuẩn hóa TỪNG token sau khi tách
cout << "\n--- Tach token roi chuan hoa tung token con ---" << endl;
for (const auto& item : items) {
string trimmed_item = trim(item); // Su dung lai ham trim tu vi du 1
cout << "- \"" << trimmed_item << "\"" << endl;
}
// Output: "Item 1", "Item 2", "Item 3" -> Day la ket qua mong muon!
return 0;
}
Giải thích:
- Hàm
getline(stream, string, delimiter)đọc các ký tự từstreamvàostringcho đến khi nó gặp ký tựdelimiter. Ký tự delimiter không được đưa vàostring. - Vòng lặp
while (getline(ss, segment, delimiter))sẽ liên tục đọc các "đoạn" của chuỗi được phân cách bởidelimitercho đến khi hết luồng. - Mỗi đoạn (
segment) đọc được là một token và được thêm vào vectortokens. - Điểm khác biệt quan trọng so với toán tử
>>:getlinekhông tự động bỏ qua khoảng trắng ở đầu hoặc cuối các token mà nó trích xuất, trừ khi ký tự phân cách là khoảng trắng. Do đó, khi tách bằng ký tự khác khoảng trắng (như dấu phẩy, dấu chấm phẩy), các token kết quả có thể vẫn còn chứa khoảng trắng thừa ở đầu hoặc cuối (ví dụ: " Item 2 "). Trong trường hợp này, bạn thường cần áp dụng lại các kỹ thuật chuẩn hóa (ví dụ: hàmtrimđã viết ở trên) lên từng token con sau khi tách để làm sạch chúng.
Kết hợp Chuẩn hóa và Tách từ
Trong các ứng dụng thực tế, chuẩn hóa và tách từ thường đi đôi với nhau. Một quy trình phổ biến để xử lý chuỗi đầu vào thô sẽ là:
- Nhận chuỗi đầu vào.
- Chuẩn hóa chuỗi: Loại bỏ khoảng trắng đầu/cuối, giảm khoảng trắng giữa, (tùy chọn) chuyển đổi định dạng chữ.
- Tách chuỗi đã chuẩn hóa thành các token dựa trên ký tự phân cách mong muốn (thường là khoảng trắng cho văn bản, hoặc dấu phẩy/chấm phẩy cho danh sách).
- (Tùy chọn) Chuẩn hóa từng token con: Nếu bạn tách bằng ký tự khác khoảng trắng, bạn có thể cần áp dụng lại
trimcho mỗi token để loại bỏ khoảng trắng thừa xung quanh nó.
Bài tập ví dụ: C++ Bài 18.A2: Giao bóng cầu lông
Giao bóng cầu lông
FullHouse Dev đang chơi một trận cầu lông đơn. Luật giao bóng trong trận đấu này như sau:
- Người chơi bắt đầu trận đấu sẽ giao bóng từ bên phải sân của họ.
- Bất cứ khi nào một người chơi giành được điểm, họ sẽ được giao bóng tiếp theo.
- Nếu người giao bóng đã giành được số điểm chẵn trong một ván, họ sẽ giao bóng từ bên phải sân cho điểm tiếp theo.
- FullHouse Dev sẽ là người bắt đầu trận đấu.
Cho biết số điểm P mà FullHouse Dev đạt được khi kết thúc trận đấu, hãy xác định xem FullHouse Dev đã giao bóng từ bên phải sân bao nhiêu lần.
INPUT FORMAT
- Dòng đầu tiên chứa một số nguyên T, biểu thị số lượng bộ test.
- Mỗi bộ test bao gồm một dòng chứa một số nguyên P, là số điểm mà FullHouse Dev đạt được.
OUTPUT FORMAT
- Với mỗi bộ test, in ra một dòng duy nhất số lần FullHouse Dev đã giao bóng từ bên phải sân.
CONSTRAINTS
- \(1 ≤ T ≤ 10^3\)
- \(0 ≤ P ≤ 10^9\)
Ví dụ
Input
4
2
9
53
746Output
2
5
27
374Giải thích:
Test 1: FullHouse Dev đạt được 2 điểm khi kết thúc trận đấu. Điều này có nghĩa là anh ấy đã giao bóng hai lần từ bên phải sân, một lần khi điểm số của anh ấy là 0 và một lần nữa khi điểm số là 2.
Test 2: FullHouse Dev đạt được 9 điểm khi kết thúc trận đấu. Điều này có nghĩa là anh ấy đã giao bóng 5 lần từ bên phải sân. Các điểm số khi anh ấy phải giao bóng từ bên phải là: 0, 2, 4, 6, 8. Chào bạn, đây là hướng dẫn giải bài tập "Giao bóng cầu lông" bằng C++.
Bài toán yêu cầu đếm số lần FullHouse Dev giao bóng từ bên phải sân, biết rằng anh ấy đạt được P điểm khi kết thúc trận đấu và tuân thủ các luật đã cho.
Hãy phân tích các luật và cách chúng ảnh hưởng đến việc giao bóng từ bên phải:
FullHouse Dev bắt đầu trận đấu: Điều này có nghĩa là giao bóng đầu tiên thuộc về Dev, và theo luật, giao bóng đầu tiên là từ bên phải (khi điểm số của Dev là 0). Đây là lần giao bóng từ bên phải đầu tiên.
Người giành điểm sẽ giao bóng tiếp theo: Điều này rất quan trọng. Nếu Dev thắng một điểm, anh ấy sẽ là người giao bóng ở lượt tiếp theo.
Giao bóng từ bên phải khi điểm số của người giao bóng là số chẵn: Khi đến lượt Dev giao bóng, anh ấy sẽ kiểm tra điểm số hiện tại của mình. Nếu điểm số là chẵn, anh ấy giao bóng từ bên phải; nếu là lẻ, từ bên trái.
Phân tích trình tự giao bóng và điểm số:
- Dev bắt đầu trận đấu, điểm số của Dev là 0 (chẵn). Anh ấy giao bóng từ phải.
- Giả sử Dev thắng điểm đó. Điểm số của Dev trở thành 1. Theo luật 2, Dev giao bóng lượt tiếp theo. Điểm số của Dev lúc này là 1 (lẻ). Anh ấy giao bóng từ trái.
- Giả sử Dev thắng điểm đó. Điểm số của Dev trở thành 2. Theo luật 2, Dev giao bóng lượt tiếp theo. Điểm số của Dev lúc này là 2 (chẵn). Anh ấy giao bóng từ phải.
- Giả sử Dev thắng điểm đó. Điểm số của Dev trở thành 3. Theo luật 2, Dev giao bóng lượt tiếp theo. Điểm số của Dev lúc này là 3 (lẻ). Anh ấy giao bóng từ trái.
- Giả sử Dev thắng điểm đó. Điểm số của Dev trở thành 4. Theo luật 2, Dev giao bóng lượt tiếp theo. Điểm số của Dev lúc này là 4 (chẵn). Anh ấy giao bóng từ phải.
Cứ như vậy, FullHouse Dev sẽ giao bóng từ bên phải sân mỗi khi đến lượt anh ấy giao bóng và điểm số của anh ấy tại thời điểm giao bóng đó là một số chẵn không âm.
Bài toán cho biết Dev đạt được P điểm khi kết thúc trận đấu. Điều này ngụ ý rằng Dev đã giành được các điểm để nâng điểm số của mình lần lượt từ 0 lên 1, từ 1 lên 2, ..., cho đến P-1 lên P. Mỗi khi Dev giành được một điểm (ngoại trừ điểm cuối cùng có thể kết thúc trận đấu), anh ấy sẽ giao bóng ở lượt tiếp theo. Ngoài ra, anh ấy còn giao bóng ở lượt đầu tiên khi điểm số là 0.
Vậy, các điểm số tại thời điểm Dev thực hiện giao bóng (nếu anh ấy giành được quyền giao bóng) sẽ là 0, 1, 2, 3, ..., P. (Lưu ý: điểm số P là điểm cuối cùng anh ấy đạt được, và anh ấy sẽ giao bóng sau khi đạt điểm P, nếu trận đấu chưa kết thúc. Tuy nhiên, câu hỏi là "khi kết thúc trận đấu", ngụ ý chúng ta xét các lần giao bóng dẫn đến hoặc xảy ra khi điểm số đạt đến P).
Chúng ta cần đếm số lần Dev giao bóng từ bên phải. Điều này xảy ra khi điểm số của anh ấy tại thời điểm giao bóng là số chẵn. Các điểm số chẵn trong dãy 0, 1, 2, ..., P là: 0, 2, 4, 6, ..., cho đến số chẵn lớn nhất nhỏ hơn hoặc bằng P.
Nhiệm vụ là đếm số lượng số chẵn không âm từ 0 đến P (bao gồm cả 0 và, nếu P chẵn, cả P).
Ví dụ:
- Nếu P=2: Các điểm số lúc giao bóng là 0, 1, 2. Các điểm chẵn là 0, 2. Có 2 lần.
- Nếu P=9: Các điểm số lúc giao bóng là 0, 1, 2, ..., 9. Các điểm chẵn là 0, 2, 4, 6, 8. Có 5 lần.
- Nếu P=53: Các điểm số lúc giao bóng là 0, 1, 2, ..., 53. Các điểm chẵn là 0, 2, 4, ..., 52. Có bao nhiêu số?
- Nếu P=746: Các điểm số lúc giao bóng là 0, 1, 2, ..., 746. Các điểm chẵn là 0, 2, 4, ..., 746. Có bao nhiêu số?
Cách đếm số chẵn từ 0 đến P:
Các số chẵn có dạng 2k, với k là số nguyên không âm.
Ta cần tìm số lượng giá trị k sao cho 0 ≤ 2k ≤ P.
Điều này tương đương với 0 ≤ k ≤ P/2.
Số lượng các giá trị nguyên của k từ 0 đến P/2 (bao gồm cả 0 và P/2 nếu là số nguyên) là (P/2 - 0 + 1) = P/2 + 1.
Trong C++, phép chia số nguyên P / 2 tự động làm tròn xuống (floor) cho P không âm, nên nó chính xác là floor(P/2).
Do đó, số lần giao bóng từ bên phải là P / 2 + 1.
Cấu trúc chương trình C++:
- Đọc số bộ test T.
- Sử dụng vòng lặp (ví dụ
whilehoặcfor) chạy T lần. - Bên trong vòng lặp:
- Đọc số điểm P.
- Tính kết quả bằng công thức
P / 2 + 1. - In kết quả ra màn hình, theo sau là ký tự xuống dòng.
Lưu ý khi triển khai:
- Sử dụng các hàm nhập/xuất chuẩn của C++:
cinvàcout. - Cần include thư viện
iostream. - Để tăng tốc độ nhập xuất (không bắt buộc với ràng buộc T nhỏ nhưng là thói quen tốt), có thể thêm
ios_base::sync_with_stdio(false); cin.tie(NULL);ở đầu hàm main. - Biến P có thể lên tới 10^9, kiểu
inttrong C++ thường đủ lớn (đến khoảng 2*10^9), nhưng để an toàn tuyệt đối có thể dùnglong long. Kết quả P/2 + 1 cũng sẽ nằm trong phạm vi tương tự.
Đây là hướng đi để giải quyết bài toán. Bạn chỉ cần cài đặt logic đơn giản này vào code C++.
Comments