лабы

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

Задание: Имеются два упорядоченных по возрастанию (предыдущий элемент меньше последующего) массива. Требуется получить третий упорядоченный по возрастанию массив, путем слияния первых двух.

Комментарии:

1. Самостоятельной подзадачей является формирование исходных массивов. Простое использование random не подходит, т.к. массивы должны быть упорядоченными. Поэтому нужно использовать random не для формирования очередного элемента, а для формирования приращения следующего элемента в сравнении с предыдущим (приращение должно быть случайным, лежащим в небольшом диапазоне, например от 0 – 10). Для контрольных запусков предусмотреть также ручной ввод массивов.

2. Длина третьего массива должна быть, что очевидно, равна сумме двух длин двух первых.

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

4. Может возникнуть ситуация, когда один массив закончился, а второй еще нет. Поэтому в программе на такой случай должен быть организован цикл записи элементов из неиспользованного «хвоста» первого или второго массива.

Лабораторная работа №2 «Внутренние сортировки»

Задание:

Требуется реализовать 3 алгоритма сортировки массивов:

• сортировка методом «пузырька»

• сортировка вставками

• сортировка Шелла

Программа должна последовательно выполнять все 3 сортировки для одинаковых массивов целых неотрицательных чисел по заданной длине и типу массива. Типы массивов:

• упорядоченные по возрастанию,

• упорядоченные по убыванию,

• случайные.

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

Для составленных алгоритмов нужно провести сравнение быстродействия всех сортировок при размерности массивов в 50000, 100000, 500000, 1000000, 5000000, 10000000 элементов и построить графики зависимости времени работы от числа точек (в Excel). Сделать предположение о характере зависимости времени сортировки от размерности массива (квадратичный, субквадратичный, логарифмический, линейный и т.д.).

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

Задание:

Требуется построить хеш-таблицу, для поиска в которой используется метод открытой адресации (размещение и поиск элементов – обязательно, удаление – желательно). Длина таблицы q – простое число в диапазоне 10-20 тысяч. Таблица строится для набора случайных символьных строк длиной 1-20 символов и хранит номера или адреса этих строк. Хеш-функция для строки S длины L:

f(S) = ((…(S[1] * 31 + S[2]) * 31 + …+S[L-1]) * 31 +S[L]) mod q.

Необходимо вычислить среднюю трудоемкость поиска при различной заполненности таблицы (например, 25, 50, 75, 90 и 99%). Для этого нужно сначала разместить в таблице нужное число строк, а потом для каждой строки подсчитать число шагов, выполняемых при ее поиске. Все вычисления провести для трех вариантов: линейные пробы, квадратичные пробы и двойное хеширование.