Bài 12.4: Bài tập thực hành mảng 1 chiều nâng cao trong C++

Chào mừng các bạn quay trở lại với series blog về C++ của FullhouseDev!

Chúng ta đã cùng nhau tìm hiểu về mảng một chiều, cách khai báo, truy cập và thực hiện các thao tác cơ bản như nhập, xuất. Mảng là một cấu trúc dữ liệu cực kỳ phổ biến và quyền năng, là nền tảng cho rất nhiều thuật toán và cấu trúc dữ liệu phức tạp hơn.

Tuy nhiên, để thực sự làm chủ mảng, chúng ta cần đi sâu vào các bài tập thực hành mang tính nâng cao hơn một chút, vượt ra ngoài những thao tác đơn giản. "Nâng cao" ở đây không có nghĩa là quá khó, mà là áp dụng tư duy giải thuật và sử dụng các công cụ hiệu đại của C++ (như thư viện chuẩn <algorithm> hay <numeric>) để xử lý các vấn đề thường gặp.

Trong bài viết này, chúng ta sẽ cùng nhau thực hành một số bài toán điển hình với mảng một chiều, sử dụng C++ hiện đại với sự trợ giúp của vector (một container linh hoạt hơn mảng C-style truyền thống, rất phổ biến trong C++ hiện đại và thường được sử dụng thay thế cho mảng) và các hàm tiện ích trong thư viện chuẩn. Điều này không chỉ giúp code của chúng ta ngắn gọn và dễ đọc hơn mà còn hiệu quả và ít lỗi hơn.

Hãy cùng bắt tay vào thực hành nào!

Chúng ta sẽ sử dụng vector để làm việc với mảng một chiều trong các ví dụ này. Nếu bạn chưa quen, hãy xem vector như một "mảng linh hoạt" có thể tự điều chỉnh kích thước. Các khái niệm về chỉ số (index) và truy cập phần tử vẫn tương tự như mảng C-style.

#include <iostream>
#include <vector>
#include <numeric> // Cho accumulate, count
#include <algorithm> // Cho find, max_element, min_element, reverse, sort

// Sử dụng namespace std để code ngắn gọn hơn
using namespace std;

// Hàm hỗ trợ in vector
void print_vector(const vector<int>& arr) {
    cout << "[";
    for (size_t i = 0; i < arr.size(); ++i) {
        cout << arr[i] << (i == arr.size() - 1 ? "" : ", ");
    }
    cout << "]" << endl;
}

int main() {
    // Khai báo và khởi tạo một số vector mẫu để thực hành
    vector<int> data1 = {1, 5, 3, 8, 2, 5, 9, 5, 4, 6};
    vector<int> data2 = {-2, 7, 0, -5, 10, 3, -8};
    vector<int> data3 = {10, 20, 30, 40, 50};
    vector<int> data4 = {5, 5, 5, 5, 5};
    vector<int> empty_data; // Vector rỗng

    cout << "--- Bat dau cac bai tap thuc hanh ---" << endl;

    // --- Các bài tập ---

    return 0;
}

Bài tập 1: Tìm tất cả các vị trí xuất hiện của một phần tử

Bài toán: Cho một mảng và một giá trị x, tìm tất cả các chỉ số (index) trong mảng mà phần tử tại đó có giá trị bằng x.

Đây là một biến thể của bài toán tìm kiếm cơ bản. Thay vì chỉ tìm vị trí đầu tiên, chúng ta cần tìm tất cả các vị trí.

    // --- Bài tập 1: Tìm tất cả các vị trí xuất hiện ---
    cout << "\n## Bai tap 1: Tim tat ca cac vi tri xuat hien" << endl;
    int target_value = 5;
    vector<int> indices; // Vector để lưu các chỉ số tìm được

    cout << "Vector: ";
    print_vector(data1);
    cout << "Tim cac vi tri cua gia tri: " << target_value << endl;

    for (size_t i = 0; i < data1.size(); ++i) {
        if (data1[i] == target_value) {
            indices.push_back(i); // Nếu tìm thấy, thêm chỉ số vào vector indices
        }
    }

    cout << "Cac vi tri tim thay: ";
    print_vector(indices); // In ra vector chứa các chỉ số

    // Ví dụ khác với giá trị không tồn tại
    target_value = 100;
    indices.clear(); // Xóa nội dung cũ
    cout << "\nVector: ";
    print_vector(data1);
    cout << "Tim cac vi tri cua gia tri: " << target_value << endl;
    for (size_t i = 0; i < data1.size(); ++i) {
        if (data1[i] == target_value) {
            indices.push_back(i);
        }
    }
     cout << "Cac vi tri tim thay: ";
    print_vector(indices); // Vector rỗng nếu không tìm thấy

    cout << "--------------------" << endl;

Giải thích: Chúng ta duyệt qua từng phần tử của vector data1 bằng một vòng lặp for thông thường, sử dụng chỉ số i. Tại mỗi chỉ số, chúng ta kiểm tra xem data1[i] có bằng target_value hay không. Nếu có, chúng ta thêm chỉ số i vào vector indices bằng phương thức push_back(). Cuối cùng, chúng ta in nội dung của indices để biết các vị trí đã tìm thấy. Nếu không tìm thấy giá trị nào, vector indices sẽ vẫn rỗng.

Bài tập 2: Tìm phần tử lớn nhất, nhỏ nhất và vị trí của chúng

Bài toán: Tìm giá trị lớn nhất và nhỏ nhất trong mảng, cùng với vị trí (chỉ số) đầu tiên mà chúng xuất hiện.

Bài toán này là bài toán kinh điển khi làm việc với mảng. Chúng ta có thể làm điều này một cách thủ công hoặc sử dụng các hàm sẵn có trong C++. Với mục tiêu "nâng cao", chúng ta sẽ xem xét cách sử dụng thư viện chuẩn.

    // --- Bài tập 2: Tìm min/max và vị trí ---
    cout << "\n## Bai tap 2: Tim phan tu lon nhat, nho nhat va vi tri" << endl;

    if (!data2.empty()) { // Chỉ thực hiện nếu vector không rỗng
        cout << "Vector: ";
        print_vector(data2);

        // Tìm phần tử lớn nhất và vị trí
        auto max_it = max_element(data2.begin(), data2.end()); // max_element trả về iterator đến phần tử lớn nhất
        int max_val = *max_it; // Lấy giá trị của phần tử lớn nhất
        // Tính chỉ số bằng cách đo khoảng cách từ begin() đến iterator tìm được
        int max_index = distance(data2.begin(), max_it);

        cout << "Phan tu lon nhat: " << max_val << " tai vi tri (dau tien): " << max_index << endl;

        // Tìm phần tử nhỏ nhất và vị trí
        auto min_it = min_element(data2.begin(), data2.end()); // min_element trả về iterator đến phần tử nhỏ nhất
        int min_val = *min_it; // Lấy giá trị của phần tử nhỏ nhất
        // Tính chỉ số
        int min_index = distance(data2.begin(), min_it);

        cout << "Phan tu nho nhat: " << min_val << " tai vi tri (dau tien): " << min_index << endl;

    } else {
        cout << "Vector rong, khong tim duoc min/max." << endl;
    }

    cout << "--------------------" << endl;

Giải thích: Thay vì viết vòng lặp thủ công để theo dõi min/max, chúng ta sử dụng hai hàm tiện ích từ thư viện <algorithm>: max_element() và min_element(). Các hàm này nhận vào hai iterator (ở đây là data2.begin() và data2.end() đại diện cho toàn bộ vector) và trả về một iterator trỏ đến phần tử lớn nhất hoặc nhỏ nhất đầu tiên tìm được trong phạm vi đó.

*max_it (hoặc *min_it) dùng để lấy giá trị thực sự tại vị trí mà iterator trỏ tới.
Hàm distance(data2.begin(), max_it) (hoặc min_it) từ thư viện <iterator> (thường được include sẵn khi dùng <vector> hoặc <algorithm>) dùng để tính khoảng cách từ iterator bắt đầu (data2.begin()) đến iterator mà max_element (hoặc min_element) trả về. Khoảng cách này chính là chỉ số của phần tử đó trong vector.
Chúng ta cũng thêm kiểm tra !data2.empty() để đảm bảo vector không rỗng trước khi thực hiện tìm kiếm, tránh lỗi.

Bài tập 3: Tính tổng các phần tử thỏa mãn một điều kiện

Bài toán: Tính tổng các phần tử trong mảng mà giá trị của chúng thỏa mãn một điều kiện nhất định (ví dụ: tổng các số dương, tổng các số chẵn, tổng các số lớn hơn 10, v.v.).

Bài toán này giúp rèn luyện khả năng kết hợp duyệt mảng với kiểm tra điều kiện. Chúng ta có thể làm điều này bằng vòng lặp for, hoặc sử dụng các hàm tổng hợp mạnh mẽ hơn.

    // --- Bài tập 3: Tính tổng các phần tử thỏa man dieu kien ---
    cout << "\n## Bai tap 3: Tinh tong cac phan tu thoa man dieu kien" << endl;
    cout << "Vector: ";
    print_vector(data2);

    // Ví dụ 1: Tính tổng các số dương
    long long sum_positives = 0; // Sử dụng long long để tránh tràn số nếu tổng lớn
    for (int val : data2) { // Sử dụng range-based for loop cho code gọn gàng
        if (val > 0) {
            sum_positives += val;
        }
    }
    cout << "Tong cac so duong trong vector: " << sum_positives << endl;

    // Ví dụ 2: Tính tổng các số chẵn - sử dụng accumulate với lambda
    // accumulate(iterator_bat_dau, iterator_ket_thuc, gia_tri_khoi_tao, ham_tuy_chinh)
    long long sum_evens = accumulate(data2.begin(), data2.end(), 0LL, // 0LL la gia tri khoi tao kieu long long
                                    [](long long current_sum, int val){ // Lambda function
                                        if (val % 2 == 0) {
                                            return current_sum + val; // Neu la so chan thi cong vao tong hien tai
                                        } else {
                                            return current_sum; // Neu khong thi giu nguyen tong hien tai
                                        }
                                    });
    cout << "Tong cac so chan trong vector: " << sum_evens << endl;

    cout << "--------------------" << endl;

Giải thích:

Ví dụ 1 (Vòng lặp for): Chúng ta sử dụng vòng lặp range-based for (for (int val : data2)) để duyệt qua từng phần tử val trong data2 một cách trực tiếp mà không cần dùng chỉ số. Nếu val lớn hơn 0, chúng ta cộng nó vào sum_positives.
Ví dụ 2 (accumulate): Đây là cách tiếp cận nâng cao hơn sử dụng hàm accumulate() từ thư viện <numeric>. Hàm này dùng để tính tổng (hoặc một phép toán kết hợp khác) trên một dãy các phần tử.
- data2.begin(), data2.end(): Phạm vi các phần tử cần xử lý.
- 0LL: Giá trị khởi tạo ban đầu cho tổng (kiểu long long).
- [](long long current_sum, int val){ ... }: Đây là một lambda function (hàm ẩn danh). Nó được gọi cho mỗi phần tử trong phạm vi. Nó nhận vào current_sum (tổng tính được cho đến thời điểm hiện tại) và val (phần tử hiện tại). Logic bên trong lambda kiểm tra nếu val là số chẵn (val % 2 == 0), nó trả về current_sum + val. Nếu không, nó chỉ trả về current_sum (không cộng val vào). accumulate sẽ lặp lại quá trình này cho đến hết vector và trả về giá trị cuối cùng của current_sum.

Cách sử dụng accumulate với lambda thể hiện sự mạnh mẽ và linh hoạt của thư viện chuẩn C++ trong việc xử lý mảng/vector.

Bài tập 4: Đếm số lần xuất hiện của một phần tử

Bài toán: Đếm xem một giá trị x xuất hiện bao nhiêu lần trong mảng.

Bài toán này tương tự bài tìm vị trí, nhưng thay vì lưu các vị trí, chúng ta chỉ cần một bộ đếm.

    // --- Bài tập 4: Dem so lan xuat hien ---
    cout << "\n## Bai tap 4: Dem so lan xuat hien cua mot phan tu" << endl;
    cout << "Vector: ";
    print_vector(data1);

    int value_to_count = 5;

    // Cách 1: Dùng vòng lặp
    int count_loop = 0;
    for (int val : data1) {
        if (val == value_to_count) {
            count_loop++;
        }
    }
    cout << "So lan xuat hien cua " << value_to_count << " (dung loop): " << count_loop << endl;

    // Cách 2: Dùng count
    // count(iterator_bat_dau, iterator_ket_thuc, gia_tri_can_dem)
    int count_stl = count(data1.begin(), data1.end(), value_to_count);
    cout << "So lan xuat hien cua " << value_to_count << " (dung count): " << count_stl << endl;

    cout << "--------------------" << endl;

Giải thích:

Cách 1 (Vòng lặp): Đây là cách làm trực tiếp, duyệt qua từng phần tử và tăng biến đếm nếu phần tử đó bằng giá trị cần đếm.
Cách 2 (count): Thư viện <algorithm> cung cấp hàm count(). Hàm này nhận vào phạm vi (data1.begin(), data1.end()) và giá trị cần đếm (value_to_count). Nó sẽ tự động duyệt qua phạm vi và trả về số lần giá trị đó xuất hiện. Cách này ngắn gọn và thể hiện việc tận dụng thư viện chuẩn, rất được khuyến khích trong C++.

Bài tập 5: Đảo ngược mảng

Bài toán: Đảo ngược thứ tự các phần tử trong mảng (phần tử đầu thành cuối, cuối thành đầu, v.v.).

Bài toán này yêu cầu thay đổi vị trí của các phần tử. Có thể làm bằng cách tạo mảng mới hoặc đảo chỗ trực tiếp trong mảng gốc.

    // --- Bài tập 5: Dao nguoc mang ---
    cout << "\n## Bai tap 5: Dao nguoc mang" << endl;
    vector<int> original_data = {1, 2, 3, 4, 5, 6};
    cout << "Vector goc: ";
    print_vector(original_data);

    // Cách 1: Tao vector moi va copy nguoc
    vector<int> reversed_data_new;
    for (int i = original_data.size() - 1; i >= 0; --i) {
        reversed_data_new.push_back(original_data[i]);
    }
    cout << "Vector dao nguoc (tao moi): ";
    print_vector(reversed_data_new);

    // Cách 2: Dao nguoc tai cho (in-place) dung reverse
    // reverse(iterator_bat_dau, iterator_ket_thuc)
    vector<int> data_to_reverse = original_data; // Tao ban sao de dao nguoc tai cho
    reverse(data_to_reverse.begin(), data_to_reverse.end());
    cout << "Vector dao nguoc (tai cho dung reverse): ";
    print_vector(data_to_reverse);


    cout << "--------------------" << endl;

Giải thích:

Cách 1 (Tạo vector mới): Chúng ta tạo một vector reversed_data_new rỗng. Sau đó, duyệt qua original_data từ cuối về đầu (sử dụng vòng lặp for với chỉ số giảm dần từ size() - 1 về 0). Mỗi phần tử duyệt được từ original_data[i], chúng ta thêm vào cuối của reversed_data_new.
Cách 2 (reverse): Thư viện <algorithm> cung cấp hàm reverse(). Hàm này nhận vào phạm vi (data_to_reverse.begin(), data_to_reverse.end()) và thực hiện đảo ngược thứ tự các phần tử trong chính phạm vi đó (hay còn gọi là đảo ngược "tại chỗ" - in-place), không tạo ra vector mới. Đây là cách ngắn gọn và hiệu quả hơn cho bài toán này.

Comments

There are no comments at the moment.