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>

using namespace std;

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

    vector<int> a(n);

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

    cout << "\nCac phan tu trong mang da nhap la:\n";
    for (int i = 0; i < n; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

Output:

Nhap so luong phan tu: 3
Nhap 3 so nguyen:
Phan tu thu 1: 10
Phan tu thu 2: 20
Phan tu thu 3: 30

Cac phan tu trong mang da nhap la:
10 20 30

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>

using namespace std;

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

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

    vector<int> a(n);

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

    // Cach 1: Duyet mang thu cong
    int maxV = a[0];
    int minV = a[0];

    for (int i = 1; i < n; ++i) {
        if (a[i] > maxV) {
            maxV = a[i];
        }
        if (a[i] < minV) {
            minV = a[i];
        }
    }

    cout << "Gia tri lon nhat trong mang: " << maxV << endl;
    cout << "Gia tri nho nhat trong mang: " << minV << endl;

    // Cach 2: Su dung thu vien <algorithm>
    // auto min_it = min_element(a.begin(), a.end());
    // auto max_it = max_element(a.begin(), a.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;
}

Output:

Nhap so luong phan tu: 5
Nhap 5 so nguyen:
10
5
80
-2
45
Gia tri lon nhat trong mang: 80
Gia tri nho nhat trong mang: -2

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>

using namespace std;

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

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

    vector<int> a(n);

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

    // Cach 1: Duyet mang thu cong
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += a[i];
    }

    double tb = static_cast<double>(sum) / n;

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

    // Cach 2: Su dung thu vien <numeric>
    // long long sum_std = accumulate(a.begin(), a.end(), 0LL);
    // double tb_std = static_cast<double>(sum_std) / n;
    // cout << "(Bang cach khac) Tong: " << sum_std << endl;
    // cout << "(Bang cach khac) Trung binh: " << tb_std << endl;

    return 0;
}

Output:

Nhap so luong phan tu: 4
Nhap 4 so nguyen:
1
2
3
4
Tong cac phan tu: 10
Trung binh cong: 2.5

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>

using namespace std;

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

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

    vector<int> a(n);

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

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

    // Cach 1: Duyet mang thu cong
    int idx = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] == x) {
            idx = i;
            break;
        }
    }

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

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

    return 0;
}

Output (Tìm thấy):

Nhap so luong phan tu: 5
Nhap 5 so nguyen:
10
20
30
40
50
Nhap gia tri can tim: 30
Gia tri 30 duoc tim thay tai chi so: 2

Output (Không tìm thấy):

Nhap so luong phan tu: 3
Nhap 3 so nguyen:
1
2
3
Nhap gia tri can tim: 5
Gia tri 5 khong ton tai trong mang.

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>

using namespace std;

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

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

    vector<int> a(n);

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

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

    // Cach 1: Duyet mang thu cong
    int dem = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == x) {
            dem++;
        }
    }

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

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

    return 0;
}

Output:

Nhap so luong phan tu: 7
Nhap 7 so nguyen:
1
2
1
3
1
4
1
Nhap gia tri can dem so lan xuat hien: 1
Gia tri 1 xuat hien 4 lan trong mang.

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>

using namespace std;

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

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

    vector<int> a(n);

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

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

    // Cach 1: Dao nguoc thu cong
    int l = 0;
    int r = n - 1;

    while (l < r) {
        int tmp = a[l];
        a[l] = a[r];
        a[r] = tmp;

        l++;
        r--;
    }

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

    // Cach 2: Su dung thu vien <algorithm>
    // reverse(a.begin(), a.end()); // Neu muon dao nguoc mot mang khac hoac reset mang a
    // (can nhap lai mang a hoac dung mang moi)

    return 0;
}

Output:

Nhap so luong phan tu: 5
Nhap 5 so nguyen:
1
2
3
4
5
Mang truoc khi dao nguoc: 1 2 3 4 5 
Mang sau khi dao nguoc (Cach 1): 5 4 3 2 1

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>

using namespace std;

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

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

    vector<int> a(n);

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

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

    sort(a.begin(), a.end());

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

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

    return 0;
}

Output:

Nhap so luong phan tu: 6
Nhap 6 so nguyen:
5
2
9
1
7
3
Mang truoc khi sap xep: 5 2 9 1 7 3 
Mang sau khi sap xep (tang dan): 1 2 3 5 7 9

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.