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

Содержание

Задание

Дано множество записей о людях. Каждая запись содержит поля: имя, фамилия, день месяца, месяц и год рождения.

Требуется реализовать указанную в варианте структуру данных (сбалансированное дерево поиска или хэш-таблицу) и операции для работы над ней (вставка и поиск элементов; элемент — запись о человеке). Если совпадающие ключи не допускаются, при вставке нового элемента с существующим ключом он замещает старый элемент; при поиске возвращается один элемент. Если совпадающие ключи допускаются, при вставке нового элемента с существующим ключом он не замещает старый элемент, а “добавляется” к нему; при поиске возвращается вся группа элементов для указанного ключа. Правильность работы алгоритмов проверить с помощью юнит-тестов.

Для реализованной структуры данных замерить время поиска на данных разного размера (использовать генерацию входных данных из предыдущей работы). Сначала все входные данные добавляются в структуру по указанным ключам, далее производится поиск заданного числа ключей (например, 10000 или 100000), время которого замеряется. Ключи для поиска также сгенерировать самостоятельно. Время поиска для тех же данных и ключей сравнить со временем линейного поиска в обычном массиве/списке.

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

В отчет включить:

Псевдокод/описание алгоритмов

Текст программы

Текст юнит-тестов

Результаты замера времени поиска

Работающую программу иметь с собой на занятии

Выдержка из текста

Отчет по программированию, тема "Алгоритмы поиска"

Задание:

Хэш-таблица со связными списками для разрешения коллизий. Ключ: фамилия + первая буква имени. Совпадающие ключи допускаются.В отчете предоставлена работающая программа, юнит-тесты и результаты работы программы (время).

Программа работает верно.

Список использованной литературы

https://docs.google.com/document/d/1zurSefz_X2OgfxDeSV4Mam1bkWargoo9IbZfFkUKOwU/edit#

С этим материалом также изучают

Курсовой проект, Вариант № 30, введение , исходные данные — в таблице вариантов

... исходные данные в таблицы: Список источников ... время делается на использование программы «1С: Бухгалтерия 8.2».Выпускная работа предусматривает изучение введения исходных данных в программу ... управления и ключей управления ... финан-сы: Учебник для вузов. – ...

Разработка системы поиска логических закономерностей в данных с использованием алгоритма ограниченного перебора

... поиска логических закономерностей в данных с использованием алгоритма ограниченного перебора Параллельные программы ... для выработки опти-мальных управленческих решений. В последнее время, ... "Фермопилы") Список литературы ... эффективной при наличии ...

Разработка системы поиска логических закономерностей в данных с использованием алгоритма ограниченного перебора 2

... безопасности для пользователя АРМ 6.4 Расчет заземления Заключение Список литературы Приложение. Исходный текст программ Выдержка из текста Разработка системы поиска логических закономерностей в данных с ...

Решение проблемы программного сбоя при использовании программ отраслевой направленности

... данные в таблицы базы данных, изменяет структуру таблиц (добавление/удаление записей), формирует результирующий отчёт работы программы; ... для теории и практики транспортной логистики. Список ... В настоящее время не ... сбоя при использовании программ отраслевой ...

5 задач по логистике (4 вариант, ГУАП). Постройте транспортную модель для исходных данных задачи № 1.1 при условии, что квартальный спрос в пункте распреде

... вариант, ГУАПЗадача 1Постройте транспортную модель для исходных данных задачи № 1.1 при условии, что квартальный спрос в ... по каждому из возможных маршрутов приведены в таблице 1. Таблица 1 - Стоимость перевозки автомобилей, руб./шт. ...

Поиск внешнеполитического курса России после смутного времени и при правлении Михаила Федоровича Романова.

... международной арене после смутного времени. 2.Взгляды на внешнюю политику отца Филарета при Михаиле Фёдоровиче. Самостоятельная ... географические условия (реки, морские побережья и т.д.) для надежной защиты своей территории, ее расширения, развития ...

Использование технологий обработки текстов и таблиц при составлении рабочих документов PR

... данных для проведения исследованийЗаключениеСписок литературыСодержание Выдержка из текста Использование технологий обработки текстов и таблиц при ... внешнего или внутреннего). Список литературы 1.Алешина И.В. Паблик Рилейшнз для менеджеров и маркетеров ...

Методика решения задачи на интерференцию света с бипризмой Френеля

Готовитесь к контрольной по оптике? Подробно разбираем решение задачи с бипризмой Френеля: от теории интерференции и ключевых формул до пошагового алгоритма.

Блез Паскаль для доказательства справедливости своего закона при стечении любопытствующих экспериментировал с заполненным доверху винным бочонком диа

... Подтвердите свою версию оценочным расчетомВыдержка из текстаБлез Паскаль для доказательства справедливости своего закона при стечении любопытствующих экспериментировал с заполненным доверху винным бочонком ...

Разработка комплекса мероприятий по поиску устройств для несанкционированного съема информации по радио-каналам в защищаемом помещении 6

... поиск устройств для несанкционированного съема информации по радио каналам в защищаемом помещении. Список использованной литературы Список ... защищенном помещении; разработка программы порядка проведения ... полученных в исследовании данных. В данной ...

Похожие записи