close

Giải thuật Tìm kiếm nhiều mục tiêu (Multiple-Item Search) trong C++ - Giải thích, Ví dụ và Mã nguồn

Giải thuật tìm kiếm nhiều mục tiêu được sử dụng để tìm tất cả các vị trí xuất hiện của một phần tử cụ thể trong một danh sách. Khác với các thuật toán tìm kiếm một mục tiêu, phương pháp này ghi nhận nhiều vị trí của phần tử mục tiêu và trả về danh sách các vị trí đó.

Cách hoạt động

  1. Bắt đầu từ đầu danh sách.
  2. Duyệt qua từng phần tử trong danh sách.
  3. So sánh phần tử hiện tại với giá trị mục tiêu.
  4. Nếu phần tử hiện tại bằng giá trị mục tiêu, ghi nhận vị trí của nó.
  5. Tiếp tục đến phần tử tiếp theo và lặp lại các bước 3-4.
  6. Sau khi duyệt qua toàn bộ danh sách, trả về danh sách các vị trí đã ghi nhận.

Ví dụ

Hãy xem xét một danh sách các số nguyên và muốn tìm tất cả các vị trí xuất hiện của số 23.

Danh sách: {12, 23, 45, 23, 56, 23, 89, 90}

  1. Bắt đầu từ đầu: 12. Không phải số cần tìm.
  2. Tiếp tục với phần tử tiếp theo: 23. Tìm thấy phù hợp, ghi nhận vị trí là 1.
  3. Tiếp tục với phần tử tiếp theo: 45. Không phải số cần tìm.
  4. Tiếp tục với phần tử tiếp theo: 23. Tìm thấy phù hợp, ghi nhận vị trí là 3.
  5. Tiếp tục với phần tử tiếp theo: 56. Không phải số cần tìm.
  6. Tiếp tục với phần tử tiếp theo: 23. Tìm thấy phù hợp, ghi nhận vị trí là 5.
  7. Tiếp tục với phần tử tiếp theo: 89. Không phải số cần tìm.
  8. Tiếp tục với phần tử tiếp theo: 90. Không phải số cần tìm.
  9. Sau khi duyệt qua danh sách, trả về danh sách các vị trí: [1, 3, 5].

Mã ví dụ trong C++

#include <iostream>
#include <vector>

std::vector<int> multipleItemSearch(const std::vector<int>& arr, int target) {
    std::vector<int> positions;

    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] == target) {
            positions.push_back(i);
        }
    }

    return positions;
}

int main() {
    std::vector<int> numbers = {12, 23, 45, 23, 56, 23, 89, 90};
    int target = 23;

    std::vector<int> result = multipleItemSearch(numbers, target);

    std::cout << "Các vị trí xuất hiện của " << target << " là: ";
    for (int pos : result) {
        std::cout << pos << " ";
    }
    std::cout << std::endl;

    return 0;
}

Trong ví dụ trên, chúng ta sử dụng hàm multipleItemSearch để tìm tất cả các vị trí xuất hiện của số 23 trong danh sách các số nguyên. Kết quả sẽ là một vector chứa các vị trí của tất cả các vị trí xuất hiện (vị trí bắt đầu từ 0).