Выполнить задание на C++
Практическая работа № 5
Алгоритм поиска в отсортированных массивах
Постановка задачи
Составить программу поиска заданного элемента по ключу в одномерном целочисленном массиве A[n], используя алгоритм согласно варианту индивидуального задания. Провести тестирование программы на исходном массиве, сформированном вводом с клавиатуры. Рабочий массив A сформировать с использованием генератора псевдослучайных чисел. Провести контрольные прогоны программы для размеров массива n = 100, 1000, 10000, 100000 и 1000000 элементов в трех режимах: на массивах, строго убывающих, строго возрастающих и случайных чисел и сделать вывод о зависимости (устойчивости) алгоритма от исходной упорядоченности массива.
Провести эмпирическую (практическую) оценку вычислительной сложности алгоритма, для чего предусмотреть в программе подсчет фактического количества операций сравнения Сф.
Полученные результаты свести в сводную таблицу. Построить в одной координатной плоскости графики зависимости теоретической О(n)=f(С(n)) и эмпирической (Сф(n)) вычислительной сложности алгоритма от количества элементов в массиве n.
Сравнить вычислительную сложность алгоритма с вычислительной сложностью алгоритма последовательного поиска. Экспериментально оценить долю случаев, когда последовательный поиск выполняется быстрее, чем быстрый поиск.
Провести анализ полученных результатов. Сделать выводы о проделанной работе, основанные на полученных результатах.
Сводная таблица результатов
n | f(C) | Cф |
100 |
|
|
1000 |
|
|
10000 |
|
|
100000 |
|
|
1000000 |
|
|
Варианты индивидуальных заданий
№ | Алгоритм |
5.1 | Двоичного поиска |
5.2 | С использованием бинарного дерева поиска |
5.3 | Фибоначчиего поиска |
5.4 | Поиска хэшированием |
5.5 | Поиска по бору |
5.6 | Поиска Рабина-Карпа |
Практическая работа № 6
Алгоритмы поиска строк в тексте
Постановка задачи
Составить программу поиска первого вхождения заданной строки P длиной m символов в тексте S, размером n символов, используя алгоритм согласно варианту индивидуального задания. Уточнение: настоящая задача поиска сводится к нахождению в тексте (массиве) S индекса, начиная с которого строка P полностью совпадает с фрагментом текста S. В частном случае заданная строка может отсутствовать в тексте.
Провести тестирование программы на исходном массиве, сформированном вводом с клавиатуры.
Рабочий текст (массив) сформировать из произвольного текстового файла, например, романа Л.Н. Толстого «Война и мир». Провести контрольные прогоны программы как минимум на трех текстовых файлах различной длины.
Провести эмпирическую (практическую) оценку вычислительной сложности алгоритма, для чего предусмотреть в программе подсчет фактического количества операций посимвольного сравнения Сф и сдвигов подстроки Мф относительно текста.
Полученные результаты свести в сводную таблицу. Построить в одной координатной плоскости графики зависимости теоретической О(n)=f(С+М) и эмпирической (Сф+Мф) вычислительной сложности алгоритма от размера текста (количества элементов в массиве) n.
Сравнить вычислительную сложность алгоритма с вычислительной сложностью алгоритма прямого поиска строки.
Провести анализ полученных результатов. Сделать выводы о проделанной работе, основанные на полученных результатах.
Сводная таблица результатов
n | f(C+М) | Cф+Мф |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Варианты индивидуальных заданий
№ | Алгоритм |
6.1 | Прямого поиска строки |
6.2 | Кнута-Морриса-Пратта |
6.3 | Бойера-Мура |
6.4 | Поиска хэшированием |
Практическое задание №7
Линейные динамические списки
- 1. Однонаправленные списки
Постановка задачи
Определите список операции над списками варианта, включая операцию добавления узла в начало списка, вывода списка. Разработайте для каждой операции функцию с параметрами. Информационная часть узла имеет тип int.
Реализуйте программу решения задачи варианта.
Вариант 1
Даны два линейных однонаправленных списка L1 и L2. Разработать процедуру, которая формирует список L, включив в него по одному разу элементы, значения которых входят хотя бы в один из списков L1 и L2.
Вариант 2
Даны два линейных однонаправленных списка L1 и L2. Разработать процедуру, которая формирует список L, включив в него по одному разу элементы, значения которых входят одновременно в оба списка L1 и L2.
Вариант 3
Даны два линейных однонаправленных списка L1 и L2. Разработать процедуру, которая формирует список L, включив в него по одному разу элементы, значения которых входят в список L1 и не входят в список L2.
Вариант 4
Даны два линейных однонаправленных списка L1 и L2. Разработать процедуру, которая формирует список L, включив в него по одному разу элементы, значения которых входят в один из списков L1 и L2 и в не входят в другой.
- 2. Двунаправленные списки
Постановка задачи
Разработать многомодульную программу, которая демонстрирует выполнение всех операций, определенных вариантом, над линейным двунаправленным динамическим списком.
Требования к разработке.
- Разработать структуру узла списка, структура информационной части узла определена вариантом. Для определения структуры узла списка, используйте тип struct. Сохраните определение структуры узла в заголовочном файле.
- Разработайте функции для выполнения операции над линейным динамическим списком:
- вывод списка в двух направлениях
- поиск узла с заданным значением (операция должна возвращать указатель на узел с заданным значением).
- Дополнительные операции над списком, указанные вариантом оформите в виде функций и включите в отдельный файл с расширением cpp. Подключите к этому файлу заголовочный файл с определением структуры узла.
- Разработайте программу, управляемую текстовым меню, и включите в меню демонстрацию выполнения всех операций задания и варианта.
- Проведите тестирование операций.
- Оцените сложность алгоритма первой дополнительной операции для реализации линейного списка:
- на линейном динамическом списке
- на одномерном массиве.
Примечание. В определении информационной части узла варианта, подчеркнутое поле считать полем ключа.
Варианты
Вариант | Тип информационной части узла списка | Дополнительные Операции |
1 | Номер зач. книжки, Номер группы, Оценка. | Вставить новый узел перед первым узлом с таким же ключом, если такого узла еще нет, то вставить перед первым узлом, у которого ключ больше. Удалить узлы с указанным номером группы. Сформировать новый список из исходного, включив в него узлы с оценкой неуд, исключив их при этом из исходного списка. |
2
| Номер телефона (из 7 цифр), время разговора (целое число), номер телефона вызываемого абонента. | Добавить новый узел в список, упорядочивая узлы по первым четырем цифрам телефона в порядке возрастания. Удалить последний узел с заданным значением телефона. Подсчитать суммарное время разговора с заданного телефона. |
3 | Номер абонемента, Название книги, дата выдачи, дата возврата, дата фактического возврата. | Вставить новый узел в список после последнего узла с таким же номером абонента(дата фактического возврата еще не заполнена). Изменить значение поля фактической даты возврата по указанной книге, указанного абонемента. Удалить узлы, в которых дата возврата и дата фактического возврата совпадают. Определить количество книг, заданного абонемента. |
4 | Номер мед. полиса, Дата обращения, Код диагноза (число). | Вставка нового узла перед первым узлом с заданным значением Мед. полиса, если такого нет, то узел вставить в конец списка. Удаление из списка всех узлов с заданным значением Кода диагноза. Переместить все узлы с одинаковым мед. полисом в новый список. Определить количество обращений в одну и туже дату с одним и тем же диагнозом. |
5 | Номер счета в банке, дата, вид операции (приход или расход), сумма вклада. | Вставка нового узла перед первым узлом. Удаление сведений по счету (всех узлов), у которого общая сумма вклада равна нулю ( сумма по приходу, минус сумма по расходу). Создать новый список из исходного, которого будет содержать остаток по всем видам операций одного счета, указав вид операции – приход, и текущую дату. |
6 | Номер автобусного маршрута, время отправления (целое число), номер автобуса, стоимость одной поездки, дата отправления. | Вставить новый узел после последнего узла с заданным номером автобуса. Удалить все узлы заданного автобуса. Подсчитать, сколько раз автобус выходил на маршрут в течении заданного дня. |
- 400 руб.
- Задача
- C++
- Нет
- Visual Studio
- Есть
На нашем сайте есть работы, которые включают в себя несколько задач. Если Вам необходима только одна или несколько задач из всей работы, то вам нет необходимости покупать работу целиком. Мы можем продать задачи по отдельности. Для этого обратитесь к нам удобным для Вас способом.
Также если вдруг какая-то работа будет не соответствовать описанию или вы найдете ошибку, то мы всегда готовы исправить проблему в обговорённые с Вами сроки.