На цьому ми закінчуємо опис найпростіших арифметичних операцій, які необхідно знати, для того, щоб користуватися двійковій арифметикою, і тепер спробуємо відповісти на питання "Навіщо потрібна двоичная арифметика". Звичайно, вище вже було показано, що запис числа в двійковій системі істотно спрощує арифметичні операції, але в той же час сама запис стає значно довше, що зменшує цінність отриманого спрощення, тому необхідно пошукати такі завдання, вирішення яких істотно простіше в довічних числах.
Завдання 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 Це нульове двійковечисло означатиме нульову вибірку з якої і почнеться процес складання вибірок. Розряди числа вважаються справа наліво, тобто самий лівий розряд це найстарший.
Домовимося позначати це двійкове число великими буквами двійкову
Якщо двійкового числа складається цілком з одиниць
Те припиняємо роботу алгоритму
§ Додаємо до двійкового числа одиницю за правилами двійковій арифметики.
§ З отриманого двійкового числа складаємо чергову вибірку, як було описано вище.
Завдання 2: Пошук великих простих чисел
Для початку згадаємо, що простим числом називається таке натуральне число, яке ділиться тільки на 1 і на саме себе. Приклади простих чисел: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.
Пошук великих простих чисел - дуже важлива математична задача. Великі прості числа необхідні для надійного шифрування повідомлень деякими алгоритмами шифрування. Причому потрібні не просто великі числа, а дуже великі. Чим число більше, тим надійніше шифр, побудований на цьому числі.
Примітка. Надійним шифром називається такий шифр, для розшифровки якого потрібно дуже великий час.
Чому? Просте число грає роль ключа при кодуванні і дешифрування. Крім того, ми знаємо, що прості числа зустрічаються в ряду натуральних чисел не надто часто. Їх досить багато серед першої тисячі, потім їх кількість починає швидко зменшуватися. Тому якщо в якості ключа ми візьмемо не дуже велике число, дешифрувальників за допомогою навіть не дуже швидкого комп'ютера зможе до нього дістатися (перебираючи в якості ключа все прості одне за іншим) за обмежений час.
Досить надійний код можна отримати якщо взяти просте в якому, наприклад 150 знаків. Однак, знайти таке просте не так просто. Припустимо, що деяке число А (дуже велике) потрібно перевірити на простоту. Це те ж саме, що пошукати його подільники. Якщо ми зможемо знайти подільники в інтервалі від 2 до корінь квадратний з А, то воно не просте. Оцінимо кількість чисел які необхідно перевірити на здатність розділити число А.
Припустимо число А має 150 знаків. Корінь квадратний з нього буде містити не менше 75 знаків. Щоб перебрати таку кількість можливих дільників нам буде потрібно дуже потужний комп'ютер і величезна час, а це означає, що завдання практично не вирішується.
Як з цим боротися
По-перше, можна повчиться швидше здійснювати перевірку на подільність одного числа на інше, по-друге можна спробувати число А підбирати таким чином, щоб воно було простим з високим ступенем ймовірності. Виявляється це можливо. Математик Мерсен виявив, що числа наступного виду
Є простими з високим ступенем ймовірності.
Щоб зрозуміти написану вище фразу, порахуємо, скільки простих чисел знаходиться в першій тисячі, і скільки чисел Мерса в цій же тисячі є простими. Отже, числа Мерса в першій тисячі - це такі:
2 1 - 1 = 1; 2 + 2 -1 = 3; 2 3 - 1 = 7; 2 4 - 1 = 15; 2 5 - 1 = 31; 2 6 -1 = 63;
2 7 - 1 = 127; 2 8 -1 = 255; 2 9 - 1 = 511;
Жирним шрифтом позначені прості числа. Всього на 9 чисел Мерса 5 простих. У відсотках це 5/9 * 100 = 55,6%. У той же час на 1000 перших натуральних чисел тільки 169 простих. У відсотках це 169/1000 * 100 = 16,9%. Тобто в першій тисячі у відсотковому відношенні прості серед чисел Мерса зустрічаються майже в 4 рази частіше, ніж серед просто натуральних чисел
А тепер візьмемо конкретне число Мерса, наприклад, 2 4 - 1. Запишемо його у вигляді двійкового числа.
2 4 - 1 = 10000 - 1 = 1111
Візьмемо наступне число Мерса 2 5 -1 і запишемо його двійковим числом. Отримаємо наступне:
2 5 -1 = 100000 - 1 = 11111
Вже видно, що всі числа Мерса представляють собою послідовність одиниць, і вже сам цей факт дає великий виграш. По-перше, в двійковій системі числення дуже просто отримати чергове число Мерса. Для цього достатньо до чергового числа дописати одиницю. По-друге, шукати подільники в двійковій системі на багато простіше, ніж в десяткової.