Page 126 - 4496

Виконаємо оптимізацію для умов розглянутого прикладу
(M = 16, N = 63). Оптимальне значення кількості відрізків L =
16 / ln 16 = 16 / 2.7726 = 5.77  6. Ширина відрізка h = 63 / 6 
11. Для подання чисел, менших h=11, достатньо 4 двійкових
розряди, отже для зберігання всіх чисел потрібно 4  16 = 64
двійкових розряди. Оскільки значення межі п’ятого відрізка
становить 11  5 = 55, то до шостого відрізка потрапляють
числа, що більші або рівні 55, тобто (58, 62). Тому найбільше
значення границі рівне 16 - 2 = 14. Для подання цього числа
потрібно 4 розряди, отже для зберігання значень всіх п’яти
границь потрібно 5  4 = 20 двійкових розрядів. Загальний
обсяг потрібної пам’яті становить 64 + 20 = 84, а економія
складає 12 розрядів.
Перевіримо оптимальність розв’язку L = 6, провівши
обрахунки з іншими значеннями L.
Випадок 1. L = 5; h = 63 / 5 = 12.6  13; для зберігання
чисел, менших 13, потрібно 4  16 = 64 розряди; значення межі
четвертого відрізка 13  4 = 52; до п’ятого відрізка
потрапляють значення (58, 62); найбільше значення границі 16
- 2 = 14; для зберігання чотирьох границь потрібно 4  4 = 16
розрядів; загальний обсяг потрібної пам’яті 64 + 16 = 80;
економія складає 16 розрядів. Даний результат кращий
основного за рахунок збільшення ширини відрізка і
відповідного зменшення кількості границь.
Випадок 2. L = 4; h = 63 / 4  16, що вимагає тих же 4
розрядів для подання числа і 64 розрядів для зберігання всіх
чисел; значення межі третього відрізка рівне 48, отже до
четвертого відрізка потрапляють числа (50, 51, 58, 62);
найбільше значення границі рівне 12, отже для зберігання
трьох границь потрібно 4  3 = 12 розрядів; загальний обсяг
потрібної пам’яті складає 64 + 12 = 76 розрядів; економія
становить 96 - 76 = 20 двійкових розрядів. Даний результат ще
кращий основного за рахунок найбільшої можливої ширини
відрізка при чотирьох розрядах на число. Відзначимо, що таке
4
значення h = 16 = 2 є степенем 2, найближчим до основної
ширини відрізка h=11 в більшу строну.
Випадок 3. L = 7; h = 63 / 7 = 9; для зберігання чисел
потрібно 4  16 = 64 розряди; обсяг пам’яті для зберігання
чисел той же, що і в основному результаті, але кількість

123