Сортировка слияниями

Прежде чем обсуждать новый метод, рассмотрим следующую задачу. Объединить ("слить") упорядоченные фрагменты массива A [k],.... А [т] и А [т - 1],..., A [q] в один A [k + 1],..., A [q], естественно, тоже упорядоченный (k < т <= q).

Алгоритм состоит в попарном сравнении очередных элементов каждого фрагмента, выяснении, какой из элементов меньше, переносе его во вспомогательный массив D (для простоты) и продвижении по тому фрагменту массива, из которого взят элемент. При этом следует не забыть записать в D оставшуюся часть того фрагмента, который не успел себя "исчерпать".

ПРИМЕР. Пусть первый фрагмент состоит из 5 элементов: 3 5 8 11 16, а второй — из 8: 1 5 7 9 12 13 18 20.

РЕАЛИЗАЦИЯ АЛГОРИТМА:

Procedure SI(k,m,q:Integer);
{Массив А глобальный}
Var i, j, t: Integer;
D:MyArray;
Begin
i:=k; j: =m+1; t:=l;
While (i<=m) And (j<=q) Do Begin
{Пока не закончился хотя бы один фрагмент.}
If A[i]<=A[j] Then
Begin D[t]:=A[i]; Inc(i); End
Else Begin D[t]:=A[j ]; Inc(j); End;
Inc(t);
End; {Один из фрагментов обработан полностью, осталось перенести в D остаток другого фрагмента.}
While i<=m Do
Begin D[t]:=A[i]; Inc (i); Inc(t) End;
While j<=q Do
Begin D(t]:=A[j];Inc(j); Inc(t) End;
For i:=l To t-1 Do A[k+I-1]:=D[i];
End;

Если мы "сливаем" фрагменты одного массива А, то параметр m из заголовка процедуры можно убрать. Достаточно оставить нижнюю и верхнюю границы фрагментов, т.е. — Sl(к, q: Integer), где k — нижняя, а q — верхняя границы. Вычисление т (эта переменная становится локальной) сводится к присвоению: т:= k + (q — k) Div 2. При этом уточнении приведем процедуру сортировки. Первый вызов процедуры — Sort(1, N).

Procedure Sort(i,j:Integer);
Var t:Integer;
Begin
If i>=j Then Exit;
{Обрабатываемый фрагмент массива из одного элемента.}
If j-i=l Then Begin If A[j]<A[i] Then
Begin{Обрабатываемый фрагмент массива из двух элементов.}
t:=A[i];A[i]:=A[j];A[j]:=A[i];
End;
End
Else Begin
Sort (i,i+(J-i) Div 2);
{Разбиваем заданный фрагмент на два.}
Sort(i+(j-i) Div 2+1,j);
Sl(I,j);
End;
End;

Метод слияний — один из первых в теории алгоритмов сортировки. Он предложен Джоном фон Нейманом в 1945 году. В этом алгоритме наглядно реализован принцип "разделяй и властвуй".

ЭФФЕКТИВНОСТЬ АЛГОРИТМА:

по Д. Кнуту, составляет С= O(N• Log2N).

ЗАДАНИЯ:

III уровень:

1. 1. Дан массив 7 9 131 8 4 10 11 5 36 2. Возрастающий участок 7 9 13, а справа, если читать справа налево, есть участок 2 6. Слияние этих двух фрагментов массива дает 2 6 7 9 13. А затем "сливаем" 1 8 и 3 5 11, получаем 1 3 5 8 11.

Записываем в массив и получаем: 2 6 7 9 134 10 11 8 5 3 1. Поскольку средний участок 410 "сливать" не с чем, рассмотрим его как два — 410 и 10 (т.е. прочитаем его в двух направлениях). Если с первыми фрагментами 2 6 7 9 13 и 1 3 5 8 11 все ясно, то вторые 4 10 и 10 перекрываются. Необходимо учесть сей факт и не дублировать 10 при записи в массив. Получаем: 1 2 3 5 6 7 8 9 11 1310 4. Последнее "слияние" дает 1 2 3 4 5 6 7 8 9 10; 11 13. Массив отсортирован. Этот метод называется у Д. Кнута “сортировкой естественным двухпутевым слиянием” Реализовать алгоритм.

2. 2. 'Изменим схему выбора участков для "слияния". Не будем искать монотонные участки, а работаем с участками фиксированной длины (“простое двухпутевое слияние”).
Исходный массив:
13 1 7 5 4 3 9 10 6 19 14 16 23 2 4 8.
1-й шаг (длина 1).
8 13 2 7 416 9 19 10 6 14 3 23 5 4 1.
2-й шаг (длина 2).
14 813 3 4 14 16 19 10 9 6 23 7 5 2.
3-й шаг (длина 4).
1 2 4 5 7 8 13 23 1916 14 10 9 6 4 3.
4-й шаг (длина 8).
1 2 3 4 4 5 6 7 8 9 10 13 14 16 19 23.
Реализовать данный алгоритм сортировки. Размер массива не всегда совпадает с числом, равным степени двойки.

3. 3. Реализовать “трехпутевое“ (“четырехпутевое”,..., " k- путевое"). слияние.

Быстрая сортировка

Данный метод был предложен Ч.Э.Р. Хоаром в 1962 году. В общем случае его эффективность достаточно высока, поэтому автор назвал его "быстрой сортировкой".
АЛГОРИТМ:

В исходном массиве А выбирается некоторый элемент X (его называют "барьерным"). Целью является запись Х "на свое место" в массиве, пусть это будет место k, такое, чтобы слева от Х были элементы массива, меньшие или равные X, а справа — элементы массива, большие X, т.е. массив А будет иметь вид:
(A[1], A[2],..., A[ k - 1]), A[ k ] = (X), (A[ k + 1],..., A[n]).
В результате элемент A [ k ] находится на своем месте и исходный массив А разделен на две неупорядоченные части, барьером между которыми является элемент А [ k ]. Далее требуется отсортировать полученные части тем же методом до тех пор, пока в каждой из частей массива не останется по одному элементу, то есть пока не будет отсортирован весь массив.

П РИМЕР. Исходный массив состоит из 8 элементов: 8 12 3 7 19 11 4 16. В качестве барьерного элемента возьмем средний элемент массива (7). Произведя необходимые перестановки, получим: (4 3) 7 (12 19 11 8 16); теперь элемент 7 находится на своем месте. Продолжаем сортировку.
Левая часть: Правая часть:
(3) 4 7 (12 19 11 8 16) 3 4 7 (8) 11 (19 12 16)
3 4 7 (12 19 11 8 16) 3 4 7 8 11 (19 12 16)
3 4 7 8 11 12 (19 16)
3 4 7 8 11 12 (16) 19
3 4 7 8 11 12 16 19
Из описания алгоритма видно, что он может быть реализован посредством рекурсивной процедуры, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива.

РЕАЛИЗАЦИЯ АЛГОРИТМА:

Procedure Quicksort (m, t: Integer);
Var i, j, x, w: Integer;
Begin
i:=m; j:=t; x:=A[ (m+t) Div'2];
Repeat
While A[i]<x Do Inc(i);
While A[j]>x Do Dec(j);
If i<=j Then Begin w:=A[i]; A[i]:=A[j]; A[jl:=w; Inc(i); Dec(j) End
Until i>j;
If m<j Then Quicksort(m, j);
If i<t Then Quicksort(i,t),
End;

ЭФФЕКТИВНОСТЬ АЛГОРИТМА:

С = N + 2 • (N/2) + 4 • (N/4) +... + N • (N/N) = 0(N • logN).

ЗАДАНИЯ: III уровень:

1. 1. Следует отметить, что данный алгоритм является затратным с точки зрения использования оперативной памяти. Замените рекурсивную схему реализации логики на нерекурсивную и оцените значение N, при котором ваша программа в рекурсивной реализации не будет компилироваться по этой причине.

2. 2. Считается, что выбор элемента Х случайным образом оставляет среднюю эффективность неизменной при всех типах массивов (упорядоченный, распределенный по какому-то закону и т.д.). Реализуйте эту идею.

ПИРАМИДАЛЬНАЯ СОРТИРОВКА
Данный метод был предложен Дж.У.Дж. УИЛЬЯМСОМ и Р.У. Флойдом в 1964 году. Элементы массива А образуют пирамиду, если для всех значений i выполняются условия: A [ i ] < = А [2 • i ] и А [ i ] <= А [2 • i + 1 ].

ПРИМЕР. Элементы массива 8 10 3 6 13 9 5 12 не образуют пирамиду (А[1] > А [3], А [2] > А [4] и т.д.), а элементы массива
3 6 5 10 13 9 8 12 — образуют.
Очевидно, что элементы правой половины массива A [N/2+1.. N] независимо от их значений образуют пирамиду.
Предположим, что нам необходимо отсортировать элементы массива А (8 10 3 6 13 9 5 12) по невозрастанию.
Идею сортировки поясним с помощью следующей таблицы (курсивом выделена часть элементов массива, образующих пирамиду, жирным шрифтом — отсортированная часть массива).

В конечном итоге массив отсортирован.
Пусть мы умеем строить пирамиду из элементов массива А с индексами от 1 до q (процедура Руram (q)), тогда процедура сортировки имеет вид:

Procedure Sort;
Var t,w:Integer;
Begin
t:=N;
Repeat
Pyram(t);{Строим пирамиду из t элементов.}
w:=A[1];A[1]:=A[t];A[t]:=w;
Dec (t)
Until t<2
End;

Из таблицы мы видим, что процесс построения пирамиды начинается с конца массива. Посдедние q div 2 элементов являются пирамидой по той причине, что удвоение индекса выводит нас за пределы массива. А затем берется очередной справа элемент из "непирамидальной" части и "проталкивается" по "пирамидальному" массиву до тех пор, пока он не будет меньше элемента с удвоенным индексом (по отношению к индексу рассматриваемого элемента) и следующего за ним элемента. Процесс продолжается до тех пор, пока мы "не поставим" на своё место первый элемент массива. Приведем текст процедуры.

Procedure Pyram(q:Integer);
Varr, i, j,v:Integer;
Begin
r:=q Div 2+1;{Эта часть массива является пирамидой.}
While г>1 Do Begin{Цикл-по элементам массива, для которых необходимо найти место в пирамиде.}
Dec(г);
i:=r; v:=A[i];{Индекс, рассматриваемого элемента и сам элемент.}
j:=2*i;{Индекс элемента, с которым происходит сравнение.}
pp:=False;{Считаем, что для элемента не найдено место в пирамиде.}
While (J<=q) And Not pp Do Begin
If j<q Then If A[j]>A[j+l] Then Inc(j);{Сравниваем с меньшим элементом.}
If v<=A[j] Then pp:=true {Элемент находится на своем месте.}
else begin A[i]:=A[j]; i:=j; j:=2*i end {Переставляем элемент и идем дальше по пирамиде.}
End;
A[i]:=v
End;
End;

ЭФФЕКТИВНОСТЬ АЛГОРИТМА:

С= O(N² • logN).

При сортировке процедура Pyram вызывается N — 1 раз. Эта процедура состоит из двух вложенных циклов сложности N и — logN. Итак, упорядочивание одного элемента требует не более logN действий, построение полной пирамиды N • logN действий.

В вышеприведенной логике после каждой перестановки элементов вновь строится пирамида для оставшихся элементов массива. А зачем? Пирамида почти есть. Требуется только "протолкнуть" верхний элемент на свое место (т.е. строки таблицы с номерами 7—9, 12—14, 17—18,21—22, 25, 28, вообще говоря, избыточны).

Выделим "проталкивание" одного.элемента в отдельную процедуру Pr (r,q), где r — номер проталкиваемого элемента, q — верхнее значение индекса.

Procedure Рг(r,q:Integer);
Var r, i, j,v: Integer;
pp:boolean;
Begin
i:=r; v:A[i];{Индекс рассматриваемого элемента и сам элемент.}
j:=2*i;{Индекс элемента, с которым происходит сравнение.}
pp:=False;{Считаем, что для элемента не найдено место в пирамиде.}
While (j<=q) And Not pp Do Begin
If j<q Then If A[j]>A[j+l] Then Inc(j);{Сравниваем с меньшим элементом.}
If v<=A[j] Then pp:=true {Элемент находится на своём месте. }
else begin A[i]:=А[j]; i:=j; j:=2*i end {Переставляем элемент и идем дальше по пирамиде.}
End;
A[i]:=v
End;

Какие изменения требуется внести в процедуру Sort?
Procedure Sort;
Var t, w, i:Integer;
Begin
t:=N Div 2+1; {Эта часть массива является пирамидой.};
For i:=t-l DownTo 1 Do Pr(i,N);{Строим пирамиду(только один раз).}
For i:=N DownTo 2 Do Begin;
w:=A[1];A[1]:=A[i];A[i]:= w; {Меняем местами 1-й и i-й элементы.}
Pr(1,i-l) {Проталкиваем 1-й элемент.}
End
End;

ЗАДАНИЯ: I уровень:

1. 1. Изменить алгоритм так, чтобы элементы массива А сортировались в порядке неубывания.

II уровень:

1. Для хранения данных используется не массив, а список (однонаправленный или двунаправленный).— "сортировка списка". Разработать программу пирамидальной сортировки для этого случая.

III уровень:

1. Понижение сложности алгоритма N^2 • logN до N• logN

2. Разработать программу пирамидальной сортировки для случая, когда для хранения данных используется не массив, а бинарное дерево.
3. Много, очень много черепашек живет в огромном дворце со всеми удобствами, кроме одного. Им приходится ползать за водой к родниковому источнику. Дорога до источника прямая, ее длина М метров. В некоторый момент времени на дороге находится N черепашек. Часть из них ползет в сторону дворца, часть — к источнику. Все черепашки ползут с одинаковой скоростью (1 метр в час).
Требуется найти:
• общее количество встреч черепашек в пути;
• время последней встречи.
Входные данные (файл Input.Txt). В первой строке записаны значения М и N, а затем N строк, в каждой из которых записаны Х i (1 <= i<= N) — координата черепашки и буква "Д" или "И" (направление движения черепашки). Все координаты X i — вещественные числа и различны.
Выходные данные (файл OutputTxt). В первой строке записывается количество встреч, во второй — время последней встречи (с точностью до пяти знаков). При отсутствии встреч выводится сообщение: "NO MEETINGS".
Ограничения. 1 < = N <= 30 000, время решения — 10 секунд.

II. Поиск данных

ЛИНЕЙНЫЙ ПОИСК

Основной вопрос задачи поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинство задач поиска сводится к простейшей — к поиску в массиве элемента с заданным значением.

Рассмотрим именно эту задачу. Пусть требуется найти элемент Х в массиве А. В данном случае известно только значение разыскиваемого элемента, никакой дополнительной информации о нем или о массиве, в котором производится поиск, нет. Наверное, единственным способом является последовательный просмотр массива и сравнение значения очередного рассматриваемого элемента массива с X. Напишем фрагмент:

For i:=1 To N Do If A[i]=X Then k:=i;

В этом «цикле месячных дней» находится индекс последнего элемента А, равного X, при этом массив просматривается полностью.

Эффективность алгоритма: O(N).

ЗАДАНИЯ:

I уровень:

1. 1. Найти первый элемент, равный Х.

2. 2. Найти последний элемент, равный Х.

3. 3. написать программу поиска заданного слова в тексте. Слово и текст являются массивами символов заданной длины. Если слово присутствует в тексте, то выдать номер начальной позиции совпадения, в противном случае - 0.

4. 4. Для каждой буквы заданного текста указать, сколько раз она встречается в тексте.

II уровень:

1. Во входном файле дан массив А и массив из элементов, поиск которых будет осуществляться в массиве А. Изменить массив А таким образом, чтобы суммарное количество сравнений при поиске элементов было минимальным.

2. Даны массив А и число X.
Переставить элементы массива таким образом, чтобы вначале были записаны элементы, меньшие или равные X, а затем— большие или равные X.
Переставить элементы массива таким образом, чтобы вначале были записаны элементы, меньшие X, затем равные Х и, наконец, большие X.

Примечание. Указанные перестановки следует сделать за один просмотр А и без использования дополнительных массивов.

БИНАРНЫЙ ПОИСК

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

Пример. Пусть Х = б, а массив А состоит из 10 элементов:
3 5 б 8 12 15 17 18 20 25.
1-й шаг. Найдем номер среднего элемента: т =[(1+10)/2] = 5.
Так как 6 < А [5], далее можем рассматривать только элементы, индексы которых меньше 5:
3 5 6 8 12 15 17 18 20 25.

2-й шаг. Рассматриваем лишь первые 4 элемента массива, находим индекс среднего элемента этой части
т =[(1+4)/2] = 2, 6 > А [2], следовательно, первый и второй элементы,из рассмотрения исключаются:
3 5 6 8 12 15 17 18 20 25.

3-и шаг. Рассматриваем два элемента, значение т =[(3+4)/2] = 3:
3 5 6 8 12 15 17 18 20 25.
А [3]= б. Элемент найден, его номер — 3.

Реализация бинарного поиска:

Procedure Search;
Var i,j,m:Integer; f:Boolean;
Begin
i:=1; j:=N;{На первом шаге рассматривается весь массив.}
f:=False;(Признак того, что Х не найден.}
While (i<=j) And Not f Do Begin
m:=(i+j) Div 2;
{Или m:=i+.(j-i) Div 2;, так как i+(j-i) Div 2= (2*i+(j-i)) Div 2=(i+j) Div 2.}
If A[m]=X Then f:=True {Элемент найден, поиск прекращается.}
Else If A[m]<X Then i:=m+l {Исключаем из рассмотрения левую часть А.}
Else j:=m-l{Правую часть.}

End
End;

Рекурсивная реализация бинарного поиска. Значением переменной t является индекс искомого элемента или ноль, если элемент не найден.

Procedure Search (i,j:Integer;Var t:Integer);
{Массив А и переменная Х глобальные величины}
Var m:Integer;
Begin
If i>j Then t:=0 Else Begin m:=(i+j) Div 2;
If A[m]<X Then Search(m+1,j,t) Else
If A[m]>X Then Search(i,m-l,t) Else t:=m
End
End;

Эффективность алгоритма:

Каждое сравнение уменьшает диапазон поиска приблизительно в два раза. Следовательно, общее количество сравнений имеет порядок O (logN).

ЗАДАНИЯ:

I уровень:

1. 1. Реализовать (рекурсивную и нерекурсивную) схему бинарного поиска с использованием "барьерной" техники.

II уровень:

1. Ниже по тексту приведены три версии процедуры бинарного поиска. Какая из них верная? Исправьте ошибки. Какая из них более эффективная?

Procedure Search;
Var i, j, k: Integer;
Begin
i:=l;j:=N;
Repeat
k:=(i+j) Div 2;
If X<=A[k] Then j:=k-l;
If A[k]<=X Then i:=k+l;
Until i>j
End;

Procedure Search;
Var i, j, k: Integer;
Begin
i:=l;j:=N;
Repeat
k:=(i+j) Div 2;
If X<A[k] then j:=k Else i:=k+l;
Until i>=j
End;

Procedure Search;
Var i, j, k: Integer;
Begin
i:=l;j:=N;
Repeat
k:=(i+j) Div 2;
If A[k]<X Then i:=k Else j:=k;
Until (A[k]=X) Or (i>=j)
End;

2. Решить задачу поиска числа Х в двухмерном массиве A[1..N, 1.. M] (элементы в строках и столбцах упорядочены) за время, пропорциональное O(N + M).

ХЕШИРОВАНИЕ

Рассмотрим простую задачу. Количество различных буквосочетаний длиной не более 4 символов из 32 букв русского алфавита чуть больше 10^6. Мы проанализировали какой-то текст и выписали в соответствующий массив все встреченные буквосочетания. После этого на вход нашей простой системы анализа текста поступает некоторое буквосочетание. Нам необходимо ответить, встречалось оно ранее или нет. Очевидно, что каждому буквосочетанию соответствует некоторый цифровой код. Поэтому задача сводится к поиску в массиве некоторого цифрового значения — ключа.

При линейном поиске в худшем случае для ответа на вопрос "есть или нет" потребуется 10⁶ сравнений, при бинарном — порядка 50.

Можно ли уменьшить количество сравнений и уменьшить объем требуемой оперативной памяти, резервировать не 10⁶, а, например, 10³ элементов памяти? Обозначим цифровой аналог буквосочетания символом R, а адрес в массиве (таблице) через А.

(1) Если будет найдено преобразование
(R), дающее значение А такое, что
выполняется достаточно быстро; (2) случаев, когда
(R1) =
(R2), будет минимальное количество, то задача поиска трактуется совсем иначе, чем рассмотрено выше. Этот способ поиска называется ХЕШИРОВАНИЕМ (расстановкой ключей, рандомизацией и т.д.).

Итак, ключ преобразуется в адрес, в этом суть метода. Требование по быстродействию очевидно — это одна из задач при составлении любого алгоритма, ибо быстродействие компьютера ограничено. Второе требование не столь очевидно. Предположим, что анализируется текст из специфической страны "Д..", в которой все слова начинаются с буквы "о" и в качестве
выбран цифровой аналог первой буквы. В этом случае получаем одно значение А для всех слов (от чего уходили, к тому и пришли, но в стране "Д..." все возможно). Следовательно, необходимо выбирать такое преобразование
, чтобы количество совпадений адресов (А) для различных значений ключей (R) (такие совпадения называют коллизиями) было минимально. Полностью избежать коллизий не удается. Для любого преобразования
(хеш-функции) можно подобрать такие исходные данные, что рассматриваемый метод поиска превращается в линейный поиск. Однако цель построения хеш-функции ясна — как можно более равномерно "разбрасывать" значения ключей по таблице адресов (ее размер обозначим через М) так, чтобы уменьшить количество коллизий.

Реализация метода логически разбивается на две составляющие:
1 - построение
;
2 - схема разрешения коллизий.

1. Так или иначе для значения ключа R находится цифровой аналог, обозначим его через t.
Первый способ: в качестве М выбирается простое число и находится остаток от деления t на М (t MOD М).
Второй способ: находится значение t². Из этого значения "вырезается" q каких-то разрядов (лучше средних). Значение q выбирается таким образом, чтобы 2^q было равно М.

Третий способ: w разрядов для представления ключа t разбиваются на части длиной q разрядов. Выполняется, например, логическое

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

Качество хеш-функции оценивается средней длиной списков. Рассмотрим следующую простую задачу. Дано N(1<=N<=15 000) различных двоичных чисел длины L (1 <= L <= 100), а также Q (1 <= Q <= 20 000) запросов или двоичных чисел также длины L. Требуется определить для каждою запрошенного числа, встречается оно или нет среди N ранее определенных чисел. Время решения задачи ограничено 30 секундами.
Заметим, что сложность "лобового" решения имеет порядок O(N • L• M), поэтому по временному ограничению оно вряд ли приемлемо. Используем метод хеширования. Построим три различные хеш-функции, а для разрешения коллизий будем использовать "метод цепочек". Проверим решения на случайных тестах. Обозначим цифрой "1" хеш-функцию, использующую деление на простое число, "2" — возведение в квадрат, "3" — логические операции с подстроками фиксированной длины, выделяемые из значения ключа. Оцениваем минимальную и максимальную длины списков (Мin, Мах) и время решения (t). В таблице приведены результаты нескольких экспериментов.

Рассмотрим реализацию первой хеш-функции.
Структуры данных.

ConstInputFile='Input.Txt';
OutputFile'Output.TxT';
MaxN=15000;
MaxL=100;
MaxTbl=547; {Размер таблицы.}
Type TNum=Array [0..MaxL Div 8] Of Byte;{Массив для хранения двоичного числа.
В этом есть определенная сложность, "затемняющая"
суть решения, но чисто техническая.}
PRec=^TRec;
TRec=Record num: TNum; next: PRec; End;
Var N, Ln, Q, LnDv8: Integer;
Tbl: Array[0..MaxTbl-1] Of PRec;{Таблица указателей (ссылок).}

Ряд вспомогательных процедур и функций.

Procedure ReadNum(Var nw: TNum);{Считываем число.}
Var i: Integer;ch: Char;
Begin
FillChar(nw, SizeOf (nw), 0);
For i:=0 To Ln-1 Do Begin
Read (ch);
nw[i Div 8]:=nw[i Div 8]*2+Ord (ch)-Ord('0');
End;
ReadLn
End;

Procedure AddTRec (Var P: PRec; Const nm: TNum);
{Добавить запись в хеш-таблицу. Вставка осуществляется в начало списка.}
Var smp: PRec;
Begin
If P=nil Then Begin New (P);P^.next:=nil; P^.num:=nrn End
Else Begin New (smp); smp^.next:=P^.next; smp^.num:=nm; P^.next:=smp End
End;
Function GetNum(Const p: TNum): Integer;
{Получить хеш-значение для числа. Преобразовать представление в виде элементов массива в числовое значение и найти остаток
от деления на простое число, равное размеру таблицы указателей (ссылок).}
Var i, nw: LongInt
Begin
nw:=0;
For i:=0 To LnDv8 Do nw:=((nw shl 8)+p[i]) Mod MaxTbl;
GetNum:=nw
End;
Procedure Init;
Var i: Integer; nm: TNum;
Begin
FillChar(Tbl, SizeOf (Тbl), 0);
Assign (Input, InputFile); Reset(Input); ReadLn(N, Ln, Q); LnDv8:=(Ln-1) Div 8;
For i:=1 To N Do Begin
ReadNum (nm);
AddTRec(Тbl [GetNum(nm)], nm) {Добавляем элемент в хеш-таблицу.}
End;
Assign(Output, OutputFile); Rewrite(Output)
End;
Function IfEq(Const a, b: TNum): Boolean;{Сравнение двух ключей.}
Var i: Integer;
Begin
i:=0;
While (i<=LnDv8) And (a [i] =b [i]) Do Inc(i);
IfEq:=i > (LnDv8)
End;

Основная процедура.

Procedure Solve;
Var i: Integer; nw: TNum; fn: Boolean; uk: PRec;
Begin
For i:=l To Q Do Begin
ReadNum (nw);{Читаем очередное число.}
uk:=Tbl[GetNum(nw)];{Вычисляем адрес в хеш-таблице.}
fn:=False;
While (uk<>nil) And (Not.fn) Do Begin {Просматриваем список.}
fn:=IfEq(nw, uk^.num); {Проверяем, есть ли совпадение?}
uk:=uk^.next {Переходим к следующему элементу списка.}
End;
If fn Then WriteLn ('YES') Else WriteLn ('NO') {Выводим результат.}
End
End;

Основная программа.

Begin Init; Solve; Close(Input); Close(Output) End.

ЗАДАНИЯ:

II уровень:

1. Для реализации второй хеш-функции (средние биты квадрата числа) требуется изменить функцию GetNum и добавить одну константу. Проведите данную модификацию программы, используя следующую "заготовку".

Const... HwBite=9; МахТbl=1 shl HwBite; {Размер таблицы указателей 2⁹.}
Function GetNum(Const p: TNum): Integer;{Найти адрес таблицы указателей для значения ключа р. Программный код "утяжелен" из-за необходимости использовать массив для хранения значения ключа.}
Var i, j, nw: LongInt;clc: Array[0..(MaxL Div 8)*2] Of LongInt;
Begin
FillChar(clc, SizeOf(clc), 0);
For i:=0 To LnDv8 Do {Необходимо перемножить значения всех байт.}
For j:=0 To LnDv8 Do Begin
Inc(clc[i+j], p[i]*LongInt (p[j]));Inc(clc[i+j+1], clc[i+j] Div (1 shl 8));
clc[i+j]:=clc[i+j] Mod (1 shl 8)
End;
nw:=0; j:=((HwBite-1) Div 8+1);
For i:=LnDv8-(j Div 2) To LnDv8+(j+l) Div 2-1 Do
nw:=(nw shl 8+clc[i]) Mod MaxTbl;
GetNum:=nw
End;

2. Реализация третьей хеш-функции также требует изменения только одной составной части рассмотренной выше логики. Выполните модификацию программы с использованием нижеприведенной "заготовки".

Const... HwBite=9;MaxTbl=1 shl HwBite;
Function GetScBt (p: Byte): Byte;
Var sc: Integer;
Begin
sc:=0; While p<>0 Do Begin p:=p shr 1; If p Mod 2=1 Then Inc (sc) End;
GetScBt:=sc Mod 2
End;
Function GetNum(Const p: TNum): Integer;{Получить хеш-значение для ключа.}
Var i, nw, geth, pp: LongInt;
Begin
nw:=0;
If LnDv8+1<=HwBite Then
For i:=0 To LnDv8 Do nw:=nw*2+GetScBt(p[i])
Else Begin pp:=(LnDv8+l) Div HwBite; geth:=0;
For i:=0 To LnDv8 Do Begin
geth:=geth Xor GetScBt(p[i]);
If (i>0)And(((i Mod pp=0) And (i Div pp<HwBite)) Or (i=LnDv8))
Then Begin nw:=nw*2+geth; geth:=0 End
End
End;
GetNum:=nw
End;

III уровень:

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