Khóa học C++ từ cơ bản đến nâng cao

Bài 12.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 đến với bài thực hành quan trọng về mảng một chiều trong chuỗi bài học C++ của chúng ta! Sau khi đã nắm vững các khái niệm cơ bản về cách khai báo, truy cập và khởi tạo mảng, đây là lúc chúng ta áp dụng kiến thức đó vào các bài tập thực tế. Thực hành chính là cầu nối vững chắc giữa lý thuyết và khả năng giải quyết vấn đề thực tế trong lập trình.

Mảng một chiều là một trong những cấu trúc dữ liệu cơ bản nhất nhưng lại cực kỳ mạnh mẽ và được sử dụng rộng rãi. Việc thành thạo thao tác với mảng là nền tảng quan trọng cho việc học các cấu trúc dữ liệu phức tạp hơn sau này.

Bài tập 1: Nhập và Xuất mảng cơ bản

Yêu cầu bài toán: Viết chương trình C++ cho phép người dùng nhập vào số lượng phần tử 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 ra toàn bộ các phần tử của mảng vừa nhập.

Ý tưởng giải quyết: Chúng ta sẽ cần:

• Hỏi người dùng kích thước mảng.
• Khai báo một mảng (hoặc vector) với kích thước đó.
• Sử dụng vòng lặp for để đọc từng phần tử từ người dùng và gán vào mảng.
• Sử dụng một vòng lặp for khác để duyệt qua mảng và in từng phần tử ra màn hình.

Mã nguồn minh họa:

#include <iostream>
#include <vector> // Sử dụng vector để dễ dàng làm việc với kích thước động

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

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

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

    cout << "\nCac phan tu trong mang la:\n";
    // Vong lap xuat du lieu
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " "; // In phan tu tai chi so i
    }
    cout << endl; // Xuong dong cuoi cung

    return 0;
}

Giải thích code:

• Chúng ta bao gồm thư viện <iostream> cho nhập/xuất và <vector> để sử dụng vector. vector giống như mảng nhưng linh hoạt hơn về kích thước.
• cout << "Nhap so luong phan tu..." và cin >> n; để lấy kích thước mảng từ người dùng.
• vector<int> arr(n); khai báo một vector tên arr chứa các số nguyên và có kích thước là n.
• Vòng lặp for (int i = 0; i < n; ++i) đầu tiên chạy từ i = 0 đến n-1. Trong mỗi lần lặp, cin >> arr[i]; đọc một số nguyên từ người dùng và lưu vào phần tử thứ i của vector.
• Vòng lặp for thứ hai cũng chạy từ i = 0 đến n-1. Trong mỗi lần lặp, cout << arr[i] << " "; in ra phần tử thứ i của vector, theo sau là một khoảng trắng để các số cách nhau.
• endl; kết thúc dòng output cuối cùng.

Bài tập 2: Tính tổng và Trung bình cộng các phần tử

Yêu cầu bài toán: Cho một mảng các số nguyên. Tính tổng và trung bình cộng của tất cả các phần tử trong mảng đó.

Ý tưởng giải quyết:

• Duyệt qua tất cả các phần tử trong mảng.
• Sử dụng một biến để lưu trữ tổng. Cộng giá trị của từng phần tử vào biến tổng này.
• Sau khi duyệt xong, chia tổng cho số lượng phần tử để tính trung bình cộng. Cần cẩn thận với phép chia số nguyên.

Mã nguồn minh họa:

#include <iostream>
#include <vector>
#include <numeric> // Can dung cho accumulate (tuy chon)

int main() {
    vector<int> arr = {10, 25, 5, 30, 15}; // Mang du lieu mau

    // Cach 1: Dung vong lap de tinh tong
    long long sum = 0; // Dung long long de tranh tran so neu mang lon
    for (size_t i = 0; i < arr.size(); ++i) {
        sum += arr[i]; // Cong gia tri phan tu hien tai vao tong
    }

    // Cach 2: Dung accumulate (cung tuong tu vong lap nhung ngan gon hon)
    // long long sum = accumulate(arr.begin(), arr.end(), 0LL); // 0LL de dam bao tong la long long

    // Tinh trung binh cong
    double average = 0.0;
    if (!arr.empty()) { // Tranh chia cho 0 neu mang rong
        average = static_cast<double>(sum) / arr.size(); // Ep kieu de chia lay so thuc
    }

    cout << "Mang: ";
    for (size_t i = 0; i < arr.size(); ++i) {
         cout << arr[i] << (i == arr.size() - 1 ? "" : " ");
    }
    cout << endl;

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

    return 0;
}

Giải thích code:

• Chúng ta khai báo một vector<int> arr với các giá trị mẫu.
• Biến sum được khởi tạo bằng 0. Chúng ta sử dụng kiểu long long cho sum để đảm bảo nó có thể chứa tổng lớn mà không bị tràn số (integer overflow).
• Vòng lặp for (size_t i = 0; i < arr.size(); ++i) duyệt qua từng phần tử. arr.size() trả về số lượng phần tử trong vector (kích thước mảng). Kiểu size_t thường dùng cho kích thước và chỉ số.
• sum += arr[i]; cộng giá trị của phần tử hiện tại (arr[i]) vào sum.
• (Phần code chú thích): accumulate là một hàm tiện ích từ thư viện <numeric> giúp tính tổng gọn gàng. arr.begin() và arr.end() là các iterator chỉ điểm bắt đầu và kết thúc của vector. 0LL là giá trị khởi tạo cho tổng, ép nó thành kiểu long long.
• Trước khi tính trung bình, chúng ta kiểm tra !arr.empty() để đảm bảo mảng không rỗng, tránh lỗi chia cho 0.
• average = static_cast<double>(sum) / arr.size(); tính trung bình. static_cast<double>(sum) ép kiểu tổng sang số thực trước khi chia, đảm bảo kết quả là số thực (trung bình cộng thường có phần thập phân).
• Cuối cùng, in ra mảng, tổng và trung bình cộng. Vòng lặp in mảng sử dụng toán tử ba ngôi (i == arr.size() - 1 ? "" : " ") để không in khoảng trắng sau phần tử cuối cùng.

Bài tập 3: Tìm phần tử lớn nhất và nhỏ nhất

Yêu cầu bài toán: Tìm giá trị phần tử lớn nhất và giá trị phần tử nhỏ nhất trong một mảng các số nguyên.

Ý tưởng giải quyết:

• Giả định rằng phần tử đầu tiên của mảng vừa là lớn nhất, vừa là nhỏ nhất ban đầu.
• Duyệt qua các phần tử còn lại của mảng (bắt đầu từ phần tử thứ hai).
• Trong mỗi lần lặp, so sánh phần tử hiện tại với giá trị lớn nhất và nhỏ nhất đã ghi nhận. Cập nhật nếu tìm thấy giá trị mới lớn hơn hoặc nhỏ hơn.

Mã nguồn minh họa:

#include <iostream>
#include <vector>
#include <algorithm> // Can dung cho min_element va max_element (tuy chon)
#include <limits>    // Can dung cho numeric_limits (tuy chon)

int main() {
    vector<int> arr = {10, 4, 8, 20, 1, 15}; // Mang du lieu mau

    if (arr.empty()) { // Xu ly truong hop mang rong
        cout << "Mang rong, khong the tim max/min." << endl;
        return 1;
    }

    // Cach 1: Dung vong lap de tim
    int max_val = arr[0]; // Gia su phan tu dau tien la max ban dau
    int min_val = arr[0]; // Gia su phan tu dau tien la min ban dau

    for (size_t i = 1; i < arr.size(); ++i) { // Bat dau tu phan tu thu hai
        if (arr[i] > max_val) {
            max_val = arr[i]; // Cap nhat max_val neu tim thay gia tri lon hon
        }
        if (arr[i] < min_val) {
            min_val = arr[i]; // Cap nhat min_val neu tim thay gia tri nho hon
        }
    }

    // Cach 2: Dung min_element va max_element (ngan gon hon)
    // auto min_it = min_element(arr.begin(), arr.end());
    // auto max_it = max_element(arr.begin(), arr.end());
    // int min_val_std = *min_it; // Lay gia tri tu iterator
    // int max_val_std = *max_it; // Lay gia tri tu iterator

    cout << "Mang: ";
    for (int val : arr) { // Vong lap for-each de in mang
         cout << val << " ";
    }
    cout << endl;

    cout << "Phan tu lon nhat: " << max_val << endl;
    cout << "Phan tu nho nhat: " << min_val << endl;

    return 0;
}

Giải thích code:

• Chúng ta kiểm tra nếu arr.empty() để tránh truy cập phần tử khi mảng rỗng.
• Biến max_val và min_val được khởi tạo bằng giá trị của phần tử đầu tiên arr[0]. Đây là điểm bắt đầu so sánh.
• Vòng lặp for (size_t i = 1; i < arr.size(); ++i) bắt đầu từ chỉ số 1 (phần tử thứ hai) vì phần tử 0 đã được dùng để khởi tạo.
• Trong vòng lặp, chúng ta so sánh arr[i] với max_val và min_val. Nếu arr[i] lớn hơn max_val hiện tại, max_val được cập nhật. Tương tự với min_val.
• (Phần code chú thích): min_element và max_element từ <algorithm> là các hàm tiện ích trả về iterator trỏ đến phần tử nhỏ nhất và lớn nhất. Toán tử * được dùng để lấy giá trị từ iterator đó.
• Đoạn code in mảng sử dụng vòng lặp range-based for loop (for (int val : arr)), đây là cách gọn gàng để duyệt qua tất cả các phần tử của container như vector.

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

Yêu cầu bài toán: Cho một mảng và một giá trị cụ thể. Đếm xem giá trị đó xuất hiện bao nhiêu lần trong mảng.

Ý tưởng giải quyết:

• Duyệt qua tất cả các phần tử trong mảng.
• Sử dụng một biến đếm, khởi tạo bằng 0.
• Trong mỗi lần lặp, so sánh phần tử hiện tại với giá trị cần đếm. Nếu chúng bằng nhau, tăng biến đếm lên 1.

Mã nguồn minh họa:

#include <iostream>
#include <vector>
#include <algorithm> // Can dung cho count (tuy chon)

int main() {
    vector<int> arr = {1, 5, 3, 5, 2, 5, 8, 5}; // Mang du lieu mau
    int target_value = 5; // Gia tri can dem

    // Cach 1: Dung vong lap de dem
    int count = 0; // Bien dem khoi tao bang 0
    for (size_t i = 0; i < arr.size(); ++i) {
        if (arr[i] == target_value) { // So sanh phan tu hien tai voi gia tri target
            count++; // Tang bien dem neu chung bang nhau
        }
    }

    // Cach 2: Dung count (ngan gon hon)
    // int count_std = count(arr.begin(), arr.end(), target_value);

    cout << "Mang: ";
    for (int val : arr) {
         cout << val << " ";
    }
    cout << endl;

    cout << "So lan xuat hien cua gia tri " << target_value << " la: " << count << endl;

    return 0;
}

Giải thích code:

• Chúng ta khai báo vector<int> arr và biến target_value là giá trị chúng ta muốn đếm.
• Biến count được khởi tạo bằng 0 để bắt đầu đếm.
• Vòng lặp for (size_t i = 0; i < arr.size(); ++i) duyệt qua từng phần tử.
• Trong vòng lặp, điều kiện if (arr[i] == target_value) kiểm tra xem phần tử hiện tại có bằng giá trị mục tiêu không.
• Nếu bằng, count++ tăng biến đếm lên 1.
• (Phần code chú thích): count từ <algorithm> là một hàm tiện ích thực hiện chính xác công việc này một cách hiệu quả. Nó đếm số lần xuất hiện của target_value trong khoảng từ arr.begin() đến arr.end().

Bài tập 5: Sắp xếp mảng

Yêu cầu bài toán: Sắp xếp các phần tử trong mảng theo thứ tự tăng dần.

Ý tưởng giải quyết: Mặc dù có nhiều thuật toán sắp xếp khác nhau (như Bubble Sort, Selection Sort, Merge Sort...), cách đơn giản nhất và hiệu quả nhất trong C++ là sử dụng hàm sắp xếp có sẵn trong thư viện chuẩn (sort).

Mã nguồn minh họa:

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

int main() {
    vector<int> arr = {12, 4, 9, 2, 18, 7}; // Mang du lieu mau

    cout << "Mang truoc khi sap xep: ";
    for (int val : arr) {
         cout << val << " ";
    }
    cout << endl;

    // Su dung sort de sap xep mang
    sort(arr.begin(), arr.end()); // Sap xep mac dinh la tang dan

    cout << "Mang sau khi sap xep tang dan: ";
    for (int val : arr) {
         cout << val << " ";
    }
    cout << endl;

    // De sap xep giam dan, co the them greater<int>() hoac dao nguoc mang sau khi sap xep tang dan
    // sort(arr.begin(), arr.end(), greater<int>());
    // reverse(arr.begin(), arr.end()); // Can #include <algorithm>

    return 0;
}

Giải thích code:

• Chúng ta bao gồm thư viện <algorithm> chứa hàm sort.
• sort(arr.begin(), arr.end()); là lời gọi hàm sắp xếp. arr.begin() và arr.end() là các iterator xác định phạm vi cần sắp xếp (từ đầu đến cuối vector).
• Mặc định, sort sắp xếp các phần tử theo thứ tự tăng dần. Nó thay đổi trực tiếp (in-place) vector arr.
• Sau khi gọi sort, vector arr đã được sắp xếp. Vòng lặp for-each được sử dụng để in ra mảng đã sắp xếp.
• (Phần code chú thích): Để sắp xếp giảm dần, bạn có thể truyền thêm tham số greater<int>() hoặc sử dụng reverse sau khi sắp xếp tăng dần.

Bài tập 6: Tìm kiếm một giá trị trong mảng (Linear Search)

Yêu cầu bài toán: Kiểm tra xem một giá trị cụ thể có tồn tại trong mảng hay không. Nếu có, cho biết nó xuất hiện lần đầu tiên tại chỉ số nào.

Ý tưởng giải quyết: Phương pháp tìm kiếm đơn giản nhất là tìm kiếm tuyến tính (Linear Search):

• Duyệt qua từng phần tử của mảng từ đầu đến cuối.
• So sánh phần tử hiện tại với giá trị cần tìm.
• Nếu tìm thấy, ta biết giá trị đó tồn tại và có thể trả về chỉ số hiện tại rồi kết thúc tìm kiếm.
• Nếu duyệt hết mảng mà không tìm thấy, giá trị đó không tồn tại trong mảng.

Mã nguồn minh họa:

#include <iostream>
#include <vector>
#include <algorithm> // Can dung cho find (tuy chon)

int main() {
    vector<int> arr = {15, 8, 22, 10, 5, 22, 30}; // Mang du lieu mau
    int search_value = 22; // Gia tri can tim kiem
    int search_value_not_found = 99; // Gia tri chac chan khong co

    // Cach 1: Dung vong lap (Linear Search tu viet)
    int found_index = -1; // Khoi tao chi so tim thay la -1 (khong tim thay)
    for (size_t i = 0; i < arr.size(); ++i) {
        if (arr[i] == search_value) {
            found_index = i; // Luu lai chi so neu tim thay
            break; // Ket thuc tim kiem ngay khi tim thay lan dau
        }
    }

    cout << "Mang: ";
    for (int val : arr) {
         cout << val << " ";
    }
    cout << endl;

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

    // Cach 2: Dung find (ngan gon hon)
    auto it = find(arr.begin(), arr.end(), search_value_not_found); // Tim gia tri khong co

    if (it != arr.end()) { // Neu iterator tra ve KHAC arr.end() thi tim thay
        // int index_std = distance(arr.begin(), it); // De lay chi so neu can
        // cout << "Gia tri " << search_value_not_found << " duoc tim thay (find)." << endl;
    } else { // Neu iterator tra ve BANG arr.end() thi khong tim thay
        cout << "Gia tri " << search_value_not_found << " khong ton tai trong mang (find)." << endl;
    }


    return 0;
}

Giải thích code:

• Chúng ta khai báo vector<int> arr, search_value (giá trị tìm thấy) và search_value_not_found (giá trị không tìm thấy).
• Biến found_index được khởi tạo bằng -1. Chúng ta dùng -1 như một chỉ báo rằng giá trị chưa được tìm thấy.
• Vòng lặp for (size_t i = 0; i < arr.size(); ++i) duyệt qua từng phần tử.
• if (arr[i] == search_value) kiểm tra xem phần tử hiện tại có bằng giá trị cần tìm không.
• Nếu có, 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ì yêu cầu là tìm lần đầu tiên xuất hiện). Nếu không có break;, nó sẽ tiếp tục duyệt và found_index sẽ lưu chỉ số của lần xuất hiện cuối cùng.
• Sau vòng lặp, chúng ta kiểm tra giá trị của found_index. Nếu nó vẫn là -1, tức là không tìm thấy. Ngược lại, found_index chứa chỉ số của lần xuất hiện đầu tiên.
• (Phần code chú thích): find từ <algorithm> cũng thực hiện tìm kiếm tuyến tính. Nó trả về một iterator trỏ đến phần tử đầu tiên tìm thấy hoặc arr.end() nếu không tìm thấy.