Немодифікуючі алгоритми в послідовних контейнерах

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД «УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»

ІНЖЕНЕРНО-ТЕХНІЧНИЙ ФАКУЛЬТЕТ КАФЕДРА КОМП'ЮТЕРНИХ СИСТЕМ ТА МЕРЕЖ

Лабораторна робота №1

з дисципліни «Системне програмне забезпечення»

«Немодифікуючі алгоритми в послідовних контейнерах»

студента

Рикавця Едуарда Васильовича

Ужгород - 2021 р.



Етап 1

Вивчив теорію, проробив і осмислив приклади 1-16 з лекції та даної лабораторної роботи.

Етап 2

1. Створити масив a з n=10 елементів, та масив b з m=10 елементів. Заповнити масив випадковими числами у діапазоні [0;10].

Рис.1. Завдання 1

2. Переписати масив у контейнер 1.

Рис.2. Завдання 2

3. Виконати задачі варіанту над контейнером 1.

Задача

Елементи першої половини послідовності зменшити на 2, а парні елементи другої половини послідовності збільшити на 2. Використати алгоритм for_each.



Лістинг програми:

Рис.3. Лістинг програми №6

Рис.4. Тестування часу №6

Задача №7

Перевірити чи присутній у першій п'ятірці послідовності елемент рівний 4. Використати алгоритм find.



Лістинг програми:

Рис.5. Лістинг програми №7

Рис.6. Тестування часу №7

Рис.7. Тестування часу №7

4. Переписати контейнер 1 у контейнер 2.

Рис.8. Завдання 4.



5. Виконати задачі варіанту над контейнером 2.

Задача

Знайти номер початку останнього входження другої половини послідовності 2 в першу половину послідовності 1. Використати алгоритм find_end.

Лістинг програми:

Рис.9. Лістинг програми №8

Рис.10. Тестування часу №8.



Задача

Знайти перший елемент в другій половині послідовності v, який співпадає із одним з елементів другої половини послідовності t. Використати алгоритм find_first_of.

Лістинг програми:

Рис.11. Лістинг програми №9

Рис.12. Тестування №9



6. Переписати контейнер 2 у контейнер 3.

Рис.13.

7. Виконати задачі варіанту над контейнером 3.

Задача

Знайти перший елемент в другій половині послідовності, що задовольняє умову 5<a<9. Використати алгоритм find_if.

Лістинг програми:

Рис.14. Лістинг програми №10



Рис.15. Тестування №10

Задача

Знайти номер початку першого входження першої половини послідовності y, у другу половину послідовності x. Використати алгоритм search.

Лістинг програми:

Рис.16. Лістинг програми №11

Рис.17. Тестування часу №11



Етап 3

Дослідницька частина роботи. Дослідити час виконання задач варіанту для n,m = 10,10; 100,10; 1000,10; 10000,100; 100000,100; 1000000,1000; 10000000,1000. Заповнити таблицю з результатами дослідження.

		Діапазон функції rand()	Час виконання задач варіанту у сек.
			Контейнер 1	Контейнер 2	Контейнер 3
n	m		6	7	8	9	10	11
10	10	[0;10]	0.0001802	0.0002846	0.0010414	0.0004143	0.0002455	0.0003539
100	10	[0;10]	0.0001699	0.000198	0.0003504	0.0004884	0.0002249	0.0002436
1000	10	[0;10]	0.0001673	0.00015	0.0011681	0.0009209	0.0002091	0.0018318
10000	100	[0;100]	0.0045757	0.0002044	0.0131264	0.0069402	0.0001907	0.0012408
100000	100	[0;100]	0.0425807	0.0002002	0.089782	0.057441	0.0002186	0.0107561
1000000	1000	[0;1000]	0.418706	0.0001781	0.871678	0.506226	0.0001979	0.103881
10000000	1000	[0;1000]	4.9924	0.0001544	10.6923	6.00428	0.0002514	1.19082

Висновок: під час роботи даної лабораторної роботи я знайомився з послідовними контейнерами бібліотеки STL, освоїв немодифікуючі алгоритми, та зіткнувся з такою проблемою:

Дивного виведення часу в Задачі №6, вона виникає при заповнені елементів масива

n, m = (10,10); (100,10); (1000, 100).

Рис.18. Виведення часу

Причиною такого виводу часу скоріше за все являється швидке опрацювання даної програми.

З іншими задачами проблем не виникло, все було зроблено чітко за інструкціями, весь матеріал було переглянуто та виконано за шаблонами прикладів задач наведених в теорії.

бібліотека контейнер алгоритм лістинг

Основні характеристики комп'ютера:

Лістинг програми:

#include <iostream>

#include <vector>

#include <algorithm>

#include <list>

#include <deque>

#include <omp.h>

using namespace std;

const long int n = 10;

const int m = 10;

int maxD = 10;

int a[n];

int b[m];

int main()

{

//Етап 2. Завдання 1.

for (int i = 0; i < n; i++) a[i] = rand() % maxD;

for (int i = 0; i < m; i++) b[i] = rand() % maxD;

//Етап 2. Завдання 2. Переписати масив в deque

deque<int> dq1;

deque<int> dq2;

for (int i = 0; i < n; i++) dq1.push_back(a[i]);

for (int i = 0; i < m; i++) dq2.push_back(b[i]);

// Етап 2. Завдання 3.

// 6 Задача

cout << endl << "Task 6" << endl;

//dq1 = { 2, 3, 4, 2, 5, 4, 7, 1, 6, 5 };

double t1 = omp_get_wtime();

for_each(dq1.begin(), dq1.begin() + dq1.size() / 2, [](int& a) { a -= 2; });

for_each(dq1.begin() + dq1.size() / 2, dq1.end(), [](int& a) { if (a % 2 == 0) a *= 2; });

double t2 = omp_get_wtime();

//for_each(dq1.begin(), dq1.end(), [](int& a) { cout << a << " "; });

cout << endl << "Time: " << t2 - t1 << endl;

// 7 задача

cout << endl << "Task 7" << endl;

t1 = omp_get_wtime();

//dq1 = { 3, 5, 4, 13, 2, 14, 7, 10, 6, 5 };

//dq1 = { 3, 15, 14, 13, 2, 14, 7, 10, 6, 5, 1 };

deque <int>::iterator idq = find(dq1.begin(), dq1.begin() + 5, 4);

if (idq == dq1.begin() + 5) cout << '-' << endl;

else cout << '+' << endl;

t2 = omp_get_wtime();

cout << "Time: " << t2 - t1 << endl;

// Етап 2. Завдання 4.

list<int> l1;

list<int> l2;

for (int i = 0; i < dq1.size(); i++) {

l1.push_back(dq1[i]);

}

for (int i = 0; i < dq2.size(); i++) {

l2.push_back(dq2[i]);

}

// Етап 2. Завдання 5.

// 8 задача

cout << endl << "Task 8" << endl;

t1 = omp_get_wtime();

//l1 = { 2, 1, 4, 2, 1, 5, 7, 1, 2, 1, 5, 2, 1, 0 };

//l2 = { 4, 3, 2, 1 };

list<int>::iterator il1 = l1.begin();

list<int>::iterator il2 = l2.begin();

std::advance(il1, distance(l1.begin(), l1.end()) / 2);

std::advance(il2, distance(l2.begin(), l2.end()) / 2);

list<int>::iterator r = find_end(l1.begin(), il1, il2, l2.end());

if (r == il1)

cout << '-' << endl;

else cout << '+' << std::distance(l1.begin(), r) << endl;

t2 = omp_get_wtime();

cout << "Time: " << t2 - t1 << endl;

// 9 Задача

cout << endl << "Task 9" << endl;

t1 = omp_get_wtime();

//l1 = { 2, 1, 4, 2, 1, 5, 7, 1, 2, 1, 5, 2, 1, 0 };

//l2 = { 4, 3, 2, 1 };

list<int>::iterator iil1 = l1.begin();

list<int>::iterator iil2 = l2.begin();

std::advance(iil1, distance(l1.begin(), l1.end()) / 2);

std::advance(iil2, distance(l2.begin(), l2.end()) / 2);

list<int>::iterator ffo = find_first_of(iil1, l1.end(), iil2, l2.end());

if (ffo == l1.end())

cout << '-' << endl;

else cout << '+' << *ffo << endl;

t2 = omp_get_wtime();

cout << "Time: " << t2 - t1 << endl;

//Етап 2. Завдання 6

vector<int> v1;

vector<int> v2;

list<int>::iterator ilv1 = l1.begin();

list<int>::iterator ilv2 = l2.begin();

for (ilv1; ilv1 != l1.end(); ilv1++) v1.push_back(*ilv1);

for (ilv2; ilv2 != l2.end(); ilv2++) v2.push_back(*ilv2);

//Етап 2. Завдання 7

//Задача 10

cout << endl << "Task 10" << endl;

t1 = omp_get_wtime();

//v1 = { 2, 2, 4, 2, 2, 4, 7, 1, 2, 5, 5, 1, 8, 0, 7, 1 };

vector<int>::iterator vi = find_if(v1.begin() + v1.size() / 2, v1.end(), [](int a) { return a > 5 && a < 9; });

if (vi == v1.end())

cout << "Not found!" << endl;

else

cout << *vi << endl;

t2 = omp_get_wtime();

cout << "Time: " << t2 - t1 << endl;

//Задача 11

cout << endl << "Task 11" << endl;

t1 = omp_get_wtime();

//v1 = { 2, 1, 4, 2, 1, 5, 7, 1, 2, 1, 5, 2, 1, 0 };

//v2 = { 2, 1, 4, 3 };

auto iiv = search(v1.begin() + v1.size() / 2, v1.end(), v2.begin(), v2.begin() + v2.size() / 2);

if (iiv != v1.end())

cout << '+' << (iiv - v1.begin()) << endl;

else

cout << '-' << endl;

t2 = omp_get_wtime();

cout << "Time: " << t2 - t1 << endl;

return 0;}

Размещено на Allbest.ru