§ 12. Поиск элементов с заданными свойствами

12.3. Нахождение всех элементов, удовлетворяющих условию поиска

Если требуется определить количество элементов, удовлетворяющих какому-либо условию, то для этого определяют отдельную переменную, значение которой увеличивают на 1 каждый раз, когда найден нужный элемент. Такую переменную называют счетчиком. До начала просмотра элементов массива счетчику нужно задать начальное значение или, другими словами, инициализировать значение переменной. В случае подсчета количества элементов, удовлетворяющих условию, счетчик инициализируется нулем. Для решения задачи нужно просматривать весь массив.

Пример 12.6. Задан одномерный массив из n чисел. Определить количества элементов, кратных x в этом массиве.

Этапы выполнения задания

I. Исходные данные: массив a, количество чисел n, искомое число x.

II. Результат: количество элементов, удовлетворяющих условию — k.

III. Алгоритм решения задачи.Описание переменных: n, x, k – int, a – vector <int>.

1. Зададим числа случайно на [0; 100).
2. Инициализация счетчика.
3. В цикле будем просматривать все числа в массиве и сравнивать с нулем их остатки от деления на число x. Если остаток равен нулю, то счетчик увеличиваем на 1.

IV. Вывод результата.

Если необходимо не только посчитать, сколько элементов удовлетворяют условию, но и сохранить индексы таких элементов, то для этого можно воспользоваться дополнительным массивом. Создадим новый массив b. Как только будет найден необходимый элемент, его индекс будет заноситься в массив b. Количество элементов в массиве b заранее не известно. Поэтому опишем массив b как вектор без размера:

vector <int> b;

В этом случае для добавления элементов в конец вектора используется функция push_back(i). Вектор является динамическим типом данных, поэтому перед тем как добавить элемент в конец вектора, будет выделена память для его размещения. Если к элементу вектора b обратиться по индексу до того, как добавили элемент с помощью функции push_back, то получим ошибку времени выполнения, поскольку для размещения элемента не выделена память. Для того чтобы узнать количество элементов в массиве, можно воспользоваться функцией size(). Чтобы узнать, на каких позициях найдены числа, кратные x, необходимо вывести элементы массива b (пример 12.7).

Пример 12.6.

V. Программа:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdlib>

using namespace std;

int main()

{

srand(time(NULL));

int n;

cout << "n = ";

cin >> n;

vector <int> a(n);

cout << "chisla:" << endl;

for (int i = 0; i < n; i++){

a[i] = rand() % 100;

cout << a[i] << " ";

}

cout << endl;

int x;

cout << "x = ";

cin >> x;

int k = 0;

for (int i = 0; i < n; i++){

if (a[i] % x == 0)

k++;

}

cout << "naideno " << k;

cout << " elementov" << endl;

return 0;

}

VI. Тестирование.

VII. Анализ результатов. В первом случае кратными двум будут числа 34, 18, 82, 30, 24. Во втором случае — в массиве нет чисел, кратных 13.

Пример 12.7.

V. Программа:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdlib>

using namespace std;

int main()

{

srand(time(NULL));

int n;

cout << "n = ";

cin >> n;

vector <int> a(n);

cout << "chisla:" << endl;

for (int i = 0; i < n; i++){

a[i] = rand() % 100;

cout << a[i] << " ";

}

cout << endl;

int x;

cout << "x = ";

cin >> x;

vector <int> b;

for (int i = 0; i < n; i++)

if (a[i] % x == 0)

b.push_back(i);

int k = b.size();

cout << "naideno " << k;

cout << " elementov" << endl;

if (k) {

cout << "ih pozicii:" << endl;

for (int i = 0; i < k; i++)

cout << b[i] << " ";

cout << endl;

}

return 0;

}

VI. Тестирование.