На головну

А б в г д е є ж з и й к л м н о п р с т у ф х ц ч ш щ ь ь и е ю я

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2

Тоді, наприклад, ключ Сидоров запишеться як 8945752 (відмінність великих і малих літер ігнорується). Очевидно, така заміна може привести до того, що різні нечислові значення матимуть однакові числові заміни. Це одна з причин втрати інформації при виконанні алгоритмів рандомізації;

2. порядок числового значення ключа приводиться до порядку максимального номера Бакета. Наприклад, якщо максимальний номер Бакета - чотиризначний число, то числовий ключ 8945752, отриманий в попередньому кроці, повинен бути перетворений в чотиризначний число. Для такого перетворення існують різні способи. Деякі з них показані нижче (в припущенні, що максимальний номер Бакета - чотиризначний число):

· метод квадратів: Значення ключа зводиться в квадрат. В отриманому числі вибирається середня частина, що складається з необхідної кількості цифр. Наприклад, для числа 8945752 таке перетворення буде мати вигляд:

? ?
       
     середня частина числа, що складається з 4 цифр

· зсув розрядів: Розряди ключа діляться на старші і молодші і "зсуваються" один до одного так, щоб число перекриваються розрядів відповідало необхідному числу цифр. Поєднані цифри складаються. Наприклад, для числа 8945752 таке перетворення буде мати вигляд:

  ? ?  (13) (16) 92 ?
?  суміщені розряди  результат складання суміщених розрядів  остаточний результат
 старші розряди  молодші розряди

· метод складання: Ключ ділиться на 3 частини, середня з яких за кількістю цифр дорівнює необхідному порядку. Перша і третя частини накладаються на середню частину і суміщені цифри складаються. Наприклад, для числа 8945752 таке перетворення буде мати вигляд (тут середня частина - 9457):

?  8 25 ?  (17) 47 (12) ?
?  накладені частини числа  результат складання  остаточний результат
 середня частина числа

Очевидно, розглянуті методи можуть дати однакові результати для різних числових значень ключа. Це друга причина втрати інформації при рандомізації. Вибір того чи іншого методу з трьох розглянутих виконується експериментально: найкращим вважається той метод, при використанні якого Бакета заповнюються елементами відносно рівномірно;

3) отримане на попередньому кроці число множиться на константу С, яка розраховується як відношення максимального номера Бакета Nmax до максимального n-розрядному числу, де n - порядок максимального номера Бакета. Це дозволяє сформувати реальні номери Бакета. Наприклад, нехай максимальний номер Бакета - 7000 (це Nmax). Очевидно, n = 4. Тоді згадана константа З має значення:

С = 7000/9999 = 0,7.

Розрахуємо реальний номер Бакета для результату попереднього кроку, отриманого методом складання: 8473 * 0,7 = 5931.

Приклад 9. Розглянемо рішення задачі додавання елементів лінійного списку таблиці 11.

Оскільки в лінійному списку тільки 4 елементи, нехай максимальний номер Бакета Nmax дорівнює 0009, тоді порядок максимального номера Бакета n = 4.

Застосуємо алгоритм рандомізації для отримання номерів Бакета первинних ключів елементів таблиці 11 - прізвищ Скворцов, Соколов, Строков, Супруненко. При цьому використовуємо всі три методи приведення числового значення ключа до порядку максимального номера Бакета.

Рішення завдання складається з наступних кроків:

1. перетворення нечислових значень ключів в числові (використовується співвідношення, наведене раніше):

 



рандомизация | Прізвище (ключ) Числове значення ключа

Організація обміну інформацією в мережі | Обробка інформації | Операції над даними | лінійні списки | Способи доступу по первинному ключу | блоковий спосіб | двійковий спосіб | Індексного-послідовний спосіб | Індексного-довільний спосіб | Розміщення елементів в упорядкованому списку |

© um.co.ua - учбові матеріали та реферати