лабы
.docЛабораторная работа №1
Задание: Имеются два упорядоченных по возрастанию (предыдущий элемент меньше последующего) массива. Требуется получить третий упорядоченный по возрастанию массив, путем слияния первых двух.
Комментарии:
-
Самостоятельной подзадачей является формирование исходных массивов. Простое использование random не подходит, т.к. массивы должны быть упорядоченными. Поэтому нужно использовать random не для формирования очередного элемента, а для формирования приращения следующего элемента в сравнении с предыдущим (приращение должно быть случайным, лежащим в небольшом диапазоне, например от 0 – 10). Для контрольных запусков предусмотреть также ручной ввод массивов.
-
Длина третьего массива должна быть, что очевидно, равна сумме двух длин двух первых.
-
Элементы под текущими для каждого массива индексами сравниваются, и меньший по значению записывается в третий массив. При этом индекс массива, из которого элемент был скопирован в третий массив, должен увеличиться.
-
Может возникнуть ситуация, когда один массив закончился, а второй еще нет. Поэтому в программе на такой случай должен быть организован цикл записи элементов из неиспользованного «хвоста» первого или второго массива.
Лабораторная работа №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%). Для этого нужно сначала разместить в таблице нужное число строк, а потом для каждой строки подсчитать число шагов, выполняемых при ее поиске. Все вычисления провести для трех вариантов: линейные пробы, квадратичные пробы и двойное хеширование.