Bài 24.5: Bài tập thực hành ứng dụng mảng 1 chiều trong C++

Chào mừng bạn trở lại với chuỗi bài viết về C++ của FullhouseDev! Ở các bài trước, chúng ta đã cùng nhau tìm hiểu về khái niệm mảng một chiều (1D Array) trong C++, cách khai báo, khởi tạo và truy cập các phần tử của mảng. Mảng là một cấu trúc dữ liệu vô cùng quan trọng và được sử dụng rộng rãi trong lập trình để lưu trữ và xử lý các tập hợp dữ liệu có cùng kiểu.

Nắm vững lý thuyết là một chuyện, nhưng để thực sự thành thạo, chúng ta cần phải thực hành thật nhiều. Bài viết hôm nay sẽ tập trung vào việc áp dụng kiến thức về mảng một chiều thông qua các bài tập thực tế. Chúng ta sẽ cùng nhau giải quyết một số bài toán cơ bản nhưng rất phổ biến khi làm việc với mảng.

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

1. Nhập và Xuất các Phần tử của Mảng

Bài tập đầu tiên và cơ bản nhất là làm quen với việc đưa dữ liệu vào mảng và in dữ liệu từ mảng ra màn hình. Điều này giúp bạn nắm vững cách duyệt mảng bằng vòng lặp.

Yêu cầu: Nhập vào số nguyên n, sau đó nhập n số nguyên và lưu trữ chúng vào một mảng. Cuối cùng, in tất cả các phần tử của mảng đó ra màn hình.

Code C++:

#include <iostream>
#include <vector> // Sử dụng vector để linh hoạt hơn với kích thước mảng

int main() {
    int n;
    cout << "Nhap so luong phan tu (n): ";
    cin >> n;

    // Khai bao mảng (vector) co kich thuoc n
    vector<int> arr(n);

    cout << "Nhap " << n << " so nguyen:\n";
    // Vong lap de nhap cac phan tu vao mang
    for (int i = 0; i < n; ++i) {
        cout << "Phan tu thu " << i + 1 << ": ";
        cin >> arr[i]; // Nhap du lieu vao phan tu thu i
    }

    cout << "\nCac phan tu trong mang da nhap la:\n";
    // Vong lap de in cac phan tu trong mang
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " "; // In phan tu thu i
    }
    cout << endl; // Xuong dong ket thuc

    return 0;
}

Giải thích code:

Chúng ta sử dụng vector<int> arr(n); để tạo một mảng (vector) có kích thước n. vector linh hoạt hơn mảng C-style truyền thống vì kích thước có thể được xác định lúc chạy chương trình.
Vòng lặp for (int i = 0; i < n; ++i) được sử dụng để duyệt qua mảng từ chỉ số 0 đến n-1.
Trong vòng lặp nhập, cin >> arr[i]; đọc giá trị từ bàn phím và gán vào phần tử tại chỉ số i của mảng.
Trong vòng lặp xuất, cout << arr[i] << " "; in giá trị của phần tử tại chỉ số i ra màn hình, theo sau là một khoảng trắng để phân tách các phần tử.

2. Tìm Giá trị Lớn nhất và Nhỏ nhất trong Mảng

Đây là một bài toán kinh điển để rèn luyện kỹ năng duyệt mảng và so sánh giá trị.

Yêu cầu: Cho một mảng các số nguyên, tìm và in ra giá trị lớn nhất và nhỏ nhất trong mảng đó.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm> // Can su dung min_element va max_element

int main() {
    int n;
    cout << "Nhap so luong phan tu (n): ";
    cin >> n;

    if (n <= 0) {
        cout << "So luong phan tu khong hop le.\n";
        return 1;
    }

    vector<int> arr(n);

    cout << "Nhap " << n << " so nguyen:\n";
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    // Cach 1: Duyet mang thu cong
    int max_val = arr[0]; // Gia su phan tu dau tien la max
    int min_val = arr[0]; // Gia su phan tu dau tien la min

    for (int i = 1; i < n; ++i) { // Bat dau duyet tu phan tu thu 2
        if (arr[i] > max_val) {
            max_val = arr[i]; // Cap nhat max neu tim thay gia tri lon hon
        }
        if (arr[i] < min_val) {
            min_val = arr[i]; // Cap nhat min neu tim thay gia tri nho hon
        }
    }

    cout << "Gia tri lon nhat trong mang: " << max_val << endl;
    cout << "Gia tri nho nhat trong mang: " << min_val << endl;

    // Cach 2: Su dung thu vien <algorithm> (ngan gon hon)
    // auto min_it = min_element(arr.begin(), arr.end());
    // auto max_it = max_element(arr.begin(), arr.end());
    // cout << "(Bang cach khac) Gia tri lon nhat: " << *max_it << endl;
    // cout << "(Bang cach khac) Gia tri nho nhat: " << *min_it << endl;


    return 0;
}

Giải thích code:

Chúng ta khởi tạo max_val và min_val bằng giá trị của phần tử đầu tiên (arr[0]).
Vòng lặp bắt đầu từ chỉ số 1 (i = 1) vì phần tử 0 đã được dùng để khởi tạo.
Bên trong vòng lặp, chúng ta so sánh từng phần tử arr[i] với max_val và min_val hiện tại để cập nhật nếu cần.
Lưu ý: Thư viện <algorithm> cung cấp các hàm tiện ích như min_element và max_element giúp tìm phần tử nhỏ nhất/lớn nhất một cách ngắn gọn hơn rất nhiều (như trong phần code được comment), nhưng việc tự duyệt mảng như cách 1 giúp bạn hiểu rõ hơn về cách thuật toán hoạt động.

3. Tính Tổng và Trung bình cộng các Phần tử

Một ứng dụng phổ biến khác của mảng là tính toán các thống kê cơ bản trên dữ liệu.

Yêu cầu: Cho một mảng các số nguyên, tính tổng tất cả các phần tử và trung bình cộng của chúng.

Code C++:

#include <iostream>
#include <vector>
#include <numeric> // Can su dung accumulate

int main() {
    int n;
    cout << "Nhap so luong phan tu (n): ";
    cin >> n;

    if (n <= 0) {
        cout << "So luong phan tu khong hop le.\n";
        return 1;
    }

    vector<int> arr(n);

    cout << "Nhap " << n << " so nguyen:\n";
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    // Cach 1: Duyet mang thu cong
    long long sum = 0; // Su dung long long de tranh tran so neu tong lon
    for (int i = 0; i < n; ++i) {
        sum += arr[i]; // Cong don gia tri cua tung phan tu
    }

    double average = static_cast<double>(sum) / n; // Ep kieu sang double de tinh trung binh chinh xac

    cout << "Tong cac phan tu: " << sum << endl;
    cout << "Trung binh cong: " << average << endl;

    // Cach 2: Su dung thu vien <numeric> (ngan gon hon)
    // long long sum_std = accumulate(arr.begin(), arr.end(), 0LL); // 0LL la gia tri khoi tao cho long long
    // double average_std = static_cast<double>(sum_std) / n;
    // cout << "(Bang cach khac) Tong: " << sum_std << endl;
    // cout << "(Bang cach khac) Trung binh: " << average_std << endl;


    return 0;
}

Giải thích code:

Chúng ta sử dụng biến sum kiểu long long để đảm bảo có thể chứa được tổng của các số nguyên lớn mà không bị tràn số.
Vòng lặp duyệt qua mảng và cộng giá trị của từng phần tử vào biến sum.
Để tính trung bình, chúng ta lấy sum chia cho n. Việc ép kiểu static_cast<double>(sum) là cần thiết để kết quả phép chia là số thực, tránh trường hợp phép chia nguyên nếu cả sum và n đều là số nguyên.
Tương tự như bài tìm max/min, thư viện <numeric> có hàm accumulate giúp tính tổng ngắn gọn hơn (phần comment).

4. Tìm kiếm một Phần tử trong Mảng

Khi cần kiểm tra xem một giá trị có tồn tại trong mảng hay không, hoặc tìm vị trí của nó, chúng ta thực hiện tìm kiếm.

Yêu cầu: Cho một mảng các số nguyên và một giá trị x. Kiểm tra xem x có tồn tại trong mảng hay không. Nếu có, in ra chỉ số (vị trí) của nó (có thể là vị trí đầu tiên tìm thấy).

Code C++:

#include <iostream>
#include <vector>
#include <algorithm> // Can su dung find

int main() {
    int n;
    cout << "Nhap so luong phan tu (n): ";
    cin >> n;

    if (n <= 0) {
        cout << "So luong phan tu khong hop le.\n";
        return 1;
    }

    vector<int> arr(n);

    cout << "Nhap " << n << " so nguyen:\n";
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    int x;
    cout << "Nhap gia tri can tim kiem (x): ";
    cin >> x;

    // Cach 1: Duyet mang thu cong (Tim vi tri dau tien)
    int found_index = -1; // Mac dinh khong tim thay
    for (int i = 0; i < n; ++i) {
        if (arr[i] == x) {
            found_index = i; // Ghi lai chi so khi tim thay
            break; // Dung vong lap ngay khi tim thay phan tu dau tien
        }
    }

    if (found_index != -1) {
        cout << "Gia tri " << x << " duoc tim thay tai chi so: " << found_index << endl;
    } else {
        cout << "Gia tri " << x << " khong ton tai trong mang." << endl;
    }

    // Cach 2: Su dung thu vien <algorithm> (ngan gon hon)
    // auto it = find(arr.begin(), arr.end(), x);
    // if (it != arr.end()) {
    //     cout << "(Bang cach khac) Gia tri " << x << " duoc tim thay tai chi so: " << distance(arr.begin(), it) << endl;
    // } else {
    //     cout << "(Bang cach khac) Gia tri " << x << " khong ton tai trong mang." << endl;
    // }

    return 0;
}

Giải thích code:

Chúng ta sử dụng một biến found_index để lưu trữ chỉ số của phần tử tìm thấy. Khởi tạo nó bằng -1, một giá trị không hợp lệ cho chỉ số mảng, để biểu thị rằng chưa tìm thấy.
Vòng lặp duyệt qua mảng. Nếu arr[i] bằng với giá trị cần tìm x, chúng ta gán i vào found_index và sử dụng break để thoát khỏi vòng lặp ngay lập tức (vì chỉ cần tìm vị trí đầu tiên).
Sau vòng lặp, kiểm tra giá trị của found_index. Nếu nó vẫn là -1, nghĩa là không tìm thấy x. Nếu khác -1, đó chính là chỉ số của x trong mảng.
Thư viện <algorithm> cung cấp hàm find giúp thực hiện tìm kiếm ngắn gọn hơn (phần comment).

5. Đếm Số lần Xuất hiện của Phần tử

Bài toán này mở rộng từ bài tìm kiếm, thay vì chỉ kiểm tra sự tồn tại, chúng ta đếm tần suất xuất hiện.

Yêu cầu: Cho một mảng các số nguyên và một giá trị x. Đếm xem giá trị x xuất hiện bao nhiêu lần trong mảng.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm> // Can su dung count

int main() {
    int n;
    cout << "Nhap so luong phan tu (n): ";
    cin >> n;

    if (n <= 0) {
        cout << "So luong phan tu khong hop le.\n";
        return 1;
    }

    vector<int> arr(n);

    cout << "Nhap " << n << " so nguyen:\n";
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    int x;
    cout << "Nhap gia tri can dem so lan xuat hien (x): ";
    cin >> x;

    // Cach 1: Duyet mang thu cong
    int count = 0; // Bien dem so lan xuat hien
    for (int i = 0; i < n; ++i) {
        if (arr[i] == x) {
            count++; // Tang bien dem moi khi tim thay x
        }
    }

    cout << "Gia tri " << x << " xuat hien " << count << " lan trong mang." << endl;

    // Cach 2: Su dung thu vien <algorithm> (ngan gon hon)
    // int count_std = count(arr.begin(), arr.end(), x);
    // cout << "(Bang cach khac) Gia tri " << x << " xuat hien " << count_std << " lan trong mang." << endl;

    return 0;
}

Giải thích code:

Chúng ta sử dụng một biến count được khởi tạo bằng 0 để đếm số lần xuất hiện.
Vòng lặp duyệt qua toàn bộ mảng. Mỗi khi tìm thấy một phần tử arr[i] bằng với giá trị cần đếm x, chúng ta tăng biến count lên 1.
Sau khi duyệt hết mảng, giá trị cuối cùng của count chính là số lần x xuất hiện.
Thư viện <algorithm> cung cấp hàm count giúp thực hiện việc đếm này ngắn gọn hơn (phần comment).

6. Đảo ngược Mảng

Thay đổi thứ tự các phần tử trong mảng cũng là một thao tác phổ biến.

Yêu cầu: Cho một mảng các số nguyên, đảo ngược thứ tự các phần tử của mảng đó.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm> // Can su dung reverse

int main() {
    int n;
    cout << "Nhap so luong phan tu (n): ";
    cin >> n;

    if (n <= 0) {
        cout << "So luong phan tu khong hop le.\n";
        return 1;
    }

    vector<int> arr(n);

    cout << "Nhap " << n << " so nguyen:\n";
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    cout << "Mang truoc khi dao nguoc: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // Cach 1: Dao nguoc mang thu cong
    int left = 0; // Chi so ben trai bat dau
    int right = n - 1; // Chi so ben phai bat dau

    while (left < right) {
        // Hoan doi gia tri cua phan tu ben trai va ben phai
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;

        // Di chuyen chi so vao ben trong
        left++;
        right--;
    }

    cout << "Mang sau khi dao nguoc (Cach 1): ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // Cach 2: Su dung thu vien <algorithm> (ngan gon hon)
    // // Nhap lai mang hoac su dung mang khac de demo cach 2
    // // Vi cach 1 da thay doi mang arr
    // vector<int> arr2(n);
    // // ... nhap lai arr2 ...
    // reverse(arr2.begin(), arr2.end());
    // cout << "Mang sau khi dao nguoc (Cach 2): ";
    // for (int i = 0; i < n; ++i) {
    //     cout << arr2[i] << " ";
    // }
    // cout << endl;

    return 0;
}

Giải thích code:

Chúng ta sử dụng hai con trỏ (hoặc chỉ số), một bắt đầu từ đầu mảng (left = 0) và một bắt đầu từ cuối mảng (right = n - 1).
Vòng lặp while (left < right) tiếp tục miễn là con trỏ bên trái vẫn còn ở bên trái con trỏ bên phải.
Bên trong vòng lặp, chúng ta hoán đổi giá trị của phần tử tại chỉ số left với phần tử tại chỉ số right bằng cách sử dụng một biến tạm (temp).
Sau khi hoán đổi, chúng ta di chuyển con trỏ left tiến về phía trước (left++) và con trỏ right lùi về phía sau (right--).
Quá trình dừng lại khi left gặp hoặc vượt qua right, khi đó mảng đã được đảo ngược hoàn toàn.
Thư viện <algorithm> cung cấp hàm reverse giúp đảo ngược mảng ngắn gọn hơn (phần comment).

7. Sắp xếp Mảng

Sắp xếp là một trong những thao tác quan trọng nhất trong khoa học máy tính. Nó giúp tổ chức dữ liệu theo một trật tự nhất định (tăng dần hoặc giảm dần) để thuận tiện cho các xử lý sau này (ví dụ: tìm kiếm nhị phân).

Yêu cầu: Cho một mảng các số nguyên, sắp xếp các phần tử của mảng theo thứ tự tăng dần.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm> // Can su dung sort

int main() {
    int n;
    cout << "Nhap so luong phan tu (n): ";
    cin >> n;

    if (n <= 0) {
        cout << "So luong phan tu khong hop le.\n";
        return 1;
    }

    vector<int> arr(n);

    cout << "Nhap " << n << " so nguyen:\n";
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    cout << "Mang truoc khi sap xep: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // Su dung ham sort tu thu vien <algorithm> de sap xep
    sort(arr.begin(), arr.end());

    cout << "Mang sau khi sap xep (tang dan): ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // De sap xep giam dan, co the truyen them tham so greater<int>()
    // sort(arr.begin(), arr.end(), greater<int>());
    // cout << "Mang sau khi sap xep (giam dan): ";
    // for (int i = 0; i < n; ++i) {
    //     cout << arr[i] << " ";
    // }
    // cout << endl;


    return 0;
}

Giải thích code:

Thư viện <algorithm> trong C++ cung cấp hàm sort, một công cụ vô cùng mạnh mẽ và hiệu quả để sắp xếp mảng (hoặc các container khác).
Chúng ta chỉ cần gọi sort(arr.begin(), arr.end());. arr.begin() trả về một iterator trỏ đến phần tử đầu tiên, và arr.end() trả về một iterator trỏ sau phần tử cuối cùng. Hàm sort sẽ sắp xếp các phần tử trong phạm vi này theo thứ tự tăng dần mặc định.
Để sắp xếp giảm dần, bạn có thể thêm một tham số thứ ba là greater<int>() như trong phần comment.
Việc tự cài đặt các thuật toán sắp xếp (như Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort,...) là các bài tập tuyệt vời để hiểu sâu hơn về giải thuật, nhưng trong thực tế, bạn nên sử dụng sort vì nó đã được tối ưu hóa cao.

Comments

There are no comments at the moment.