Формулировка задания: 1. Разработка алгоритма хеш-функции для реализации таблиц идентификаторов:
a. Разработайте программу на выбранном языке программирования, генерирующую 400 случайных идентификаторов (начинаются с символа латиницы и имеют случайную длину), и сохраните их в файл ID.txt.
b. Выберите две любые хеш-функции на основе открытых источников или предложенной для практики литературы. Диапазон значений хеш-функций должен лежать в пределах от 1 до 1000.
c. Реализуйте вычисление хеш-функций на выбранном языке программирования.
d. Реализуйте чтение идентификаторов с файла ID.txt, вычисление для них хеш-функции и сохранение в массив M_ID в ячейку с номером полученного хеш-значения идентификатора (для которого вычислялась хеш-функция).
e. Если в данном элементе массива уже есть идентификатор (коллизия), то добавьте новый идентификатор через разделитель к имеющемуся в элементе массива. Одновременно занесите оба идентификатора в отдельный массив M_Col в порядке их обнаружения.
f. По окончании чтения всего списка входных идентификаторов выведите массивы M_Col и M_ID в отдельные файлы с расширением txt.
• Файл M_ID должен иметь запись всех ячеек массива в порядке возрастания с указанием в первом столбце номера элемента массива. Пустые элементы также подлежат выводу в файл.
• Файл M_Col должен содержать номер элемента массива, хеш-значение и список идентификаторов.
• В конце файла должно быть вычислено отношение количества коллизий к количеству идентификаторов в %.
• Расчет хеш-значений должен быть выполнен для двух хеш-функций.
g. Проведите сравнение полученных результатов на эффективность хеш-функций с точки зрения возникновения коллизий.
2. Разработка и реализация модуля по созданию таблицы идентификаторов:
a. Разработайте программу, реализующую создание таблицы идентификаторов по заданным алгоритмам (один из них на основе хеш-функции, взятой из предыдущей работы). В качестве реализации возьмите за основу автоматное программирование.
b. Добавьте в программу глобальный счетчик для подсчета затраченных элементарных тактов процессора с целью исследования эффективности разработанной программы.
c. Выполните исследование эффективности работы разработанной программы с подсчета затраченных элементарных операций при заполнении таблицы идентификаторов на 25, 50, 75 и 100 %.
d. Представьте сравнительный анализ эффективности работы разработанной программы в виде электронной таблицы с получением выводов по данным алгоритмам реализации.
const n=20;
var
a:array[1..n] of integer;
i,k,s:integer;
begin
Randomize;
writeln('Исходный массив:');
for i:=1 to n do begin
a[i]:=Random(51)-25;
Write(a[i]:4)
end;
writeln;
write('K = '); readln(k);
s:=0;
for i:=1 to n do
if a[i] mod k = 0 then s:=s+a[i];
Writeln('s = ',s);
end.
Пример:
Исходный массив:
18 -24 -4 -21 15 19 18 -16 -1 -8 7 -21 21 22 -24 -4 18 -16 24 4
K = 3
s = 24
2.
const n=10;
var
a:array[1..n] of integer;
i:integer;
begin
Randomize;
writeln('Исходный массив:');
for i:=1 to n do begin
a[i]:=Random(11);
Write(a[i]:4)
end;
writeln;
writeln('Выбранные элементы:');
for i:=1 to n do
if a[i]<=i then Write(a[i]:4) else write(' ':4);
Writeln;
end.
Пример:
Исходный массив:
9 1 2 8 2 7 1 10 8 3
Выбранные элементы:
1 2 2 1 8 3
begin
var a:=ArrRandom(ReadInteger('n='),1,99);
a.Println;
var k:=ReadInteger('k=');
Writeln('Сумма чисел, кратных ',k,': ',
a.Where(x->x mod k=0).Sum)
end.
Тестовое решение:
n= 18
45 17 36 15 65 17 97 44 49 43 60 51 66 72 18 55 71 85
k= 12
Сумма чисел, кратных 12: 168
// PascalABC.NET 3.1, сборка 1218 от 12.04.2016
begin
var a:=ArrRandom(ReadInteger('n='),1,20);
a.Println;
a.Where((x,i)->x=i+1).Println
end.
Тестовое решение:
n= 16
17 2 1 14 20 19 10 3 9 15 14 4 2 7 2 16
2 9 16