Однозначное соответствие

16-08-2013, 17:26
Просмотров: 832
Внешние запоминающие устройства большого объема «со случайной выборкой», такие, как: накопители на магнитной ленте карусельного типа и накопители на магнитных дисках, требуют создания методов преобразования длинных (многоразрядных) «адресов» (или «кодов вызова, обращения») в более короткие по разрядности числа, являющиеся адресами в «запоминающих устройствах со случайной выборкой».

Однозначное соответствие


Как может быть осуществлено в этом случае однозначное соответствие? Конечно, если таких чисел будет больше чем 100 000, это невозможно, но если их меньше чем 100 000, то некоторые вероятностные методы могут обеспечить преобразование случайной и «неплотной» последовательности десятиразрядных чисел в последовательность пятиразрядных адресов (занятыми окажется уже большая часть адресов). Одним из употребительных методов решения этой задачи является вариант так называемого среднеквадратного метода образования (в нашем случае) требуемого 5-разрядного адреса (числа).
Пусть задано исходное число 1 122 305 151. Тогда девятнадцатиразрядный квадрат этого числа будет равен 1 259 568 851 961 132 801. Возьмем цифры, стоящие в разрядах от восьмого до двенадцатого (85 196), и припишем им исполнение функции пятиразрядного адреса. С высокой степенью вероятности из 10 000 10-разрядных чисел не найдется таких двух, для которых совпали бы выбранные пять разрядов.
Если же при таком преобразовании произойдет совпадение, то такой адрес помечается признаком «исключение» и проделывается одно из двух: или берется десять средних разрядов первого 20-разрядного квадрата, возводится в квадрат и из этого нового числа берутся требуемые пять разрядов, или берутся другие пять разрядов из первого квадрата данного числа. В обоих случаях проводится проверка на возможное совпадение.

Источник: delete-it
Автор: Николай Максименко
Опубликовано пользователем: 805 (смотреть все)
Комментарии: