Tìm kiếm¶

Trong quá trình luyện công, người học phải tự mình viết những hàm tìm kiếm nhằm rèn luyện tư duy và kỹ thuật lập trình. Tuy nhiên, khi làm bài thi, thời gian là yếu tố quan trọng, thí sinh nên sử dụng những công cụ có sẵn của ngôn ngữ, hạn chế viết lại hoặc tạo lại nhằm dành thời giờ và công sức cho ý tưởng.

Bài viết này hướng dẫn cách sử dụng một số hàm có sẵn liên quan đến tìm kiếm trên một vector.

Tìm giá trị của phần tử nhỏ nhất¶

Đặt vec là vector gồm các số nguyên.

C++Python

vector<int> vec;

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)

Các phần tử của vec được phát sinh ngẫu nhiên bằng đoạn mã sau:

C++Python

void generate()
{
    int x;
    for (int i = 0; i < n; ++i)
    {
        x = rand() % 10; // (1)
        vec.push_back(x);
    }
}

rand() % 10 dùng để phát sinh ngẫu nhiên một số nằm trong [0, 10).

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)

Output:

Vector ban đầu:
1 7 4 0 9 4 8 8 2 4 5 5 1 7 1 1 5 2 7 6

Trong C++, để tìm vị trí của phần tử nhỏ nhất và lớn nhất trong vector, ta sử dụng hàm min_element() và max_element() của thư viện algorithm.

Hai hàm này đều trả về con duyệt, có kiểu là vector<int>::iterator, trỏ vào phần tử nhỏ nhất hoặc lớn nhất.

Sau khi có được con duyệt, ta dùng toán tử * để lấy giá trị tại vị trí tương ứng.

Đoạn mã sau tìm giá trị của phần tử nhỏ nhất trong vector.

C++Python

    int min_value = *min_element(vec.begin(), vec.end());
    cout << "Giá trị nhỏ nhất: " << min_value << endl;

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)

Output:

Giá trị nhỏ nhất: 0

Tìm chỉ số của phần tử lớn nhất¶

Để lấy được chỉ số tại vị trí tương ứng, ta đem con duyệt trả về trừ đi vector.begin().

Đoạn mã sau tìm chỉ số của phần tử lớn nhất.

C++Python

    vector<int>::iterator max_it = max_element(vec.begin(), vec.end());
    int max_position = max_it - vec.begin();
    cout << "Chỉ số của phần tử lớn nhất: " << max_position << endl;

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)

Output:

Vị trí của phần tử lớn nhất: 4

Nếu có nhiều phần tử lớn nhất thì hàm max_element trỏ vào vị trí lớn nhất đầu tiên.

Tìm phần tử có giá trị k¶

Đoạn mã sau tìm phần tử có giá trị k bằng cách dùng hàm find().

C++Python

    int k = 8;
    vector<int>::iterator it = find(vec.begin(), vec.end(), k);

    if (it != vec.end()) // (1)
    {
        int found_at = it - vec.begin();
        cout << "Tìm thấy k = " << k << " tại vị trí: " << found_at << endl;
    }
    else
    {
        cout << "Không tìm thấy" << endl;
    }

vec.end() trỏ ra sau vector, chứ không phải trỏ vào phần tử cuối.

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)

Output:

Tìm thấy k = 8 tại vị trí: 6

Tìm phần tử thỏa điều kiện cho trước¶

Giả sử ta muốn tìm phần tử vừa chẵn vừa lớn hơn 5.

Trước hết, ta viết hàm kiểm tra điều kiện vừa chẵn vừa lớn hơn 5, đặt là hàm check().

C++Python

bool check(int x)
{
    return x % 2 == 0 && x > 5;
}

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)

Sau đó, ta truyền hàm check() vừa viết vào hàm find_if().

C++Python

    int first_match = find_if(vec.begin(), vec.end(), check) - vec.begin();
    cout << "Phần tử đầu tiên thỏa điều kiện: " <<  first_match << endl;

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)

Output:

Phần tử đầu tiên thỏa điều kiện: 6

Đếm phần tử thỏa điều kiện cho trước¶

Giả sử ta muốn đếm số phần tử vừa chẵn vừa lớn hơn 5.

Vẫn dùng hàm check() như trên, lần này ta truyền check() vào hàm count_if().

C++Python

    int count_match = count_if(vec.begin(), vec.end(), check);
    cout << "Số phần tử thỏa điều kiện: " <<  count_match << endl;

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)

Output:

Số phần tử thỏa điều kiện: 3

Lọc ra các phần tử thỏa và không thỏa điều kiện cho trước¶

Giả sử ta muốn lọc/trích ra các phần tử vừa chẵn vừa lớn hơn 5.

Vẫn dùng hàm check() như trên, lần này ta truyền check() vào hàm copy_if() và đính kèm hàm back_inserter() dành cho vector kết quả.

C++Python

    vector<int> match_elements;
    copy_if(vec.begin(), vec.end(), back_inserter(match_elements), check);
    show("Các phần tử thỏa điều kiện:", match_elements);

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)

Output:

Các phần tử thỏa điều kiện:
8 8 6

Tương tự, ta dùng hàm remove_copy_if() để lọc ra các phần tử không thỏa điều kiện.

C++Python

    vector<int> unmatch_elements;
    remove_copy_if(vec.begin(), vec.end(), back_inserter(unmatch_elements), check);
    show("Các phần tử không thỏa điều kiện:", unmatch_elements);

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)

Output:

Các phần tử không thỏa điều kiện:
1 7 4 0 9 4 2 4 5 5 1 7 1 1 5 2 7

Toàn bộ chương trình¶

C++Python

Chương trình C++ hoàn chỉnh đặt tại Gist của GitHub.

Nội dung này sẽ cập nhật sau khi chủ thớt được đồ-nét :)