Арифметичні операції над двійковими числами.
Задача 1: Отримання всіх вибірок.
Дуже часто зустрічаються задачі, в яких потрібно вміти побудувати всі можливі комбінації із заданого набору предметів. Наприклад, таке завдання:
Дана велика купа каміння, розкласти каміння за двома купах таким чином, щоб маса цих двох куп була якомога однаковою.
Цю задачу можна сформулювати так:
Знайти таку вибірку каменів з великої купи, що її загальна маса буде якомога менше відрізнятися від половини маси великої купи.
Задач такого гатунку досить багато. І всі вони зводяться, як вже було сказано до вміння отримати всі можливі комбінації (далі ми будемо називати їх вибірками) із заданого набору елементів. І зараз ми розглянемо загальний метод отримання всіх можливих вибірок з використанням операції додавання двійкових чисел. А почнемо з прикладу. Нехай є безліч з трьох предметів. Побудуємо всі можливі вибірки. Предмети будемо позначати порядковими номерами. Тобто, є наступні предмети: 1, 2, 3.
Вибірки: (0, 0, 1); (0, 1, 0); (0, 1, 1); (1, 0, 0); (1, 0, 1); (1, 1, 0); (1, 1, 1);
Якщо у позиції з черговим номером стоїть одиниця, то це означає, що елемент з номером рівним цієї позиції присутній у вибірці, а якщо стоїть нуль, то елемент не присутня. Наприклад, вибірка (0, 1, 0); складається з одного елемента з номером 2, а вибірка (1, 1, 0); складається з двох елементів з номерами 1 і 2.
З цього прикладу ясно видно, що вибірку можна представити у вигляді двійкового числа. Крім того, неважко помітити, що вище записані всі можливі одно, двох і тризначні двійкові числа. Перепишемо їх таким чином:
001; 010; 011; 100; 101; 110; 111
Будемо вважати молодшим розрядом перший праворуч, відкинемо незначущі нулі (тобто нулі в старших розрядах до першої одиниці), і отримаємо наступний ряд:
1; 10; 11; 100; 101; 110; 111
Ми отримали ряд послідовних двійкових чисел, кожне з яких виходить з попереднього збільшенням одиниці. Можете це перевірити. Використовуючи цю помічену закономірність можна побудувати наступний алгоритм отримання вибірок.
Вихідні дані алгоритму
Дан набір предметів N - штук. Далі будемо називати цей набір безліччю вихідних елементів. Пронумеруємо всі елементи вихідної безлічі від 1 до N. Складемо двійковечисло з N незначних нулів. 0000 ... 0N Це нульове двійкове число буде позначати нульову вибірку з якою і почнеться процес складання вибірок. Розряди числа вважаються справа наліво, то є самий лівий розряд це самий старший.
Домовимося позначати це двійкове число великими літерами двійкову
Алгоритм
Якщо двійкового числа складається цілком з одиниць
То припиняємо роботу алгоритму
Інакше
Початок
o Додаємо до двійкового числа одиницю за правилами двійковій арифметики.
o З отриманого двійкового числа складаємо чергову вибірку, як було описано вище.
Кінець
Задача 2: Пошук великих простих чисел.
Для початку згадаємо, що простим числом називається таке натуральне число, яке ділиться тільки на 1 і на саме себе. Приклади простих чисел: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31
Пошук великих простих чисел - дуже важлива математична задача. Великі прості числа необхідні для надійного шифрування повідомлень деякими алгоритмами шифрування. Причому необхідні не просто великі числа, а дуже великі. Чим число більше, тим надійніше шифр, побудований на цьому числі.
Примітка. Надійним шифром називається такий шифр, для розшифровки якого потрібно дуже великий час.
Чому? Просте число грає роль ключа при шифруванні і дешифрування. Крім того, ми знаємо, що прості числа зустрічаються в ряду натуральних чисел не надто часто. Їх досить багато серед першої тисячі, потім їх кількість починає швидко убувати. Тому якщо в якості ключа ми візьмемо не дуже велике число, дешифрувальників за допомогою навіть не дуже швидкого комп'ютера зможе до нього добратися (перебираючи в якості ключа всі прості одне за іншим) за обмежений час.
Досить надійний код можна отримати якщо взяти просте у якому, наприклад 150 знаків. Однак, знайти таке просте не так просто. Припустимо, що деяке число А (дуже велике) потрібно перевірити на простоту. Це теж саме, що пошукати його подільники. Якщо ми зможемо знайти подільники в інтервалі від 2 до корінь квадратний з А, то воно не просте. Оцінимо кількість чисел які необхідно перевірити на здатність розділити число А.
Припустимо число А має 150 знаків. Корінь квадратний з нього буде містити не менше 75 знаків. Щоб перебрати таку кількість можливих дільників нам буде потрібно дуже потужний комп'ютер і величезний час, а це означає, що завдання практично не вирішувана.
Як з цим боротися.
По-перше, можна повчиться швидше здійснювати перевірку на подільність одного числа на інше, по-друге можна спробувати число А підбирати таким чином, щоб воно було простим з високим ступенем імовірності. Виявляється це можливо. Математик Мерсен виявив, що числа наступного виду
2n - 1
Є простими з високим ступенем імовірності.
__________________________________________________________
Щоб зрозуміти фразу написану вище, порахуємо скільки простих чисел знаходиться в першій тисячі і скільки чисел Мерсена в цій же тисячі є простими. Отже, числа Мерсена в першій тисячі - це наступні:
21 - 1 = 1; 22 -1 = 3; 23- 1 = 7; 24 - 1 = 15; 25 - 1 = 31; 26 -1 = 63;
27 - 1 =127; 28 -1 = 255; 29 - 1 = 511;
Жирним шрифтом позначені прості числа. Всього на 9 чисел Мерсена 5 простих. У відсотках це 5/9 * 100 = 55,6%. У той же час на 1000 перших натуральних чисел тільки 169 простих. У відсотках це 169/1000 * 100 = 16,9%. Тобто в першій тисячі у відсотковому відношенні прості серед чисел Мерсена зустрічаються майже в 4 рази частіше, ніж серед просто натуральних чисел
___________________________________________________________
А тепер візьмемо конкретне число Мерсена, наприклад 24 - 1. Запишемо його у вигляді двійкового числа.
24 - 1 = 10000 - 1 = 1111
Візьмемо наступне число Мерсена 25 -1 і запишемо його двійковим числом. Отримаємо наступне:
25 -1 = 100000 - 1 = 11111
Вже видно, що всі числа Мерсена являють собою послідовність одиниць і вже сам цей факт дає великий виграш. По-перше, у двійковій системі числення отримати чергове число Мерсена дуже просто, достатньо до чергового числа дописати одиницю, по-друге, шукати подільники у двійковій системі багато простіше ніж в десяткового.
Швидкий переклад десяткового числа в двійкове
Одна з головним проблем використання двійкової системи числення - це складність при перекладі десяткового числа в двійкове. Це досить трудомістка справа. Звичайно, невеликі числа трьох або чотиризначні перевести не надто складно, але для десяткових чисел, в яких 5 і більше знаків це вже скрутно. Тобто нам потрібен спосіб, що дозволяє швидко переводити в двійкове подання великі десяткові числа.
Такий спосіб був придуманий французьким математиком Лежандром. Нехай, наприклад, дано число 11183445. Ділимо його на 64, виходить залишок 21 і приватне 174741. Це число ділимо знову на 64, виходить в залишку 21 і приватне 2730.Наконец, 2730, поділене на 64, дає в залишку 42 і приватне 42. Але 64 в двійковій системі є 1000000, 21 у двійковій системі - 10101, а 42 є 101010, Тому, вихідне число запишеться у двійковій системі таким чином:
42 42 21 21
101010 101010 010101 010101
Щоб було більш зрозуміло, ще один приклад з числом поменше. Переведемо в двійкове уявлення число 235. Поділимо 235 на 64 із залишком. Отримаємо:
ПРИВАТНЕ = 3, двійкове 11 або 000011
ЗАЛИШОК = 43, двійкове 101011
Тоді 235 = 11101011, Перевіримо цей результат:
11101011 = 27 + 26 + 25 + 23 + 21+ 20 = 128+64+32+8+2+1 = 235
Примітки:
Неважко помітити, що в остаточне двійкове число включаються всі залишки і на останньому кроці і залишок і приватне.
1. Приватне записується перед залишком.
2. Якщо отримане приватне або залишок мають менше 6 розрядів, в двійковому поданні (6 нулів містить двійкове подання числа 64 = 1000000), то до нього додаються незначущі нулі.
І ще один складний приклад. Число 25678425.
Крок 1: 25678425 ділимо на 64
Приватне = 401225
Залишок = 25 = 011001
Крок 2: 401225 ділимо на 64
Приватне = 6269
Залишок = 9 = 001001
Крок 3: 6269 ділимо на 64
Приватне = 97
Залишок = 61 = 111101
Крок 4: 97 ділимо на 64
Приватне = 1 = 000001
Залишок = 33 = 100001
Число результат = 1.100001.111101.001001.011001
У цьому числі точкою відокремлені вхідні в нього проміжні результати.
Переведіть в двійкове подання числа:
а) 67579
б) 8765469
в) 76543876
г) 567631113
д) 9809090654
ДОДАТОК: ТАБЛИЦЯ 1
N |
2N |
2-N |
1 |
2 |
0,5 |
2 |
4 |
0,25 |
3 |
8 |
0,125 |
4 |
16 |
0,0625 |
5 |
32 |
0,03125 |
6 |
64 |
0,015625 |
7 |
128 |
0,0078125 |
8 |
256 |
0,00390625 |
9 |
512 |
0,001953125 |
10 |
1024 |
0,0009765625 |
11 |
2048 |
0,00048828125 |
12 |
4096 |
0,000244140625 |
13 |
8192 |
0,0001220703125 |
14 |
16384 |
0,00006103515625 |
15 |
62768 |
0,000030517578125 |
16 |
65536 |
0,0000152587890625 |
17 |
131072 |
0,00000762939453125 |
18 |
262144 |
0,000003814697265625 |
19 |
524288 |
0,0000019073486328125 |
20 |
1048576 |
0,00000095367431640625 |
21 |
4194304 |
0,000000476837158203125 |
22 |
8388608 |
0,0000002384185791015625 |
23 |
16777216 |
0,00000011920928955078125 |
24 |
33554432 |
0,000000059604644775390625 |
25 |
67108864 |
0,0000000298023223876953125 |