§ 12. Пошук элементаў з зададзенымі ўласцівасцямі

12.3. Знаходжанне ўсіх элементаў, якія задавальняюць умову пошуку

Калі патрабуецца вызначыць колькасць элементаў, якія задавальняюць якую-небудзь умову, то для гэтага вызначаюць асобную пераменную, значэнне якой павялічваюць на 1 кожны раз, калі знойдзены патрэбны элемент. Такую пераменную называюць лічыльнікам. Да пачатку прагляду элементаў масіву лічыльніку трэба задаць пачатковае значэнне ці, іншымі словамі, ініцыялізаваць значэнне пераменнай. У выпадку падліку колькасці элементаў, якія задавальняюць умову, лічыльнік ініцыялізуецца нулём. Для рашэння задачы трэба праглядаць увесь масіў.

Прыклад 12.6. Зададзены аднамерны масіў з n лікаў. Вызначыць колькасці элементаў, кратных x у гэтым масіве

Этапы выканання задання

I. Зыходныя даныя: масіў a, колькасць лікаў n, шуканы лік x.

II. Вынік: колькасць элементаў, якія задавальняюць умову, — k.

III. Алгарытм рашэння задачы. 

1. Зададзім лікі выпадкова на [0; 100).
2. Ініцыялізацыя лічыльніка.
3. У цыкле будзем праглядаць усе лікі ў масіве і параўноўваць з нулём іх астачы ад дзялення на лік x. Калі астача роўна нулю, то лічыльнік павялічваем на 1.
4. Вывад выніку.

IV. Апісанне пераменных: n, x, k – int, a – vector <int>.

Калі неабходна не толькі палічыць, колькі элементаў задавальняюць умову, але і захаваць індэксы такіх элементаў, то для гэтага можна выкарыстаць дадатковы масіў. Створым новы масіў 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. Тэсціраванне.