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

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

Федеральное государственное бюджетное образовательное учреждение высшего образования

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

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

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

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

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

Проверил:

Чайка А.Д.

Москва 2022

Содержание

3.1. Организация нескольких видов поиска элемента в массиве. 4

6

3.2. Организовать хэшировние и рехэшировние элементов 10

3.3. Решить задачу про ферзей 15

1. Цель работы: Изучить основные алгоритмы поиска элементов в массивах.

2. Задание:

1. Организовать несколько видов поиска элемента в массиве.

2. Организовать хэшировние и рехэшировние элементов

3. Решить задачу про ферзей

3. Ход выполнения лабораторной работы

3.1. Организация нескольких видов поиска элемента в массиве.

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

Код метода бинарного поиска представлен на рисунке 1. Результат работы представлен на рисунке 2.

Рисунок 1 – Код метода бинарного поиска

Рисунок 2 – Результат работы кода

Дерево двоичного поиска для множества чисел S — это размеченное бинарное дерево, каждой вершине которого сопоставлено число из множества S, причем все пометки удовлетворяют следующему простому правилу: «если больше — направо, если меньше — налево». Результат работы метода поиска по бинарному дереву представлен на рисунке 3.

Рисунок 3 – Результат работы кода

Интерполяционный поиск, при котором поиск происходит подобно двоичному поиску, но вместо деления области поиска на две части,  интерполирующий поиск производит оценку новой области поиска  по расстоянию между ключом и текущим значением элемента (примерно оценивает - элемент ближе к концу или началу). Код метода интерполяционного поиска представлен на рисунке 4. Результат работы представлен на рисунке 5.

Рисунок 4 – Код метода интерполяционного поиска

Рисунок 5 – Результат работы кода

Поиск Фибоначчи работает в отсортированном массиве, который сужает возможные местоположения с помощью чисел Фибоначчи. По сравнению с бинарным поиском, поиск Фибоначчи делит массив на две части, размеры которых являются последовательными числами Фибоначчи. Код метода поиска Фибоначчи представлен на рисунке 6. Результат работы представлен на рисунке 7.

Рисунок 6 – Код метода интерполяционного поиска

Рисунок 7 – Результат работы кода

Реализация вставки и удаления числа из массива представлена на рисунке 8. Работа методов представлена на рисунке 9.

Рисунок 8 – Код методов вставки и удаления числа из массива

Рисунок 9 – Результат работы кода

3.2. Организовать хэшировние и рехэшировние элементов

Код класса простого рехеширования, представлен на рисунке 10.

Рисунок 3 – Код класса простого рехеширования

Результат работы кода представлен на рисунке 11.

Рисунок 11 – Результат работы кода

Код класса рехеширования цепочками, представлен на рисунке 12

Рисунок 12 – Код класса рехеширования цепочками

Результат работы кода представлен на рисунке 13.

Рисунок 13 – Результат работы кода

Код класса рехэширования с помощью псевдослучайных чисел представлен на рисунке 14.

Рисунок 14 – Код класса рехэширования с помощью псевдослучайных чисел

Результат работы кода представлен на рисунке 15.

Рисунок 15 – Результат работы кода

3.3. Решить задачу про ферзей

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

Рисунок 16 – Код метода решения задачи

Рисунок 17 – Результат работы кода

4. Ссылка на репозиторий гитхаба

https://github.com/TerraficMint/BST2004_US_Olga__Python_lab2

5. Вывод

Я изучила основные методы поиска элемента в массиве.