ГлавнаяПрограммирование → Выполнить задание на C++

Выполнить задание на C++

Задание

Практическая работа № 5

Алгоритм поиска в отсортированных массивах

 

Постановка задачи

Составить программу поиска заданного элемента по ключу в одномерном целочисленном массиве A[n], используя алгоритм согласно варианту индивидуального задания. Провести тестирование программы на исходном массиве, сформированном вводом с клавиатуры. Рабочий массив A сформировать с использованием генератора псевдослучайных чисел. Провести контрольные прогоны программы для размеров массива n = 100, 1000, 10000, 100000 и 1000000 элементов в трех режимах: на массивах, строго убывающих, строго возрастающих и случайных чисел и сделать вывод о зависимости (устойчивости) алгоритма от исходной упорядоченности массива.

Провести эмпирическую (практическую) оценку вычислительной сложности алгоритма, для чего предусмотреть в программе подсчет фактического количества операций сравнения Сф.

Полученные результаты свести в сводную таблицу. Построить в одной координатной плоскости графики зависимости теоретической О(n)=f(С(n)) и эмпирической (Сф(n)) вычислительной сложности алгоритма от количества элементов в массиве n.

Сравнить вычислительную сложность алгоритма с вычислительной сложностью алгоритма последовательного поиска. Экспериментально оценить долю случаев, когда последовательный поиск выполняется быстрее, чем быстрый поиск.

Провести анализ полученных результатов. Сделать выводы о проделанной работе, основанные на полученных результатах.

 

Сводная таблица результатов

n

f(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. 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 и в не входят в другой.

 

  1. 2.    Двунаправленные списки

Постановка задачи

Разработать многомодульную программу, которая демонстрирует выполнение всех операций, определенных вариантом, над линейным двунаправленным динамическим списком.

Требования к разработке.

  1. Разработать структуру узла списка, структура информационной части узла определена вариантом. Для определения структуры узла списка, используйте тип struct. Сохраните определение структуры узла в заголовочном файле.
  2. Разработайте функции для выполнения операции над линейным динамическим списком:
  • вывод списка в двух направлениях
  • поиск узла с заданным значением (операция должна возвращать указатель на узел с заданным значением).
  1. Дополнительные операции над списком, указанные вариантом оформите в виде функций и включите в отдельный файл с расширением cpp. Подключите к этому файлу заголовочный файл с определением структуры узла.
  2. Разработайте программу, управляемую текстовым меню, и включите в меню  демонстрацию выполнения всех операций задания и варианта.
  3. Проведите тестирование операций.
  4. Оцените сложность алгоритма первой дополнительной операции для реализации линейного списка:
  • на линейном динамическом списке
  • на одномерном массиве.

 

Примечание. В определении информационной части узла варианта, подчеркнутое поле считать полем ключа.

Варианты

Вариант

Тип информационной части узла списка

Дополнительные Операции

1

Номер зач. книжки, Номер группы, Оценка.

Вставить новый узел перед первым узлом с таким же ключом, если такого узла еще нет, то вставить перед первым узлом, у которого ключ больше.

Удалить узлы с указанным номером группы.

Сформировать новый список из исходного,  включив в него узлы с оценкой неуд, исключив их при этом из исходного списка.

2

 

 

Номер телефона (из 7 цифр), время разговора (целое число), номер телефона вызываемого абонента.

Добавить новый узел в список, упорядочивая узлы по первым четырем цифрам телефона в порядке возрастания.

Удалить последний узел  с заданным значением телефона.

Подсчитать суммарное время разговора с заданного телефона.

3

Номер абонемента, Название книги, дата выдачи, дата возврата, дата фактического возврата.

Вставить новый узел  в список после последнего узла с таким же номером абонента(дата фактического возврата еще не заполнена).

Изменить значение поля фактической даты возврата по указанной книге, указанного абонемента.

Удалить узлы, в которых дата возврата и дата фактического возврата совпадают.

Определить количество книг, заданного абонемента.

4

Номер мед. полиса, Дата обращения, Код диагноза (число).

Вставка нового узла перед первым узлом с заданным значением Мед. полиса, если такого нет, то узел вставить в конец списка.

Удаление из списка всех узлов с заданным значением Кода диагноза.

Переместить все узлы с одинаковым  мед. полисом в новый список.

Определить количество обращений в одну и туже дату с одним и тем же диагнозом.

5

Номер счета в банке, дата, вид операции (приход или расход), сумма вклада.

Вставка нового узла перед первым узлом.

Удаление сведений по счету (всех узлов), у которого общая сумма вклада равна нулю ( сумма по приходу, минус сумма по расходу).

Создать новый список из исходного, которого будет содержать остаток по всем видам операций одного счета, указав вид операции – приход, и текущую дату. 

6

Номер автобусного маршрута, время отправления (целое число), номер автобуса, стоимость одной поездки, дата отправления.

Вставить новый узел после последнего узла с заданным номером автобуса.

Удалить все узлы заданного автобуса.

Подсчитать, сколько раз автобус выходил на маршрут в течении заданного дня.

 

 

Детали товара
  • 400 руб.
  • Задача
  • C++
  • Нет
  • Visual Studio
  • Есть
Изображения товара
Обратите внимание

На нашем сайте есть работы, которые включают в себя несколько задач. Если Вам необходима только одна или несколько задач из всей работы, то вам нет необходимости покупать работу целиком. Мы можем продать задачи по отдельности. Для этого обратитесь к нам удобным для Вас способом.

Также если вдруг какая-то работа будет не соответствовать описанию или вы найдете ошибку, то мы всегда готовы исправить проблему в обговорённые с Вами сроки.