Bài 29.4: Bài toán tần suất ký tự trong C++
Bài 29.4: Bài toán tần suất ký tự trong C++
Chào mừng trở lại với hành trình chinh phục C++ cùng FullhouseDev!
Trong thế giới lập trình và xử lý dữ liệu, có những bài toán tưởng chừng đơn giản nhưng lại là nền tảng cho rất nhiều ứng dụng phức tạp hơn. Một trong số đó chính là bài toán tần suất ký tự (Character Frequency Problem). Hôm nay, chúng ta sẽ cùng nhau khám phá bài toán này, hiểu rõ bản chất của nó và quan trọng nhất là cách giải quyết một cách hiệu quả, "chuẩn C++"!
Bài toán tần suất ký tự là gì?
Đúng như tên gọi, bài toán này yêu cầu chúng ta đếm xem mỗi ký tự trong một đoạn văn bản hoặc một chuỗi (string) xuất hiện bao nhiêu lần.
Ví dụ, nếu bạn có chuỗi "Hello World!", tần suất ký tự của nó sẽ là:
- 'H': 1 lần
- 'e': 1 lần
- 'l': 3 lần
- 'o': 2 lần
- ' ': 1 lần (ký tự khoảng trắng cũng được tính nhé!)
- 'W': 1 lần
- 'r': 1 lần
- 'd': 1 lần
- '!': 1 lần
Lưu ý rằng trong ví dụ trên, chúng ta đang phân biệt chữ hoa chữ thường ('H' và 'h' là khác nhau). Yêu cầu của bài toán có thể thay đổi tùy theo ngữ cảnh, chẳng hạn như không phân biệt chữ hoa chữ thường, hoặc chỉ đếm các ký tự chữ cái, v.v.
Tại sao bài toán này quan trọng?
Bạn có thể tự hỏi, đếm tần suất ký tự thì có gì thú vị hay ứng dụng gì mà lại được xem là kinh điển? Thực tế, bài toán này xuất hiện trong nhiều lĩnh vực:
- Phân tích văn bản: Hiểu cấu trúc ngôn ngữ, nhận dạng tác giả (dựa trên tần suất các ký tự hoặc cụm từ).
- Nén dữ liệu: Các thuật toán nén đơn giản như Huffman Coding dựa trên tần suất xuất hiện của các ký hiệu để gán mã ngắn hơn cho các ký hiệu phổ biến.
- Mật mã học cơ bản: Phân tích tần suất ký tự trong văn bản mã hóa (Frequency Analysis) là một kỹ thuật cơ bản để phá các mã hóa thay thế đơn giản.
- Xử lý dữ liệu: Đôi khi bạn chỉ cần thống kê sự phân bố của các ký tự trong một tập dữ liệu.
Nắm vững cách giải bài toán này không chỉ giúp bạn giải quyết các vấn đề cụ thể mà còn rèn luyện kỹ năng sử dụng cấu trúc dữ liệu để giải quyết các bài toán đếm và thống kê.
Giải pháp C++: Sử dụng map
Để đếm tần suất của các ký tự, chúng ta cần một cách để lưu trữ cặp giá trị: ký tự và số lần xuất hiện của nó. Mỗi ký tự là duy nhất trong danh sách thống kê (chúng ta không đếm 'l' nhiều lần trong danh sách, chỉ là đếm xem nó xuất hiện bao nhiêu lần), và chúng ta cần một giá trị số để lưu số đếm tương ứng.
Cấu trúc dữ liệu nào trong C++ đáp ứng được yêu cầu này? Chính là map hoặc unordered_map!
map: Lưu trữ các cặp key-value theo thứ tự tăng dần của key. Key của chúng ta sẽ làchar(ký tự), và value sẽ làint(số đếm).unordered_map: Tương tự nhưmapnhưng không đảm bảo thứ tự và thường có hiệu suất trung bình tốt hơn (nhờ sử dụng bảng băm).
Trong phần này, chúng ta sẽ bắt đầu với map vì nó tự động sắp xếp các ký tự, giúp kết quả in ra trông gọn gàng hơn.
Cách tiếp cận sẽ như sau:
- Đọc chuỗi input.
- Tạo một
map<char, int>trống để lưu tần suất. - Duyệt qua từng ký tự trong chuỗi input.
- Với mỗi ký tự, chúng ta sử dụng nó làm key để truy cập hoặc thêm vào map:
- Nếu ký tự đó đã tồn tại trong map (tức là đã gặp trước đó), chúng ta chỉ việc tăng giá trị đếm tương ứng lên 1.
- Nếu ký tự đó chưa có trong map, khi chúng ta truy cập
map[ky_tu],mapsẽ tự động thêm ký tự đó vào làm key với giá trị khởi tạo mặc định là 0. Sau đó, toán tử++sẽ biến giá trị đó thành 1. Đây là một tính năng rất tiện lợi củamapvàunordered_map!
- Sau khi duyệt hết chuỗi, map của chúng ta sẽ chứa đầy đủ tần suất của tất cả các ký tự xuất hiện.
- Cuối cùng, chúng ta duyệt qua map và in kết quả.
Hãy cùng xem code C++ để hiện thực hóa ý tưởng này:
#include <iostream>
#include <string>
#include <map>
int main() {
string s = "Lap trinh C++ that thu vi va huu ich!";
map<char, int> tanSuat;
for (char c : s) {
tanSuat[c]++;
}
cout << "--- Tan suat ky tu trong chuoi (phan biet hoa thuong) ---" << endl;
for (const auto& p : tanSuat) {
cout << "Ky tu '" << p.first << "': " << p.second << " lan" << endl;
}
cout << "------------------------------------------------------" << endl;
return 0;
}
Output:
--- Tan suat ky tu trong chuoi (phan biet hoa thuong) ---
Ky tu ' ': 7 lan
Ky tu '+': 2 lan
Ky tu 'C': 1 lan
Ky tu 'L': 1 lan
Ky tu 'a': 3 lan
Ky tu 'c': 1 lan
Ky tu 'e': 1 lan
Ky tu 'h': 2 lan
Ky tu 'i': 3 lan
Ky tu 'm': 1 lan
Ky tu 'n': 1 lan
Ky tu 'p': 1 lan
Ky tu 'r': 1 lan
Ky tu 't': 4 lan
Ky tu 'u': 2 lan
Ky tu 'v': 1 lan
Ky tu 'x': 1 lan
------------------------------------------------------Giải thích code:
- Chúng ta include các header cần thiết:
<iostream>,<string>,<map>. - Một
stringtênsđược khai báo với dữ liệu đầu vào. map<char, int> tanSuat;tạo một map trống.- Vòng lặp
for (char c : s)là cách tiện lợi để duyệt qua mỗi ký tự trong chuỗis. Biếncsẽ lần lượt nhận giá trị của từng ký tự. tanSuat[c]++;là dòng code "ma thuật" chính. Khi ký tựcđược dùng làm chỉ mục chomap tanSuat, nếucchưa tồn tại làm key,mapsẽ tạo một entry mớic -> 0. Sau đó, toán tử++tăng giá trị từ 0 lên 1. Nếucđã tồn tại, toán tử++chỉ đơn giản là tăng giá trị hiện tại lên 1.- Vòng lặp thứ hai
for (const auto& p : tanSuat)duyệt qua từng cặp (key-value) trong map.p.firstlà key (ký tự),p.secondlà value (tần suất).const auto&là cách khai báo gọn gàng và hiệu quả. cout << ...được sử dụng để in kết quả ra màn hình.
Chạy đoạn code này, bạn sẽ thấy tần suất của từng ký tự xuất hiện trong chuỗi s, bao gồm cả khoảng trắng và các ký tự đặc biệt khác, và kết quả sẽ được sắp xếp theo thứ tự các ký tự (vì chúng ta dùng map).
Biến tấu: Không phân biệt chữ hoa chữ thường và chỉ đếm chữ cái
Yêu cầu bài toán thường linh hoạt. Đôi khi chúng ta chỉ muốn đếm tần suất của các ký tự chữ cái và không quan tâm chúng là chữ hoa hay chữ thường.
Để làm được điều này, chúng ta cần thực hiện hai bước bổ sung trong vòng lặp đếm:
- Kiểm tra xem ký tự hiện tại có phải là chữ cái không.
- Nếu là chữ cái, chuyển nó về cùng một kiểu (ví dụ: chữ thường) trước khi dùng làm key trong map.
C++ cung cấp các hàm tiện ích trong header <cctype> như isalpha() để kiểm tra xem ký tự có phải là chữ cái không và tolower() để chuyển ký tự về chữ thường.
Hãy xem code được cập nhật:
#include <iostream>
#include <string>
#include <map>
#include <cctype>
int main() {
string s = "Lap trinh C++ that thu vi va huu ich!";
map<char, int> tanSuat;
cout << "--- Dang dem tan suat ky tu (chu cai, khong phan biet hoa thuong) ---" << endl;
for (char c : s) {
if (isalpha(static_cast<unsigned char>(c))) {
char lc = tolower(static_cast<unsigned char>(c));
tanSuat[lc]++;
}
}
cout << "--- Ket qua tan suat chu cai (khong phan biet hoa thuong) ---" << endl;
for (const auto& p : tanSuat) {
cout << "Ky tu '" << p.first << "': " << p.second << " lan" << endl;
}
cout << "------------------------------------------------------------" << endl;
return 0;
}
Output:
--- Dang dem tan suat ky tu (chu cai, khong phan biet hoa thuong) ---
--- Ket qua tan suat chu cai (khong phan biet hoa thuong) ---
Ky tu 'a': 3 lan
Ky tu 'c': 2 lan
Ky tu 'e': 1 lan
Ky tu 'h': 2 lan
Ky tu 'i': 3 lan
Ky tu 'l': 1 lan
Ky tu 'm': 1 lan
Ky tu 'n': 1 lan
Ky tu 'p': 1 lan
Ky tu 'r': 1 lan
Ky tu 't': 4 lan
Ky tu 'u': 2 lan
Ky tu 'v': 1 lan
Ky tu 'x': 1 lan
------------------------------------------------------------Điểm mới trong code:
- Include
<cctype>. - Trong vòng lặp:
isalpha(static_cast<unsigned char>(c)): Kiểm tra xemccó phải là ký tự chữ cái không. Việc ép kiểu sangunsigned charlà cần thiết cho các hàm xử lý ký tự trong<cctype>để tránh các vấn đề tiềm ẩn với giá trị ký tự âm (đặc biệt với các bộ mã hóa ký tự mở rộng).char lc = tolower(static_cast<unsigned char>(c));: Nếu là chữ cái, chuyển nó về chữ thường và lưu vàolc.tanSuat[lc]++;: Sử dụng ký tự chữ thường (lc) làm key để đếm. Điều này đảm bảo rằng 'A' và 'a' đều được tính vào cùng một key 'a' trong map.
- Vòng lặp in kết quả giờ đây sẽ chỉ in ra các ký tự chữ thường có tần suất > 0.
Kết quả của code này sẽ chỉ hiển thị tần suất của các chữ cái 'a' đến 'z', tổng hợp cả chữ hoa và chữ thường từ chuỗi gốc.
Sử dụng unordered_map: Khi tốc độ là ưu tiên
Như đã đề cập, unordered_map là một lựa chọn khác. Nó thường nhanh hơn map trong các thao tác chèn, xóa và truy cập (trung bình) vì nó sử dụng kỹ thuật băm (hashing). Tuy nhiên, nó không đảm bảo thứ tự của các phần tử khi duyệt.
Nếu thứ tự in ra không quan trọng và bạn đang xử lý chuỗi rất dài, unordered_map có thể là lựa chọn tốt hơn về mặt hiệu suất.
Việc chuyển đổi từ map sang unordered_map trong trường hợp này là cực kỳ đơn giản: chỉ cần thay thế map bằng unordered_map và include header tương ứng <unordered_map>. Logic đếm vẫn giữ nguyên.
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
string s = "Mot chuoi dai hon de kiem tra toc do unordered_map neu can!";
unordered_map<char, int> tanSuat;
for (char c : s) {
tanSuat[c]++;
}
cout << "--- Tan suat ky tu trong chuoi (su dung unordered_map) ---" << endl;
for (const auto& p : tanSuat) {
cout << "Ky tu '" << p.first << "': " << p.second << " lan" << endl;
}
cout << "----------------------------------------------------------" << endl;
return 0;
}
Output (có thể khác nhau tùy lần chạy):
--- Tan suat ky tu trong chuoi (su dung unordered_map) ---
Ky tu 'e': 6 lan
Ky tu 'n': 3 lan
Ky tu ' ': 9 lan
Ky tu 'u': 3 lan
Ky tu 'a': 4 lan
Ky tu 'l': 1 lan
Ky tu 'c': 3 lan
Ky tu 'k': 1 lan
Ky tu 'h': 3 lan
Ky tu 'd': 3 lan
Ky tu 'o': 7 lan
Ky tu 'i': 2 lan
Ky tu 'r': 2 lan
Ky tu 'p': 1 lan
Ky tu 't': 3 lan
Ky tu 'f': 1 lan
Ky tu '!': 1 lan
Ky tu 'm': 2 lan
Ky tu 'M': 1 lan
----------------------------------------------------------Code này hoàn toàn giống với phiên bản map ngoại trừ việc sử dụng unordered_map. Kết quả in ra sẽ có cùng các cặp ký tự-tần suất, nhưng thứ tự của chúng có thể khác nhau mỗi lần chạy hoặc khác với thứ tự bảng chữ cái.
Tóm tắt các kỹ thuật đã sử dụng
Qua bài viết này, chúng ta đã áp dụng và làm quen với một số khái niệm và kỹ thuật quan trọng trong C++:
string: Làm việc với chuỗi văn bản.map: Cấu trúc dữ liệu key-value, tự động sắp xếp theo key, rất phù hợp cho bài toán đếm tần suất khi cần kết quả có thứ tự.unordered_map: Cấu trúc dữ liệu key-value dựa trên băm, thường nhanh hơnmapnhưng không đảm bảo thứ tự.- Range-based for loop: Cú pháp hiện đại (từ C++11) giúp duyệt qua các container như
string,map,vector, ... một cách gọn gàng. - Truy cập/Chèn vào map bằng
[]: Cách tiện lợi để tăng giá trị đếm, map sẽ tự động khởi tạo key nếu chưa tồn tại. isalphavàtolower: Các hàm tiện ích từ<cctype>giúp xử lý các yêu cầu về phân biệt hoa thường và lọc ký tự.- Ép kiểu
static_cast<unsigned char>: Kỹ thuật cần thiết khi làm việc với các hàm xử lý ký tự để đảm bảo tính đúng đắn. - Duyệt qua map: Cách lặp qua các cặp key-value để truy cập và in kết quả.
Bài toán tần suất ký tự là một ví dụ tuyệt vời để thực hành sử dụng map hoặc unordered_map trong C++. Nắm vững cách sử dụng các cấu trúc dữ liệu này cho các bài toán đếm và thống kê sẽ rất hữu ích cho bạn sau này.
Bài tập ví dụ: C++ Bài 18.B1: Độ hòa tan của đường
Độ hòa tan của đường
FullHouse Dev đang nghiên cứu về độ hòa tan của đường trong nước. Họ phát hiện ra rằng khi nhiệt độ tăng lên 1 độ, độ hòa tan của đường trong nước tăng thêm B g/100 mL.
FullHouse Dev tiến hành một thí nghiệm để kiểm tra xem có thể hòa tan được bao nhiêu đường (tính bằng g) khi ban đầu có 1 lít nước ở nhiệt độ X độ và độ hòa tan của đường ở nhiệt độ này là A g/100 mL. Họ không muốn mất nước nên chỉ có thể tăng nhiệt độ tối đa lên 100 độ.
Giả sử không có sự mất nước trong quá trình này, hãy tìm lượng đường tối đa (tính bằng g) có thể hòa tan trong 1 lít nước trong điều kiện đã cho.
INPUT FORMAT
- Dòng đầu tiên chứa số nguyên T — số lượng bộ test.
- Mỗi bộ test gồm một dòng chứa ba số nguyên X, A, B.
OUTPUT FORMAT
- Với mỗi bộ test, in ra một dòng duy nhất là câu trả lời cho bài toán.
CONSTRAINTS
- 1 ≤ T ≤ 1000
- 31 ≤ X ≤ 40
- 101 ≤ A ≤ 120
- 1 ≤ B ≤ 5
Ví dụ
Input
3
40 120 1
35 120 2
40 115 3Output
1800
2500
2950Giải thích:
Test 1: Vì độ hòa tan tăng theo nhiệt độ, độ hòa tan tối đa sẽ ở 100 độ, bằng 120 + (100 - 40) = 180 g/100 mL. Vậy với 1 lít nước, giá trị là 180 * 10 = 1800 g.
Test 2: Độ hòa tan tối đa ở 100 độ là 120 + (100 - 35) 2 = 250 g/100 mL. Với 1 lít nước, giá trị là 250 10 = 2500 g.
Test 3: (Giải thích tương tự) Tuyệt vời, đây là hướng dẫn giải bài tập C++ này theo yêu cầu:
1. Phân tích bài toán:
- Bạn được cho nhiệt độ ban đầu (X), độ hòa tan ở nhiệt độ đó (A g/100mL), và lượng tăng độ hòa tan khi nhiệt độ tăng 1 độ (B g/100mL).
- Bạn có 1 lít nước (tức là 1000 mL).
- Bạn có thể tăng nhiệt độ tối đa lên 100 độ C.
- Độ hòa tan tăng theo nhiệt độ (do B > 0), nên lượng đường tối đa hòa tan sẽ đạt được ở nhiệt độ cao nhất có thể sử dụng, tức là 100 độ C.
- Cần tính lượng đường tối đa có thể hòa tan trong 1 lít (1000 mL) nước.
2. Xác định các bước giải:
- Bước 1: Tính toán nhiệt độ tăng thêm từ nhiệt độ ban đầu (X) đến nhiệt độ tối đa (100 độ C).
- Bước 2: Tính toán tổng lượng tăng thêm của độ hòa tan do nhiệt độ tăng.
- Bước 3: Tính độ hòa tan tổng cộng ở nhiệt độ 100 độ C (độ hòa tan ban đầu cộng với lượng tăng thêm). Lưu ý độ hòa tan này vẫn tính trên 100 mL nước.
- Bước 4: Chuyển đổi độ hòa tan từ 100 mL sang 1000 mL (1 lít) để có được lượng đường tối đa hòa tan trong 1 lít nước.
3. Công thức tính toán:
- Nhiệt độ tăng thêm:
Delta_T = 100 - X(độ C). - Lượng tăng độ hòa tan trên 100 mL:
Tang_do_hoa_tan_tren_100mL = Delta_T * B(g/100mL). - Độ hòa tan ở 100 độ C trên 100 mL:
Do_hoa_tan_100C_tren_100mL = A + Tang_do_hoa_tan_tren_100mL(g/100mL). - Lượng đường tối đa hòa tan trong 1 lít (1000 mL):
Luong_duong_toi_da = Do_hoa_tan_100C_tren_100mL * (1000 / 100)(g). - Rút gọn công thức cuối cùng:
Luong_duong_toi_da = (A + (100 - X) * B) * 10(g).
4. Cấu trúc chương trình C++:
- Bạn cần đọc số lượng bộ test
T. - Sử dụng một vòng lặp (ví dụ
whilehoặcfor) để xử lý từng bộ testTlần. - Bên trong vòng lặp, đọc ba số nguyên
X,A, vàBcho mỗi bộ test. - Áp dụng công thức
(A + (100 - X) * B) * 10để tính kết quả. - In kết quả cho mỗi bộ test, theo sau là ký tự xuống dòng.
- Sử dụng thư viện
iostreamcho việc nhập/xuất (cin,cout). - Để chương trình chạy nhanh hơn (quan trọng với nhiều bộ test), bạn có thể thêm
ios_base::sync_with_stdio(false); cin.tie(NULL);ở đầu hàmmain.
5. Gợi ý về kiểu dữ liệu:
- Các biến
T,X,A,Blà số nguyên. - Kết quả tính toán
(A + (100 - X) * B) * 10cũng sẽ là số nguyên. Kiểuinttrong C++ là đủ để chứa kết quả này dựa trên các ràng buộc đã cho.
Hướng dẫn chi tiết (không phải code hoàn chỉnh):
#include <iostream>
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int x, a, b;
cin >> x >> a >> b;
int kq = (a + (100 - x) * b) * 10;
cout << kq << endl;
}
return 0;
}
Output (với Input mẫu):
1800
2500
2950
Comments