Министерство цифрового развития, связи и массовых коммуникаций

Российской Федерации Ордена Трудового Красного Знамени

федеральное государственное бюджетное образовательное

учреждение высшего образования

Московский технический университет связи и информатики

Кафедра «Математическая кибернетика и информационные технологии»

Лабораторная работа №2

«Методы поиска»

по дисциплине

«Структуры и алгоритмы обработки данных»

Москва 2022

Содержание

1 Цель работы 3

2 Задание на лабораторную работу 3

3 Ход работы 4

3.1 Задание №1 4

3.2 Задание №2 8

3.3 Задание №3 12

4 Вывод 13

Список использованных источников 13

1 Цель работы

Реализовать различные алгоритмы поиска числа в массиве, функции рехэширования и метод цепочек. Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого».

2 Задание на лабораторную работу

Задание №1

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

Задание №2

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

Задание №3

Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого». Подразумевается, что ферзь бьёт все клетки, расположенные по вертикалям, горизонталям и обеим диагоналям

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

3 Ход работы

3.1 Задание №1

Была создана функция генерации и сортировки массива generate_mas. Код функции представлен на рисунке 1.

Рисунок 1-generate_mas

Далее мной были реализованы различные алгоритмы поиска. На рисунке 2 представлен бинарный поиск, на рисунке 3 представлен алгоритм бинарного дерева, на рисунке 4 представлен фиббоначиев поиск, на рисунке 5 представлен интерполяционный поиск.

Рисунок 2-бинарный поиск

Рисунок 3-Бинарное дерево

Рисунок 4-Фиббоначиев поиск

Рисунок 5-Интерполяционный поиск

3.2 Задание №2

Были реализованы алгоритмы простого рехэширования, и рехэширования при помощи псевдослучайных чисел. Код представлен на рисунке 6-7.

Рисунок 6-Алгоритмы рехэширования

Рисунок 7-Алгоритмы рехэширования

Был реализован метод цепочек. Его реализация представлена на рисунке 8.

Рисунок 8-Метод цепочек

3.3 Задание №3

Был реализован алгоритм расстановки 8 ферезей на шахматной доске. Код представлен на рисунке 9.

Рисунок 9-Алгоритм расстановки ферзей

4 Вывод

Реализовать различные алгоритмы поиска числа в массиве, функции рехэширования и метод цепочек. Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого».

Список использованных источников

1) ГОСТ 7.32.2017 Система стандартов по информации, библиотечному и издательскому делу. Отчет о научно-исследовательской работе. Структура и правила оформления. – М.: Стандартинформ, 2017, - 27 с.