§ 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. Тестирование.