Поместить в хеш таблицу 7 книг методом средних квадратов (по
названию книги). быть готовым объяснить принцип работы метода.

ответ:

генераторов случайных чисел уходит корнями к одному из самых известных имен в теории вычислительных машин - джону фон нейману (john von neumann). в 1946 году он предложил следующую схему генерации последовательностей случайных чисел: возьмите n-значное число, возведите его в квадрат и из результата, выраженного в виде 2n-значного числа (при необходимости дополненного слева до 2n-значного), возьмите средние n цифр. это и будет следующее число в последовательности. так, например, если n равно 4, в качестве начального числа можно взять 1234. следующими числами в последовательности будут 5227, 3215, 3362, 3030, 1809 и т.д. описанный метод известен под названием метода средних квадратов (middle-square method).

листинг 6.1. метод средних квадратов в действии

var

midsqseed : integer;

function getmidsquarenumber : integer;

var

seed : longint;

begin

seed : = longint(midsqseed) * midsqseed;

midsqseed : = (seed div 100) mod 1;

result : = midsqseed;

end;

к сожалению, с алгоритмом связано несколько больших проблем, которые исключают его применение в практических целях. вернемся к нашему примеру с четырехзначными случайными числами. предположим, что в последовательности нам встретилось число меньше 10. при вычислении квадрата будет получено число меньше 100. это, в свою очередь, означает, что следующим числом в последовательности будет 0 (поскольку мы возьмем четыре средние цифры из числа хх). это число также меньше 10, следовательно, все последующие числа в последовательности будут равны 0. вряд ли кто-то может сказать, что такая последовательность будет случайной! (если в качестве начального взять число 1234, то до попадания в 0 последовательность будет содержать 55 чисел.) кроме того, если начать, например, с числа 4100, последовательность будет состоять из 8100, 6100, 2100, 4100 и так до бесконечности. существуют и другие патологические последовательности, на которые легко натолкнуться и трудно избежать.

метод средних квадратов позволяет легко генерировать случайные числа на основе 16-битного целого числа. возведение 16-битного числа в квадрат дает 32-битное число. затем для вычисления средних 16-бит нужно всего лишь сдвинуть полученный результат на 8 бит вправо и выполнить операцию and с числом $. тем не менее, даже в этом случае алгоритм средних квадратов будет давать бесполезные результаты. после 50-60 случайных чисел алгоритм приводит к генерации нулей или попадает в цикл. то же самое происходит и для 32-битных чисел. в общем случае, несмотря простоту, применение метода средних квадратов вследствие его недостатков предельно ограничено.

объяснение: