но розбити на групи по три цифри, справа наліво, а потім перетворити кожну групу в вісімкову цифру. Якщо в останній, лівої, групі виявиться менше трьох цифр, то потрібно його доповнити нулями зліва.
Приклад:
101 000 0102
5 0 28
+111101000010 000 1 002
7. +5 0 2 0 48
А для переведення цілого двійкового числа в шістнадцяткове, число розбивають на групи по 4 цифри і слідують тим же алгоритмом, що і з вісімковій системою числення.
Наприклад:
0000 1100 0111 00012
0 З 7116
Наприклад:
1001 1101 00029 D 016
Дане правило працює і навпаки, тобто будь-яке ціле число можна перевести з вісімковій в двійкову і з шістнадцятковій в двійкову.
Наприклад:
123456780010100111001011101112АBCDEF123451010101111001101111011110001001000110100010167891601100111100010012
РОЗДІЛ 2. ВИКОРИСТАННЯ двійковій системі числення НА ПРИКЛАДАХ
.1 Гроші в конвертах і зерна на шахівниці
Поставимо перед собою завдання. Припустимо, що банкіри, які займаються відмиванням брудних грошей, і завтра чекають важливого клієнта, якому повинні видати круглу або не дуже круглу, але заздалегідь їм відому суму від 1 до 1000000000 у.о., щоб не бруднити руки об брудні гроші, вони заздалегідь дали своїм касирам заготовити деяку кількість конвертів з грошима, на яких написані містяться в них суми, і збираються просто віддати клієнту один або кілька конвертів, в яких і буде міститися необхідна їм сума. Яка кількість конвертів необхідно мати?
Звичайно, можна просто заготовити конверти з усіма сумами від 1 до 1000000000, але де взяти стільки грошей на конверти?
. Дізнаємося, яка буде в цьому випадку повна сума у ??всіх конвертах? Спробуємо оцінити також масу паперу, припускаючи, що використані не більше ніж сотенні купюри.
Є більш раціональні підхід до нашої справи. Треба покласти в перший конверт 1 у.о., а в кожен наступний класти вдвічі більшу суму, ніж у попередній. Тоді, наприклад, у 5-му конверті буде 16 у.о., в 10-му - 512 у.о., в 11-му - 1024 у.о., в 21-му - 1024=1048576 у. е., в 31-му - +1024=1073741824 у.о., але він, очевидно, вже не знадобиться, а ось 30-й з 1 073 741 824/2=536 870 912 у.о. може і стати в нагоді. У загальному випадку сума в (n + 1) -м конверті буде дорівнює добутку n двійок, це число прийнято позначати 2 і називати n-й ступенем двійки. Домовимося вважати, що 20=1. проведені вище обчислення заснувалися на наступних властивостях операції зведення в ступінь: 2n2m=2n + m, 2n/2m=2n-m, (2n) m=2nm
Експериментально легке перевірити, що будь-яке число можна представити єдиним чином у вигляді суми різних менших ступенів двійки, і тому наша задача вирішена. Наприклад, 30000=214 + 213 + 212 + 210 + 28 + 25 + 24.
Але для реального застосування потрібен алгоритм побудови такого розкладання. Далі наведемо кілька різних алгоритмів, але на початку розглянемо найпростіший. По суті, це алгоритм видачі здачі клієнту, записаний колись навіть в інструкції для працівників торгівлі, але дуже рідко ними виконуються. А він дуже простий - здачу треба видавати, починаючи з найбільших купюр. У нашому випадку потрібно знайти конверт з найбільшою сумою грошей, не перевершує необхідну, тобто найбільший ступінь двійки, яка не перевищує необхідної кількості грошей. Якщо необхідна сума дорівнює цього ступеня, то алгоритм закінчує роботу. В іншому випадку знову вибирається конверт з найбільшою сумою грошей, не перевершує залишилася і т.д. Алгоритм закінчить роботу, коли залишиться сума, в точності рівна ступеня двійки, і буде видана останнім конвертом.
Нижче доведемо, що, маючи набір конвертів з сумами в 1 у.о., 2у.е., 4 у.е., ..., 2n у.о., будь-яку суму грошей від 1 у.е. до 2n + 1 - 1 у.о. можна видати єдиним способом. Також буде доведено, що, діючи за описаним алгоритмом, завжди отримаємо цей спосіб видачі необхідної суми.
Спочатку розглянемо приклад роботи алгоритму з числом 2n - 1. Ясно, що на першому кроці вибрано число 2 n - 1, залишиться число 2n - 1 - 2 n - 1=2 n - 1 - 1, потім буде вибрано число 2 n - 2, і т.д., і в результаті вийде розкладання: 2n - 1=2 n - 1 + 2 n - 2 + ... + 22 + 21 + 20.
Але воно не здалося б очевидним, якщо, не знаючи заздалегідь відповіді, довелося б обчислювати суму 1 + 2 + 4 + 8 + ... + 2 n - 2 + 2 n - 1, звану сумою геометричній прогресії зі знаменником 2.
Адже для цього довелося б вигадати який-небудь трюк зразок н...
