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

12.2. Пошук аднаго элемента, які задавальняе ўмову пошуку

Прыклад 12.1. Аднамерны масіў a складаецца з n выпадковых натуральных лікаў (усе лікі меншыя за 100). Вызначыць, ці ёсць у ім хоць бы адзін элемент, роўны x (значэнне x уводзіцца).

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

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

II. Вынік: вывад паведамлення «элемент знойдзены» або «элемент не знойдзены».

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

1. Увод колькасці элементаў і генерацыя элементаў масіву выпадковым чынам.
2. Лагічная пераменная p мае значэнне «праўда», калі элемент у масіве знойдзены, і «няпраўда» — у адваротным выпадку. Да прагляду элементаў масіву p = false.
3. У цыкле будзем праглядаць усе лікі ў масіве і параўноўваць іх з лікам x.
4. Пошук заканчваецца пры выкананні адной з дзвюх наступных умоў:

4.1. Элемент знойдзены (p = true), г. зн. у масіве ёсць такі элемент a[i], што a[i] = x.
4.2. Увесь масіў прагледжаны, і супадзення не выяўлена (p = false).

5. Вывад выніку.

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

Часта патрабуецца не толькі вызначыць, ці ёсць у масіве шуканы элемент, але і высветліць, на якім месцы ён знаходзіцца.

Будзем захоўваць індэкс знойдзенага элемента ў пераменнай k, якой да пачатку прагляду прысвоілі значэнне –1 (прыклад 12.2). Пасля выканання дадзенага алгарытму па значэнні пераменнай k можна вызначыць, ці ёсць у масіве шуканы элемент, і, калі ёсць, то дзе ён стаіць. Калі ў масіве некалькі такіх элементаў, то ў пераменнай k будзе захоўвацца нумар апошняга з іх. Калі такога элемента няма, то значэнне пераменнай k не зменіцца (k застанецца роўным –1).

На практыцы аперацыю пошуку даводзіцца выконваць дастаткова часта, і хуткасць работы праграмы знаходзіцца ў прамой залежнасці ад выкарыстоўваемага алгарытму пошуку.

У разгледжаных вышэй алгарытмах патрабуецца прагледзець увесь масіў нават у тым выпадку, калі шуканы элемент знаходзіцца на першым месцы.

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

Калі выкарыстоўваецца цыкл for з умовай прагляду ўсіх элементаў, то пры знаходжанні элемента трэба спыніць выкананне цыкла (прыклад 12.3).

Можна выкарыстаць цыкл while. Цыкл заканчвае работу, калі будзе знойдзены шуканы элемент або калі k == n , г. зн. элемента, які супадае з x, няма ў масіве (прыклад 12.4).

Пры такой рэалізацыі на кожнай ітэрацыі цыкла патрабуецца павялічваць індэкс k і вылічаць лагічны выраз. Паскорыць пошук можна, спрасціўшы лагічны выраз. Змесцім у канец масіву дадатковы элемент са значэннем х (вектар павінен быць апісаны з n + 1 элемента). Тады супадзенне з х абавязкова адбудзецца, і можна не правяраць умову a[k] != x. Такі дапаможны элемент часта называюць бар’ерам або вартавым, паколькі ён перашкаджае выхаду за межы масіву.

Прыклад 12.1.

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 + 1;

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

  }

  cout << endl;

  int x;

  cout << "x = ";

  cin >> x;

  bool p = false;

  ///лінейны пошук элемента

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

    if (a[i] == x)

      p = true;

  }

  if (p)

    cout << "naiden";

  else

    cout << "ne naiden";

  cout << endl;

  return 0;

}

VI. Тэсціраванне.

Прыклад 12.2. Фрагмент праграмы:

int k = -1;

///лінейны пошук элемента

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

  if (a[i] == x)

    k = i;

}

if (k == -1)

  cout << "ne naiden";

else

  cout << "naiden na meste " << k;

cout << endl;

 

Тэсціраванне.

Прыклад 12.3. Фрагмент праграмы:

int k = -1;

///лінейны пошук элемента

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

  if (a[i] == x){

    k = i;

    break;

  }

}

if (k == -1)

  cout << "ne naiden";

else

  cout << "naiden na meste " << k;

cout << endl;

Прыклад 12.4. Фрагмент праграмы:

int k = 0;

///лінейны пошук элемента

while (k < n && a[k] != x)

  k++;

if (k == n)

  cout << "ne naiden";

else

  cout << "naiden na meste " << k;

cout << endl;

Прыклад 12.5. Праграма:

#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 + 1);

  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;

  a[n] = x;

  ///лінейны пошук з бар'ерам

  while (a[k] != x)

    k++;

  if (k == n)

    cout << "ne naiden";

  else

    cout << "naiden na meste " << k;

  cout << endl;

  return 0;

}

У прыкладзе 12.5 прыведзена праграма рашэння задачы з прыкладу 12.1, у якой рэалізаваны алгарытм пошуку з бар’ерам