§ 20. Выкарыстанне бібліятэчных функцый для сартавання і пошуку даных

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

Шмат якія з разгледжаных намі задач дастаткова часта сустракаюцца на практыцы. Таму іх рашэнні, аформленыя ў выглядзе адпаведных функцый, былі ўключаны ў бібліятэку algorithm[1]. Для падключэння бібліятэкі неабходна каманда #include <algorithm>.

Разгледзім некаторыя з функцый гэтай бібліятэкі. У Дадатку можна знайсці больш падрабязны спіс.

[1] https://ru.cppreference.com/w/cpp/algorithm (дата доступу 25.06.2020).

20.1. Лінейны пошук элемента

Для арганізацыі лінейнага пошуку элемента ў масіве можна выкарыстоўваць наступныя функцыі:

find	Знаходзяць значэнне ў дадзеным дыяпазоне
count	Вяртае колькасць элементаў, якая адпавядае дадзенаму значэнню
find_if	Шукае першае ўваходжанне элемента, для якога дакладна значэнне функцыі кампаратара
count_if	Вяртае колькасць элементаў, для якіх значэнне функцыі кампаратара з’яўляецца праўдай

Ва ўсіх гэтых функцый тры параметры. Першыя два параметры з'яўляюцца ітэратарамі, якія вызначаюць дыяпазон для пошуку ў масіве, трэці задае ўмову пошуку. Пры гэтым левая мяжа дыяпазону ўваходзіць у вобласць пошуку, а правая — не. Гэта значыць дыяпазон пошуку з’яўляецца паўінтэрвалам. Калі пошук ажыццяўляецца ва ўсім вектары, то выкарыстоўваюцца ітэратры begin() и end().

У якасці выніку функцыі find і find_if выдаюць значэнне ітэратара, які паказвае на першы элемент, што адпавядае пошукаваму запыту.

Кампаратар для функцый, якія рэалізуюць пошук элемента ў дыяпазоне, мае адзін параметр. Кампаратар вяртае значэнне true, калі элемент задавальняе ўмову пошуку, і false, калі не. Функцыя пошуку перадае ў кампаратар па чарзе значэнні з дыяпазону пошуку. Як толькі для якога-небудзь значэння атрымалі true, работа пошукавай функцыі спыняецца.

Калі элемент не знойдзены, функцыя вяртае ітэратар на правую мяжу вобласці пошуку.

Прыклад 20.1. Дадзены лінейны масіў цэлых лікаў. Напісаць праграму, якая:

1) знойдзе пазіцыю элемента, роўнага x;

2) знойдзе пазіцыю элемента, кратнага x;

3) палічыць колькасць элементаў, роўных x;

4) палічыць колькасць элементаў, кратных x.

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

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

II. Вынік: пазіцыі элементаў n1 і n2 (пункты 1 і 2) і колькасць элементаў k1 і k2 (пункты 3 і 4).

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

1. Увод зыходных даных. Даныя згенерыруем выпадковым чынам.
2. Будзем выкарыстоўваць наступныя функцыі:

2.1. find для пункта 1.
2.2. find_if для пункта 2.
2.3. count для пункта 3.
2.4. count_if для пункта 4.

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

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

Функцыі min_element і max_element і max_element вяртаюць ітэратар на мінімальнае і максімальнае значэнні элементаў у дыяпазоне.

Прыклад 20.2. Дадзены лінейны масіў цэлых лікаў. Напісаць праграму, якая знойдзе мінімальны і максімальны элементы ў масіве.

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

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

II. Вынік: пазіцыі мінімальнага і максімальнага элементаў nmin і nmax і іх значэнні.

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

Увод зыходных даных. Даныя згенерыруем выпадковым чынам.
Будзем выкарыстоўваць адпаведныя функцыі.
Вывад выніку.

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

Прыклад 20.1.

V. Праграма:

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstdlib>

#include <ctime>

using namespace std;

int x;

bool comp(int t)

{

return (t % x == 0);

}

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;

//пошук элемента x у масіве

cout << "x = ";

cin >> x;

int n1 = find(a.begin(), a.end(), x) - a.begin();

if(n1 < a.size())

cout << "chislo na meste " << n1 << endl;

else

cout << "net chisla = x" << endl;

//пошук па ўмове: лік кратны x

int n2 = find_if(a.begin(), a.end(), comp) - a.begin();

if (n2 < a.size()){

cout << "chislo " << a[n2];

cout << " na meste " << n2;

cout << endl;

}

else

cout << "net kratnyh chisel" << endl;

//колькасць элементаў, роўных х

int k1 = count(a.begin(), a.end(), x);

cout << "ravno x - " << k1 << endl;

//колькасць элементаў, кратных х

int k2 = count_if(a.begin(), a.end(), comp);

cout << "kratno x - " << k2 << endl;

return 0;

}

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

VII. Аналіз вынікаў. Індэкс ліку 3 у масіве роўны 1, а таксама гэты лік кратны самому сабе. У масіве адзін лік, роўны 3, і два лікі (3 і 18), кратныя 3.

Звярніце ўвагу на тое, што пераменная x апісана як глабальная пераменная, паколькі яна выкарыстоўваецца як у функцыі main, так і ў кампаратары comp.

Прыклад 20.2.

V. Праграма:

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstdlib>

#include <ctime>

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 nmin = min_element(a.begin(), a.end()) - a.begin();

cout << "min element = " << a[nmin];

cout << " na meste - " << nmin << endl;

int nmax = max_element(a.begin(), a.end()) - a.begin();

cout << "max element = " << a[nmax];

cout << " na meste - " << nmax << endl;

return 0;

}

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

Функцыі min_element і max_element могуць мець трэці параметр — кампаратар, які вызначае правіла парадку для элементаў паказанага дыяпазону.

20.2. Сартаванне

Для сартавання элементаў вектара выкарыстоўваецца функцыя sort, якая мае два параметры: межы дыяпазону, які сартуецца.

Калі ў якасці меж дыяпазону выкарыстоўваць стандартныя ітэратары begin() і end(), то элементы вектара будуць адсартаваны ў парадку ўзрастання. Калі выкарыстоўваць ітэратары rbegin() і rend(), то элементы будуць адсартаваны ў парадку спадання. Пры гэтым вектар павінен складацца з элементаў, для якіх вызначаны аперацыі параўнання: цэлых ці рэчаісных лікаў, сімвалаў, радкоў.

Калі вектар складаецца з элементаў, для якіх не вызначана паняцце парадку (структур ці іншых вектараў), то для іх сартавання неабходны трэці параметр — функцыя-кампаратар, якая задае адносіны парадку для элементаў.

Прыклад 20.3. Дадзены лінейны масіў цэлых лікаў. Напісаць праграму, якая адсартуе лікі ў парадку спадання.

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

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

II. Вынік: адсартаваны масіў.

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

Увод зыходных даных. Даныя згенерыруем выпадковым чынам.
Будзем выкарыстоўваць функцыю sort. Паколькі сартаваць элементы трэба па спаданні, то будзем выкарыстоўваць адваротныя ітэратары rbegin() і rend().
Вывад выніку.

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

Для сартавання ў парадку спадання можна выкарыстаць стандартны кампаратар, які задае парадак — большае раней за меншае:

sort(v.begin(), v.end(), greater<int>());

Акрамя кампаратара greater, могуць выкарыстоўвацца кампаратары: less (менш), equal_to (роўна), not_equal_to (не роўна), less_equal (менш або роўна), greater_equal(больш або роўна). Гэтыя кампаратары асацыяваны з тыпам свайго параметра, для якога павінны быць вызначаны аперацыі параўнання. Па змоўчанні працуе кампаратар less, які можна прапускаць.

Прыклад 20.4. На плоскасці зададзены сваімі каардынатамі n пунктаў. Размясціць пункты ў парадку ўзрастання іх абсцыс. Знайсці ўсе пары суседніх пунктаў, абсцысы якіх знаходзяцца на адлегласці не менш за l адна ад адной.

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

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

II. Вынік: адсартаваны масіў.

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

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

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

У рэалізацыі Стандартнай бібліятэкі шаблонаў (STL) у C++ для рэалізацыі сартавання выкарыстоўваецца падыход Дэвіда Мюсера. У 1997 г. ён прапанаваў выкарыстоўваць інтраспектыўнае сартаванне (Introsort). Гэта камбінаваны алгарытм сартавання, які выкарыстоўвае хуткае сартаванне і пераключаецца на пірамідальнае[1] сартаванне, калі глыбіня рэкурсіі перавысіць лагарыфм ад ліку элементаў, што сартуюцца. У хуткім сартаванні выбар апорнага элемента робіцца як медыяны з трох. Калі колькасць элементаў становіцца меншай за 16, ужываецца алгарытм сартавання простымі ўстаўкамі. Такім чынам, функцыя sort аб’ядноўвае ў сабе тры алгарытмы сартавання: хуткае, пірамідальнае і сартаванне простымі ўстаўкамі. Функцыя гарантавана выкарыстоўвае каля аперацый параўнанняў і абменаў.

Прыклад 20.3.

V. Праграма:

#include <iostream>

#include <vector>

#include <cstdlib>

#include <ctime>

#include <algorithm>

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 << "sort" << endl;

sort(a.rbegin(), a.rend());

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

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

cout << endl;

return 0;

}

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

Прыклад 20.4.

V. Праграма:

#include <iostream>

#include <cmath>

#include <vector>

#include <algorithm>

using namespace std;

struct tchk

{

double x, y;

};

bool comp(tchk a, tchk b)

{

return (a.x < b.x ||

(a.x == b.x && a.y < b.y));

}

int main()

{

int n;

cout << "n = ";

cin >> n;

vector <tchk> t(n);

cout << "koordinaty tochek" << endl;

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

cin >> t[i].x >> t[i].y;

/// сартаванне

sort(t.begin(), t.end(), comp);

cout << "sort" << endl;

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

cout << "(" << t[i].x << ","

<< t[i].y << ")" << " ";

cout << endl;

double l;

cout << "l = ";

cin >> l;

///пошук

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

if (abs(t[i].x - t[i + 1].x) >= l){

cout << "(" << t[i].x << ",";

cout << t[i].y << ")" << '\t';

cout << "(" << t[i + 1].x ;

cout << ","<< t[i + 1].y;

cout << ")" << endl;

}

return 0;

}

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

[1] Пірамідальнае сартаванне выкарыстоўвае бінарнае сартавальнае дрэва для захоўвання даных. Пачытаць пра яго можна тут: Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн., 3-е издание. — М.: «Вильямс», 2013.

20.3. Бінарны пошук

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

binary_search	Вызначае, ці прысутнічае элемент у некаторым дыяпазоне
equal_range	Шукае дыяпазон элементаў, роўных вызначанаму элементу
lower_bound	Шукае першае месца ў дыяпазоне, у якое можна ўставіць значэнне, захоўваючы ўпарадкаванасць
upper_bound	Шукае апошняе месца, куды можна ўставіць значэнні, захоўваючы ўпарадкаванасць (першае месца, у якім элемент большы, чым устаўляемае значэнне)

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

Прыклад 20.5. Дадзены лінейны адсартаваны масіў цэлых лікаў. Напісаць праграму, якая атрымае колькасць элементаў, меншых за x і большых за y. Масіў упарадкаваны па спаданні. Даныя прачытаць з файла. Лікі x і y увесці з клавіятуры.

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

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

II. Вынік: колькасць элементаў, меншых за x і большых за y.

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

1. Увод зыходных даных.

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

2.1. Для пошуку n1 — нумару першага значэння, меншага за x, выкарыстаем функцыю upper_bound.
2.2.Для пошуку n2 — нумару першага значэння, большага y, выкарыстаем функцыю lower_bound.
2.3. Адказам будзе значэнне, роўнае модулю рознасці пазіцый для лікаў x і y.
2.4. Вывод результата.

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

Функцыя equal_range вяртае дыяпазон, які змяшчае ўсе элементы, роўныя x. Дыяпазон вызначаецца двума ітэратарамі, першы паказвае на першы элемент, не меншы (роўны ці большы), чым x, другі паказвае на першы элемент, большы, чым x. Першы ітэратар можа быць атрыманы выкарыстаннем lower_bound(), другі — upper_bound(). Вяртаемым значэннем з’яўляецца тып пара (pair), які змяшчае два ітэратары.

Для выкарыстання тыпу даных pair неабходна бібліятэка utility.

Прыклад 20.5.

V. Праграма:

#include <iostream>

#include <fstream>

#include <vector>

#include <cmath>

#include <algorithm>

using namespace std;

int main()

{

ifstream fin("input.txt");

int n;

fin >> n;

vector <int> a(n);

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

fin >> a[i];

int x, y;

cout << "x, y" << endl;

cin >> x >> y;

int n1 = upper_bound(

a.begin(), a.end(),

x, greater<int>())

- a.begin();

int n2 = lower_bound(

a.begin(), a.end(),

y, greater<int>())

- a.begin();

cout << n1 << " " << n2 << endl;

int rez = abs(n2 - n1);

cout << "mezdu x i y ";

cout << rez << " chisel";

cout << endl;

return 0;

}

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

Аналіз вынікаў. Значэнне 7 — нумар першага, меншага за 88, а значэнне 8 — нумар першага, большага за 82.

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

1. Якую бібліятэку можна выкарыстоўваць для пошуку і сартавання элементаў масіву?

2. Якія функцыі дазваляюць ажыццяўляць пошук элемента?

3. З дапамогай якой функцыі можна адсартаваць масіў?

4. У якіх функцыях рэалізаваны алгарытм бінарнага пошуку?

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

1. Рэалізуйце рашэнне задач з практыкаванняў 5—7 пасля § 12, выкарыстоўваючы функцыі пошуку з бібліятэкі algorithm.

2. Выкарыстоўваючы функцыі для пошуку мінімальнага і максімальнага элементаў, рэалізуйце рашэнне задач з практыкаванняў 6—7, 9—16 пасля § 13.

3. Адсартуйце масівы з практыкаванняў 3—5 пасля § 18, выкарыстоўваючы функцыю sort.

4. Выкарыстоўваючы функцыі бінарнага пошуку з бібліятэкі algorithm, рэалізуйце рашэнні задач з практыкаванняў 1—2 пасля § 19.

5. На плоскасці сваімі каардынатамі зададзены n пунктаў. Размясціць пункты ў парадку спадання іх абсцыс. Знайсці ўсе тройкі суседніх пунктаў, абсцысы якіх строга спадаюць.

6*. На плоскасці сваімі каардынатамі зададзены n пунктаў. Размясціць пункты ў парадку ўзрастання вугла нахілу вектара, зададзенага дадзеным пунктам (вугал паміж вектарам і воссю ОХ). Калі вуглы роўныя (адрозніваюцца не больш чым на 0,00001), то сартаваць па даўжыні вектара. Знайсці велічыню максімальнага вугла паміж суседнімі вектарамі.

§ 20. Выкарыстанне бібліятэчных функцый для сартавання і пошуку даных

Оглавление

20.1. Лінейны пошук элемента

20.2. Сартаванне

20.3. Бінарны пошук

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

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