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ư map như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:

  1. Đọc chuỗi input.
  2. Tạo một map<char, int> trống để lưu tần suất.
  3. Duyệt qua từng ký tự trong chuỗi input.
  4. 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], map sẽ 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ủa map và unordered_map!
  5. 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.
  6. 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> // Để sử dụng cout và endl
#include <string>   // Để sử dụng string
#include <map>      // Để sử dụng map
#include <limits>   // Chỉ để tạm dừng màn hình, không liên quan logic chính

int main() {
    // Chuỗi đầu vào
    string text = "Lap trinh C++ that thu vi va huu ich!";

    // Khai báo một map để lưu tần suất.
    // key là char (ký tự), value là int (số lần xuất hiện).
    map<char, int> frequency;

    // Duyệt qua từng ký tự trong chuỗi sử dụng range-based for loop (C++11 trở lên)
    // Đây là cách hiện đại và gọn gàng để lặp qua các phần tử của container
    for (char c : text) {
        // Với mỗi ký tự 'c', chúng ta truy cập phần tử tương ứng trong map.
        // Nếu 'c' chưa là key trong map, nó sẽ được thêm vào với giá trị mặc định là 0.
        // Sau đó, toán tử ++ sẽ tăng giá trị lên 1.
        frequency[c]++;
    }

    // In kết quả
    cout << "--- Tan suat ky tu trong chuoi (phan biet hoa thuong) ---" << endl;
    // Duyệt qua map. map lưu các cặp key-value (pair).
    // auto& pair có kiểu là pair<const char, int>
    for (const auto& pair : frequency) {
        // pair.first là ký tự (key), pair.second là số lần xuất hiện (value)
        // Chúng ta chỉ in ra các ký tự có tần suất > 0 (mặc dù map chỉ chứa các ký tự đã xuất hiện)
        if (pair.second > 0) {
            cout << "Ky tu '" << pair.first << "': " << pair.second << " lan" << endl;
        }
    }
    cout << "------------------------------------------------------" << endl;


    // Giữ màn hình console mở cho đến khi người dùng nhấn Enter (tùy chọn)
    // cout << "Nhan Enter de ket thuc...";
    // cin.ignore(numeric_limits<streamsize>::max(), '\n');
    // cin.get(); // Đọc ký tự Enter

    return 0; // Chương trình kết thúc thành công
}

Giải thích code:

  • Chúng ta include các header cần thiết: <iostream>, <string>, <map>.
  • Một string tên text được khai báo với dữ liệu đầu vào.
  • map<char, int> frequency; tạo một map trống.
  • Vòng lặp for (char c : text) là cách tiện lợi để duyệt qua mỗi ký tự trong chuỗi text. Biến c sẽ lần lượt nhận giá trị của từng ký tự.
  • frequency[c]++; là dòng code "ma thuật" chính. Khi ký tự c được dùng làm chỉ mục cho map frequency, nếu c chưa tồn tại làm key, map sẽ tạo một entry mới c -> 0. Sau đó, toán tử ++ tăng giá trị từ 0 lên 1. Nếu c đã 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& pair : frequency) duyệt qua từng cặp (key-value) trong map. pair.first là key (ký tự), pair.second là 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 text, 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:

  1. Kiểm tra xem ký tự hiện tại có phải là chữ cái không.
  2. 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> // Để sử dụng isalpha và tolower
#include <limits>

int main() {
    string text = "Lap trinh C++ that thu vi va huu ich!";
    map<char, int> frequency; // Map sẽ lưu trữ các ký tự chữ thường

    cout << "--- Dang dem tan suat ky tu (chu cai, khong phan biet hoa thuong) ---" << endl;

    // Duyệt qua từng ký tự trong chuỗi
    for (char c : text) {
        // isalpha kiểm tra xem 'c' có phải là ký tự chữ cái không ('a'-'z', 'A'-'Z')
        // Cần ép kiểu sang unsigned char vì một số hàm trong <cctype> mong đợi kiểu này
        if (isalpha(static_cast<unsigned char>(c))) {
            // Nếu là chữ cái, chuyển nó về chữ thường
            char lower_c = tolower(static_cast<unsigned char>(c));
            // Tăng số đếm cho ký tự chữ thường này trong map
            frequency[lower_c]++;
        }
        // Các ký tự không phải chữ cái (khoảng trắng, số, dấu câu...) sẽ bị bỏ qua
    }

    // In kết quả
    cout << "--- Ket qua tan suat chu cai (khong phan biet hoa thuong) ---" << endl;
    for (const auto& pair : frequency) {
         // pair.first bây giờ chỉ chứa các ký tự chữ thường đã được đếm
         cout << "Ky tu '" << pair.first << "': " << pair.second << " lan" << endl;
    }
    cout << "------------------------------------------------------------" << endl;


    // Giữ màn hình console mở (tùy chọn)
    // cout << "Nhan Enter de ket thuc...";
    // cin.ignore(numeric_limits<streamsize>::max(), '\n');
    // cin.get();

    return 0;
}

Điểm mới trong code:

  • Include <cctype>.
  • Trong vòng lặp:
    • isalpha(static_cast<unsigned char>(c)): Kiểm tra xem c có phải là ký tự chữ cái không. Việc ép kiểu sang unsigned char là 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 lower_c = tolower(static_cast<unsigned char>(c));: Nếu là chữ cái, chuyển nó về chữ thường và lưu vào lower_c.
    • frequency[lower_c]++;: Sử dụng ký tự chữ thường (lower_c) 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> // Sử dụng unordered_map thay vì map
#include <limits>

int main() {
    string text = "Mot chuoi dai hon de kiem tra toc do unordered_map neu can!";

    // Khai báo một unordered_map
    unordered_map<char, int> frequency;

    // Logic đếm vẫn tương tự
    for (char c : text) {
        frequency[c]++;
    }

    // In kết quả. Lưu ý: thứ tự in ra có thể không theo bảng chữ cái
    cout << "--- Tan suat ky tu trong chuoi (su dung unordered_map) ---" << endl;
    for (const auto& pair : frequency) {
         if (pair.second > 0) {
            cout << "Ky tu '" << pair.first << "': " << pair.second << " lan" << endl;
        }
    }
    cout << "----------------------------------------------------------" << endl;


    // Giữ màn hình console mở (tùy chọn)
    // cout << "Nhan Enter de ket thuc...";
    // cin.ignore(numeric_limits<streamsize>::max(), '\n');
    // cin.get();

    return 0;
}

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ơn map như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.
  • isalpha và 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 3

Output

1800
2500
2950
Giả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ụ while hoặc for) để xử lý từng bộ test T lần.
  • Bên trong vòng lặp, đọc ba số nguyên X, A, và B cho 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 iostream cho 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àm main.

5. Gợi ý về kiểu dữ liệu:

  • Các biến T, X, A, B là số nguyên.
  • Kết quả tính toán (A + (100 - X) * B) * 10 cũng sẽ là số nguyên. Kiểu int trong 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):

// Bắt đầu chương trình C++

// Bao gồm thư viện cần thiết cho nhập xuất
#include <iostream>

// Hàm main là điểm bắt đầu thực thi
int main() {
    // Tối ưu hóa tốc độ nhập xuất (tùy chọn nhưng nên dùng cho bài có nhiều test)
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);

    // Khai báo biến cho số lượng bộ test
    int T;

    // Đọc số lượng bộ test
    // cin >> T;

    // Vòng lặp xử lý từng bộ test
    // while (T--) {
        // Khai báo biến cho X, A, B
        int X, A, B;

        // Đọc giá trị của X, A, B
        // cin >> X >> A >> B;

        // Tính toán kết quả sử dụng công thức đã suy luận
        // int ket_qua = ... công thức của bạn ... ;

        // In kết quả và xuống dòng
        // cout << ket_qua << endl;
    // }

    // Trả về 0 để báo hiệu chương trình kết thúc thành công
    return 0;
}

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.