МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ “БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ”
ФАКУЛЬТЕТ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ ИНФОКОММУНИКАЦИОННЫЕ СИСТЕМЫ (СИСТЕМЫ ИНФОКОММУНИКАЦИЙ)
ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ (С++)
Работу выполнил: студент 1 курса 2630401 группы
Преподаватель: Гуревич Ольга Викторовна
г. Минск, 2023
Вариант 4 Лабораторная работа No1
Числа Фибоначчи определяются следующим образом: Fb(0) = 0; Fb(1) = 1; Fb(n) = Fb(n – 1) + Fb(n – 2). Определить Fb(n). #include <iostream> using namespace std; int fibR(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return fibR(n - 1) + fibR(n - 2); } } int fibN(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { int prev = 0; int curr = 1; for (int i = 2; i <= n; i++) { int next = prev + curr; prev = curr; curr = next; } return curr; } } int main() { int n; cout << "num fib: "; cin >> n; cout << "Rec(" << n << ") = " << fibR(n) << endl << endl; cout << "NoRec(" << n << ") = " << fibN(n) << endl; return 0; } 1. Какая функция называется рекурсивной? Это функция, которая в процессе выполнения обращается сама к себе.
2. Может ли в реализации рекурсивной функции существовать несколько операторов передачи управления return? Да, может иметь несколько операторов, которые могут вернуть значения различных ветвей.
Лабораторная No2
Написать программу обработки файла данных, состоящих из структур, в которой реализованы следующие функции: стандартная обработка файла (создание, просмотр, добавление); линейный поиск в файле; сортировка массива (файла) методами прямого выбора и QuickSort; двоичный поиск в отсортированном массиве. В справочной автовокзала хранится расписание движения автобусов. Для каждого рейса указаны его номер, пункт назначения, время отправления и прибытия. Вывести информацию о рейсах, которыми можно воспользоваться для прибытия в пункт назначения раньше заданного времени. Ключ: время прибытия. #include <iostream> #include <string> using namespace std; struct Bus { int number; string destination; string departureTime; string arrivalTime; } ; int menu() { int n; cout << "\t\t\t MENU\n"; cout << "\t1.ADD\n"; cout << "\t2.LIST TRIPS\n"; cout << "\t3.LINE SEARCH\n"; cout << "\t4.SELECTION SORT\n"; cout << "\t5.QUICK SORT\n"; cout << "\t6.BINARY SEARCH\n"; cout << "\t0.EXIT\n\n"; cout << "\tSELECT(0 - 6) :"; cin >> n; return n; } void addTrip(Bus trips[], int& numTrip, int maxTrips) { if (numTrip >= maxTrips) { cout << "Error!" << endl; return; } cout << "New trip:" << endl; cout << "Number: "; cin >> trips[numTrip].number; cout << "Destination: ";
cin >> trips[numTrip].destination; cout << "Departure time: "; cin >> trips[numTrip].departureTime; cout << "Arrival time: "; cin >> trips[numTrip].arrivalTime; numTrip++; } void printTrips(Bus trips[], int numTrip) { cout << "Unsorted trips list:" << endl; for (int i = 0; i < numTrip; i++) { cout << "Bus " << trips[i].number << " to " << trips[i].destination << " departs at " << trips[i].departureTime << " and arrives at " << trips[i].arrivalTime << endl; } cout << endl; } void linearSearch(Bus trips[], int numTrip, string targetTime) { bool found = false; cout << "Trips arriving before " << targetTime << ":" << endl; for (int i = 0; i < numTrip; i++) { if (trips[i].arrivalTime < targetTime) { found = true; cout << "Bus " << trips[i].number << " to " << trips[i].destination << " departs at " << trips[i].departureTime << " and arrives at " << trips[i].arrivalTime << endl; } } if (!found) { cout << "Not found " << targetTime << endl; } } void selectionSort(Bus arr[], int n) { for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j].arrivalTime < arr[minIndex].arrivalTime) { minIndex = j; } } if (minIndex != i) { swap(arr[i], arr[minIndex]); }
} } void quickSort(Bus* trips, int left, int right) { int i = left, j = right; Bus temp; Bus pivot = trips[(left + right) / 2]; while (i <= j) { while (trips[i].number < pivot.number) { i++; } while (trips[j].number > pivot.number) { j--; } if (i <= j) { temp = trips[i]; trips[i] = trips[j]; trips[j] = temp; i++; j--; } } if (left < j) { quickSort(trips, left, j); } if (i < right) { quickSort(trips, i, right); } } void binarySearch(Bus trips[], int numTrip, string targetTime) { quickSort(trips, 0, numTrip - 1); int left = 0, right = numTrip - 1; bool found = false; while (left <= right) { int middle = (left + right) / 2; if (trips[middle].arrivalTime == targetTime) { found = true; cout << "Found: Bus " << trips[middle].number << " to " << trips[middle].destination << " departs at " << trips[middle].departureTime << " and arrives at " << trips[middle].arrivalTime << endl; break; } else if (trips[middle].arrivalTime < targetTime) { left = middle + 1; }
else { right = middle - 1; } } if (!found) { cout << "Not found " << targetTime << endl; } } int main() { const int maxTrips = 100; int numTrip = 5; Bus trips[maxTrips]; string targetTime; trips[0] = { 134, "Grodno", "19:00", "22:00" }; trips[1] = { 211, "Gomel", "11:00", "12:00" }; trips[2] = { 31123, "Brest", "18:00", "19:00" }; trips[3] = { 44, "Vitebsk", "11:00", "18:00" }; trips[4] = { 5, "Mogilev", "12:00", "21:00" }; while (true) { switch (menu()) { case 1: addTrip(trips, numTrip, maxTrips); break; case 2: printTrips(trips, numTrip); break; case 3: cout << "Enter arrival time: "; cin >> targetTime; linearSearch(trips, numTrip, targetTime); break; case 4: selectionSort(trips, numTrip); break; case 5: quickSort(trips, 0, numTrip - 1); break; case 6: cout << "Enter arrival time: "; cin >> targetTime; binarySearch(trips, numTrip, targetTime); break; case 0: system("pause"); return 0;
break; }; } }
1. Устойчив ли интерполяционный поиск на неравномерном объеме ин- формации?
Если ключи в массиве распределены неравномерно, то интерполяционный поиск может быть неустойчивым. 2. Какая сложность у быстрой сортировки? За счет чего она достигается? Сложность быстрой сортировки в среднем составляет от O(n log n) до O(n^2) (маловероятно). Такая сложность достигается благодаря тому, что в каждом рекурсивном вызове массив делится на две примерно равные части, и это происходит до тех пор, пока массивы не достигнут минимального размера, затем происходит слияние этих частей.
Лабораторная No3
Написать программу по созданию, добавлению, просмотру и решению приведенных далее задач (в рассмотренных примерах это действие отсутствует) для однонаправленного линейного списка типа Stack. Реализовать сортировку стека методами, рассмотренными в подразделе 3.1. В созданном списке поменять местами крайние элементы. #include <iostream> #include <locale> #include <cstdlib> using namespace std; struct Stack { int info; Stack* next; } *stackBegin, * t; Stack* InStack(Stack*, int); void Del_First(Stack**); void View(Stack*); void Del_All(Stack**); void Sort_p(Stack**); void Sort_info(Stack**); void Swap(Stack**); Stack* InStack(Stack* p, int in) { Stack* t = new Stack; t->info = in; t->next = p; return t; } void Del_First(Stack** p) { Stack* t = *p; *p = (*p)->next;
delete t; } void View(Stack* p) { Stack* t = p; while (t != NULL) { cout << " " << t->info << endl; t = t->next; } } void Sort_p(Stack** p) { Stack* t = NULL, * t1, * r; *p = InStack(*p, 0); if ((*p)->next->next == NULL) { Del_First(p); return; } do { for (t1 = *p; t1->next->next != t; t1 = t1->next) if (t1->next->info > t1->next->next->info) { r = t1->next->next; t1->next->next = r->next; r->next = t1->next; t1->next = r; } t = t1->next; } while ((*p)->next->next != t); Del_First(p); } void Sort_info(Stack** p) { Stack* t = NULL, * t1; int r; do { for (t1 = *p; t1->next != t; t1 = t1->next) if (t1->info > t1->next->info) { r = t1->info; t1->info = t1->next->info; t1->next->info = r; } t = t1; } while ((*p)->next != t); } void Swap(Stack** p) { if (*p == NULL || (*p)->next == NULL) return; Stack* prev = NULL, * curr = *p; while (curr->next != NULL) { prev = curr; curr = curr->next;
} if (prev != NULL) prev->next = *p; Stack* tmp = (*p)->next; (*p)->next = curr->next; curr->next = tmp; *p = curr; } void Del_All(Stack** p) { while (*p != NULL) { t = *p; *p = (*p)->next; delete t; } } int main() { int i, in, n, kod; while (true) { cout << "\n\t1. CREATE\n\t2. ADD\n\t3. VIEW\n\t4. DEL\n\t5. CHANGE ADDRES\n\t6. CHANGE DATA\n\t7. SWAP\n\t0. EXIT \n\t\t: "; cin >> kod; switch (kod) { case 1: case 2: if (kod == 1 && stackBegin != NULL) { cout << "Clear Memory!" << endl; break; } cout << "Elements inside stack?: "; cin >> n; for (i = 1; i <= n; i++) { in = rand() % 20; stackBegin = InStack(stackBegin, in); } if (kod == 1) cout << "Created " << n << endl; else cout << "Add " << n << endl; break; case 3: if (!stackBegin) { cout << "Stack enmpty!" << endl; break; } cout << "Stack" << endl; View(stackBegin); break; case 4: Del_All(&stackBegin); cout << "Memory Free!" << endl;
break; case 5: if (!stackBegin) { cout << "Stack enmpty!" << endl; break; } Sort_p(&stackBegin); cout << "Sorted!" << endl; View(stackBegin); break; case 6: if (!stackBegin) { cout << "Stack enmpty!" << endl; break; } Sort_info(&stackBegin); cout << "Sorted!" << endl; View(stackBegin); break; case 7: if (!stackBegin) { cout << "Stack enmpty!" << endl; break; } Swap(&stackBegin); cout << "Swaped!" << endl; View(stackBegin); break; case 0: if (stackBegin != NULL) Del_All(&stackBegin); return 0; } } } 1. Что такое стек? Это структура данных, которая представляет собой упорядоченный набор элементов, где добавление и удаление новых элементов происходит с одного конца. Этот конец называется вершиной стека работает по принципу "последним вошел - первым вышел" (LIFO, Last-In-First-Out). Это означает, что последний добавленный элемент будет первым удаленным, а первый добавленный элемент будет последним удаленным. 2. Что такое рекурсивный тип данных? Это тип данных, который содержит в себе самого себя. Такой тип данных может использоваться для определения структур данных, которые могут содержать вложенные элементы того же типа.
3. Возможно ли удалить из стека элемент, не являющийся вершиной, при этом не потеряв основной список? Невозможно удалить из стека элемент, не являющийся вершиной, при этом не потеряв основной список, только элемент на вершине стека может быть удален. Нужно сначала извлечь все элементы, находящиеся выше этого элемента, чтобы достичь его, а затем вернуть все эти элементы обратно в стек после удаления нужного элемента.
Лабораторная No4
Написать программу по созданию, добавлению (в начало, в конец), просмотру (с начала, с конца) и решению приведенной в подразделе 3.3 задачи для двунаправленных линейных списков. В созданном списке поменять местами крайние элементы #include <iostream> #include <locale> #include <cstdlib> using namespace std; struct Spis2 { int info; Spis2* next, *prev; } *beginS, *endS, *t; void Create_Spis2(Spis2**, Spis2**, int); void Add_Spis2(int, Spis2**, Spis2**, int); void View_Spis2(int, Spis2*); void Del_All(Spis2**); void Swap(Spis2** b, Spis2** e); void Create_Spis2(Spis2** b, Spis2** e, int in) { t = new Spis2; t->info = in; t->next = t->prev = NULL; *b = *e = t; } void Add_Spis2(int kod, Spis2** b, Spis2** e, int in) { t = new Spis2; t->info = in; if (kod == 0) { t->prev = NULL; t->next = *b; (*b)->prev = t; *b = t; } else { t->next = NULL; t->prev = *e; (*e)->next = t; *e = t;
} } void View_Spis2(int kod, Spis2 * t) { while (t != NULL) { cout << t->info << endl; if (kod == 0) t = t->next; else t = t->prev; } } void Del_All(Spis2** b) { if ((*b) == NULL) return; Del_All(&((*b) -> next)); cout << "delete" << (*b)->info << endl; delete (*b); *b = NULL; } void Swap(Spis2** b, Spis2** e) { if (*b == NULL) { return; } if (*b == *e) { return; } Spis2* last = *b; while (last->next != NULL) { last = last->next; } int temp = (*b)->info; (*b)->info = last->info; last->info = temp; } int main() { int n, i, in, kod, kod1; char Str[2][10] = { "Begin ", "End " }; while (true) { cout << "\n\t1. Create\n\t2. Add\n\t3. View\n\t4. Del\n\t5. Swap\n\t6. Random\n\t0. EXIT \n\t: "; cin >> kod; switch (kod) { case 1: if (beginS != NULL) { cout << "Clear Memory!" << endl; break; } cout << "Begin value : "; cin >> in;
Create_Spis2(&beginS, &endS, in); cout << "Create Begin = " << beginS->info << endl; break; case 2: cout << "Input value: "; cin >> in; cout << "0. Add to Begin, 1. Add to End : "; cin >> kod1; Add_Spis2(kod1, &beginS, &endS, in); if (kod1 == 0) t = beginS; else t = endS; cout << "Add to " << Str[kod1] << " " << t->info << endl; break; case 3: if (!beginS) { cout << "Stack empty!" << endl; break; } cout << "0. View Begin 1. View End:"; cin >> kod1; if (kod1 == 0) { t = beginS; cout << "Begin" << endl; } else { t = endS; cout << "End" << endl; } View_Spis2(kod1, t); break; case 4: Del_All(&beginS); cout << "Memory Free!" << endl; break; case 5: Swap(&beginS, &endS); cout << "Swapped!" << endl; View_Spis2(kod1, t); break; case 6: cout << "Elements inside list?: "; cin >> n; cout << "0. Add to Begin, 1. Add to End : "; cin >> kod1; for (i = 1; i <= n; i++) { in = rand() % 30 - 20; Add_Spis2(kod1, &beginS, &endS, in); if (kod1 == 0) t = beginS; else t = endS; cout << "Add to " << Str[kod1] << " " << t->info << endl; } break; case 0: if (beginS != NULL)
Del_All(&beginS); return 0; default: cout << "Wrong!" << endl; break; } } } 1. Что такое однонаправленная очередь? Это структура данных, которая позволяет хранить элементы в порядке их добавления и извлекать их в порядке их добавления. 2. Что такое двунаправленная очередь? Это структура данных, которая позволяет хранить, добавлять и удалять элементы с обоих концов очереди. 3. Где, на ваш взгляд, удобнее всего использовать динамические линейные списки? Динамические линейные списки могут быть очень полезными в тех случаях, когда нужно хранить набор данных переменной длины и/или когда нужно часто добавлять или удалять элементы в середине списка.
Лабораторная No5
Написать программу формирования ОПЗ и расчета полученного выраже ния. Разработать удобный интерфейс ввода исходных данных и вывода резуль татов. Работу программы проверить на конкретном примере.
#include <iostream> #include <cmath> #include <string> using namespace std; struct Stack { char info; Stack* next; }; int Pr(char); Stack* Add(Stack*, char); Stack* Del(Stack*, char*); void Result(string, Stack*&); double Arr[201]; char zn[] = { 'a', 'b', 'c', 'd', 'e', 'f'}; int cou; int Pr(char a) { switch (a) { case '^': return 4; case '*': case '/': return 3;
case '-': case '+': return 2; case '(': return 1; default: break; } return 0; } Stack* Add(Stack* p, char in) { Stack* t = new Stack; t->info = in; t->next = p; return t; } Stack* Del(Stack* p, char* out) { Stack* t = p; (*out) = p->info; p = p->next; delete t; return p; } void Result(string opz, Stack*& begin) { char ch, ch1 = ' ', ch2 = ' ', chr = 'z' + 1; double op1 = 0, op2 = 0, res = 0; for (int i = 0; i < opz.size(); i++) { ch = opz[i]; if (ch >= 'a' && ch <= 'z') { begin = Add(begin, ch); } else if (ch == ' ') continue; else { begin = Del(begin, &ch1); begin = Del(begin, &ch2); op1 = Arr[int(ch1)]; op2 = Arr[int(ch2)]; switch (ch) { case '+': res = op2 + op1; break; case '-': res = op2 - op1; break; case '*': res = op2 * op1; break; case '/': res = op2 / op1; break; case '^': res = pow(op2, op1); break; default: break; } Arr[int(chr)] = res; begin = Add(begin, chr); chr++; } } cout << endl << "Result: " << res << endl;
return; } int main() { Stack* beg = NULL; char ss, a = ' '; string prev, act; cout << "Input exp: "; getline(cin, prev); int len = prev.size(), k; for (k = 0; k < len; k++) { ss = prev[k]; if (ss == '(') { beg = Add(beg, ss); } else if (ss == ')') { while (beg != NULL && beg->info != '(') { beg = Del(beg, &a); act += a; //act += " "; } if (beg != NULL) { beg = Del(beg, &a); } else { cout << "Error" << endl; return 0; } } else if (ss >= 'a' && ss <= 'z') { cou++; act += ss; } else if (ss == '*' || ss == '/' || ss == '+' || ss == '-' || ss == '^') { while (beg != NULL && Pr(beg->info) >= Pr(ss)) { beg = Del(beg, &a); act += a; } beg = Add(beg, ss); } } while (beg != NULL) { beg = Del(beg, &a); act += a; } cout << "OPZ: " << act << endl; char ch; for (int i = 0; i < cou; i++) {
ch = zn[i]; cout << "Add " << ch << " = "; cin >> Arr[int(ch)]; } Result(act, beg); return 0; } 1. Что такое постфиксная запись? Это запись оператора после операнда. Использование оператора происходит после использовании операнда в выражении. 2. Что такое инфиксная запись? Это наиболее распространенный и классический способ записи выражений, в котором оператор расположен между двумя операндами. 3. Где, на ваш взгляд, могут быть применены алгоритмы, реализующие обратную польскую запись? ОПЗ применяется, где требуется обработка и вычисление математических выражений, т.к она предоставляет удобную и компактную форму для обработки и вычисления.
