Печатать книгуПечатать книгу

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

Сайт: Профильное обучение
Курс: Інфарматыка. 10 клас (Павышаны ўзровень)
Книга: § 12. Пошук элементаў з зададзенымі ўласцівасцямі
Напечатано:: Гость
Дата: Суббота, 4 Май 2024, 12:55

Оглавление

12.1. Лінейны пошук

Разгледзім, як ажыццяўляецца пошук даных, якія захоўваюцца ў масіве.

Сярод разнавіднасцей самых простых задач пошуку, якія сустракаюцца на практыцы, можна вылучыць наступныя тыпы:

1. Знайсці хоць бы адзін элемент, роўны зададзенаму элементу x. У выніку атрымліваюць i — індэкс (нумар) элемента масіву, такі, што a[i] = x.
2. Знайсці ўсе элементы, роўныя зададзенаму x. У выніку атрымліваюць колькасць такіх элементаў і (ці) іх індэксы.

Часам пошук арганізуецца не па супадзенні з элементам x, а па выкананні некаторых умоў. Прыкладам можа служыць пошук элементаў, якія задавальняюць умову: x1 ≤ a[i] ≤ x2, дзе x1 і x2 зададзены.

Калі няма ніякай дадатковай  інфармацыі пра даныя, якія адшукваюцца, то самы просты падыход — паслядоўны прагляд элементаў масіву.

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

Чалавек увесь час сутыкаецца з задачамі пошуку патрэбнай інфармацыі. У сучасным свеце інфармацыю шукаюць з выкарыстаннем сеткі Інтэрнэт. Таксама прыкладам пошуку інфармацыі можа служыць праца з даведнікамі ці бібліятэчнай картатэкай, якія могуць быць электроннымі. 

Для таго каб гэты пошук быў выніковым і хуткім, распрацоўваюць эфектыўныя алгарытмы пошуку. Важную ролю ў працэсе пошуку інфармацыі адыгрывае спосаб захоўвання даных. Адной з самых простых структур для гэтага з’яўляецца масіў.

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

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

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, у якой рэалізаваны алгарытм пошуку з бар’ерам

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. Тэсціраванне.

12.4. Рашэнне задач з выкарыстаннем алгарытма лінейнага пошуку

Прыклад 12.8. На складзе захоўваюцца пустыя скрыні для ўпакоўвання тавару. Вядома, што ёмістасць аднаго пакета з цукеркамі x кг. Вызначыце сумарную масу пакетаў з цукеркамі, якія можна ўпакаваць у такія скрыні, запоўніўшы скрыню цалкам.

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

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

II. Вынік: колькасць скрынь — k, сумарная маса — s.

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

1. Увод зыходных даных.
2. Ініцыялізацыя лічыльніка і значэння сумы:
k = 0; s = 0;
3. Праглядаючы масіў, праверым, ці з’яўляецца бягучы элемент лікам, кратным x (у гэтым выпадку скрыня будзе запоўнена цалкам). Калі кратны, то  павялічым лічыльнік k на 1, а пераменную s — на значэнне знойдзенага элемента масіву.
4.  Вывад выніку.

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

Прыклад 12.9. Маецца спіс хлопчыкаў 10 «В» класа і вынікі іх бегу на 100 м. Для здачы нарматыву неабходна прабегчы дыстанцыю не больш чым за 16 с. Вывесці прозвішчы навучэнцаў, якія не выканалі нарматыў па бегу. Колькі такіх навучэнцаў у класе? Зыходныя даныя захоўваюцца ў тэкставым файле input.txt. Вынік вывесці ў тэкставы файл output.txt.

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

I. Зыходныя даныя: масівы fam (прозвішчы навучэнцаў) і r (вынікі бегу ў секундах), колькасць навучэнцаў n.

II. Вынік: прозвішчы тых навучэнцаў, якія не выканалі нарматыў па бегу.

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

1. Увод зыходных даных.
2. Ініцыялізацыя лічыльніка: k = 0;
3. Будзем праглядаць масіў з вынікамі і правяраць, ці з’яўляецца бягучы элемент лікам, большым за 16 (нарматыў не здадзены). Калі такое значэнне знойдзена, то выведзем элемент масіву fam з адпаведным нумарам і павялічым значэнне лічыльніка на 1..
4. Вывад значэння лічыльніка.

IV. Апісанне пераменных:  
n, k – int, r – vector <double>,
fam – vector <string>.

Прыклад 12.10. У двух лінейных масівах x і y, зададзеных выпадковым чынам, захоўваюцца каардынаты пунктаў плоскасці (–200 ≤ x[i], y[i] ≤ 200). Вызначыць, якіх пунктаў больш — якія ляжаць унутры або звонку вобласці, абмежаванай акружнасцю радыуса r з цэнтрам у пачатку каардынат (будзем лічыць, што пункты, якія ляжаць на акружнасці, ляжаць унутры вобласці).

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

I. Зыходныя даныя: x, y — масівы лікаў, r — радыус акружнасці, n — колькасць пунктаў.

II. Вынік — адно з паведамленняў: «унутры пунктаў больш», «звонку пунктаў больш» або «пунктаў пароўну».

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

1. Увод зыходных даных. 
2. Ініцыялізацыя лічыльнікаў: k1 = 0; k2 = 0; 
3. Будзем праглядаць усе пункты і для кожнага правяраць прыналежнасць вобласці. Калі x2 + y2 ≤ R2, то пункт ляжыць унутры вобласці, тады павялічым значэнне лічыльніка k1 на 1, калі не, то павялічым на 1 значэнне лічыльніка k2. 
4. Параўнаем значэнні k1 і k2 і выведзем вынік.

IV. Апісанне пераменных: n, k1, k2 — int, x, y – vector <int>.

Прыклад 12.11. Зададзены аднамерны масіў з n цэлых лікаў. Вызначыць колькасці элементаў, якія з’яўляюцца лікамі Сміта. Вывесці тыя элементы, якія з’яўляюцца лікамі Сміта. (Лік Сміта — такі састаўны лік, сумма лічбаў якога роўна суме лічбаў усіх яго простых сумножнікаў.) Напрыклад, лікам Сміта з’яўляецца 202 = 2  × 101, паколькі 2 + 0 + 2 = 4 і 2 + 1 + 0 + 1 = 4.

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

I. Зыходныя даныя: а — масіў лікаў, n — колькасць лікаў у масіве.

II. Вынік: лікі Сміта і іх колькасць у масіве.

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

1. Увод зыходных даных.
2. Ініцыялізацыя лічыльніка: k = 0;
3. Будзем праглядаць кожны элемент масіву і вызначаць, ці з’яўляецца ён лікам Сміта. Для праверкі створым функцыю check, якая будзе атрымліваць у якасці параметра элемент масіву, а таксама вяртаць значэнне true, калі лік з’яўляецца лікам Сміта, і false — у адваротным выпадку.

3.1. Знойдзем суму лічбаў ліку.
3.2. Будзем раскладаць лік на простыя множнікі і для кожнага множніка знаходзіць суму лічбаў.
3.3. Для раскладання ліку на простыя множнікі будзем дзяліць яго спачатку  на 2 (пакуль дзеліцца), затым на 3. На 4 лік ужо дзяліцца не будзе, будзем дзяліць на 5 і г. д. Скончыцца раскладанне тады, калі пасля ўсіх дзяленняў лік стане роўным 1.
4. Таксама нам спатрэбіцца функцыя sum, якая для ліку будзе вяртаць яго суму лічбаў. 

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

Прыклад 12.12. Зададзены аднамерны масіў з n радкоў. Даныя ў масіве чытаюцца з тэкставага файла input.txt. Кожны радок з’яўляецца сказам са слоў, падзеленых прабеламі. Знайсці і вывесці ў тэкставы файл output.txt тыя сказы, у якіх няцотная колькасць слоў. Колькі сказаў вывелі?

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

I. Зыходныя даныя: а — масіў лікаў, n — колькасць лікаў у масіве.

II. Вынік: шуканыя радкі і іх колькасць.

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

1. Увод зыходных даных.
2. Ініцыялізацыя лічыльніка: k = 0;
3. Будзем праглядаць кожны радок і вызначаць, колькі ў ім слоў. Для праверкі створым функцыю check, якая будзе атрымліваць у якасці параметра элемент масіву і вяртаць колькасць слоў у радку. Калі колькасць слоў з’яўляецца няцотным лікам, то выведзем радок і павялічым значэнне лічыльніка.

3.1. Перад кожным словам сказа, акрамя першага, стаіць прабел. Слова пачынаецца з сімвала, які прабелам не з’яўляецца.
3.2. Дабавім прабел перад першым словам, тады колькасць слоў будзе вызначацца колькасцю спалучэнняў пар сімвалаў: прабел і не прабел.

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

Прыклад 12.8.

V. Праграма:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  setlocale(0,"");

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

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

    cin >> a[i];

  int x;

  cout << "маса цукерак ";

  cin >> x;

  int s = 0, k = 0;

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

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

      k++;

      s += a[i];

    }

  cout << "упакавалі " << k;

  cout << " скрынь, сумарная маса ";

  cout << s << " кг" << endl;

  return 0;

}

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

VII. Аналіз вынікаў. Скрыні, якія задавальняюць умову задачы, маюць масу 15, 25, 10, 20, 45.

Прыклад 12.9.

V. Праграма:

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

 

using namespace std;

 

int main()

{

  ifstream fin ("input.txt");

  ofstream fout ("output.txt");

  int n;

  fin >> n;

  fin.ignore (); 

  vector <string> fam(n);

  vector <double> r(n);

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

    fin >> fam[i] >> r[i];

  int k = 0;

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

    if (r[i] > 16){

      fout << fam[i] << endl;

      k ++;

    }

  fout << "не здалі нарматыў ";

  fout << k << " навучэнцаў" << endl;

  return 0;

}

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

VII. Аналіз вынікаў. Вынік Сідарава 21, а Каралёва 16.1, што перавышае нарматыў.

Прыклад 12.10.

V. Праграма:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdio>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n, r;

  cout << "n = ";

  cin >> n;

  cout << "r = ";

  cin >> r;

  vector <int> x(n), y(n);

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

    x[i] = rand() % 401 - 200;

    y[i] = rand() % 401 - 200;

  }

  int k1 = 0, k2 = 0;

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

    if (x[i] * x[i] + y[i] * y[i] 
        <= r * r)

      k1++;

    else

      k2++;

  if (k1 > k2)

    cout << "vnutri";

  else

    if (k1 < k2)

      cout << "snarugi";

    else

      cout << "porovnu";

  cout << endl;

  return 0;

}

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

VII. Аналіз вынікаў. Паводле паведамленняў, якія выдае праграма, складана меркаваць пра яе правільнасць. Для праверкі можна вывесці значэнні каардынат кожнага пункта ў файл і пры праверцы ставіць дадатковыя паметкі. Напрыклад, «+», калі пункт унутры, і «-», калі звонку.

Прыклад 12.11.

V. Праграма:

#include <iostream>

#include <vector>

 

using namespace std;

 

int sum(int x)

{

  int s = 0;

  while (x >0){

    s += x % 10;

    x /= 10;

  }

  return s;

}

 

bool check(int x)

{

  int s1 = sum(x);

  int s2 = 0;

  int d = 2;

  //разкладанне на простыя множнікі

  while (x != 1){

    while (x % d == 0){

      s2 += sum(d);

      x /= d;

    }

    d++;

  }

  return (s1 == s2);

}

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

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

    cin >> a[i];

  int k = 0;

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

    if (check(a[i])){

      k++;

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

  }

  cout << endl << "vsego " << k;

  cout << " chisel Smita" << endl;

  return 0;

}

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

Прыклад 12.12.

V. Праграма:

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

#include <windows.h>

 

using namespace std;

using namespace std::__cxx11;

 

int check(string x)

{

  int k = 0;

  x = " " + x;

  int len = x.length();

  for (int i = 0; i < len - 1; i++)

    if (x[i] == ' ' && x[i + 1] != ' ')

      k++;

  return k;

}

 

int main()

{

  SetConsoleCP(1251);

  SetConsoleOutputCP(1251);

  ifstream fin("input.txt");

  ofstream fout("output.txt");

  int n;

  fin >> n;

  fin.ignore();

  vector <string> a(n);

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

    getline(fin, a[i]);

  int k = 0;

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

    if (check(a[i]) % 2){

      fout << a[i] << endl;

      k++;

    }

  fout << "Всего - " << k;

  fout << " строк(–а, –u)" << endl;

  return 0;

}

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

 

Пытанні да параграфу

1. Што называюць паслядоўным пошукам?

2. Як вызначыць, што ў масіве быў знойдзены элемент з пэўнымі ўласцівасцямі?

3. Для чаго выкарыстоўваюць пераменныя-лічыльнікі?

4. Што такое ініцыялізацыя пераменнай?

Практыкаванні

    

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

2. Зададзены прозвішчы і рост навучэнцаў 10-га класа. Напішыце праграму, якая выведзе прозвішчы навучэнцаў, рост якіх меншы за сярэдні рост па класе.

3. Вядомы даныя пра плошчу n краін (у млн кв. км) і колькасці насельніцтва (у млн). Напішыце праграму, якая выведзе нумары тых краін, шчыльнасць насельніцтва ў якіх большая за x.

4. Для практыкавання 3 дабаўце магчымасць уводзіць і выводзіць назвы краін з тэкставага файла.

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

1. Ці з’яўляецца дадатным лікам?
2. Ці з’яўляецца цотным лікам?
3. Ці з’яўляецца няцотным, кратным 7 лікам?
4. Пры дзяленні на 7 дае ў астачы 1, 2 або 3?

6. Напісаць праграму, якая палічыць колькасць элементаў масіву, што задавальняюць уласцівасці, апісаныя ў практыкаванні 5.

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

8. У прыкладзе 7.15 разглядалася рэкурсіўная функцыя для раскладання ліку на простыя множнікі. Змяніце функцыю check у прыкладзе 12.11 на рэкурсіўную па аналогіі з функцыяй з прыкладу 7.15.

9. Напісаць праграму, якая палічыць колькасць пар суседніх (нумары такіх элементаў адрозніваюцца на 1) элементаў масіву, якія задавальняюць названую ніжэй умову.

1. Абодва лікі ў пары з’яўляюцца дадатнымі.
2. Лікі ў пары маюць розныя знакі.
3. Ніводны лік з пары не роўны нулю.
4. Лікі маюць аднолькавую цотнасць (або абодва цотныя, або абодва няцотныя).

10. Напішыце праграму, якая знойдзе ў лінейным масіве і выведзе ўсе лікі Армстранга. Лікам Армстранга называецца такі лік, які роўны суме сваіх лічбаў, узведзеных у ступень, роўную колькасці яго лічбаў. Напрыклад, лікам Армстранга з’яўляецца лік 371 = 33 + 73 + 13 = 27 + 343 + 1. Вызначыць, колькі лікаў вывелі.

11. Зададзены аднамерны масіў з N радкоў. Кожны радок з’яўляецца сказам са слоў, падзеленых прабеламі. Напішыце праграму, якая знойдзе і выведзе тыя сказы, у якіх ёсць словы, што пачынаюцца на галосную літару (маленькую або вялікую). Зыходныя даныя прачытаць з тэкставага файла input.txt. Вынік запісаць у тэкставы файл output.txt.