Нещодавно ми з колегою їхали на черговий евент, і він поставив мені просту, здавалося б, загадку:
Отже, ось невеликий опис процесу міркувань про набір можливих рішень.
речовинність
Перше питання, яке потрібно вирішити - це як з нулів отримувати речові числа? Тут, природно, маються на увазі тільки математичні операції ніж суто комп'ютерні: наприклад число можна інвертувати і зрушити, але це має на увазі що ми знаємо скільки в ньому біт. Загалом, обмежимося математикою.
Звичайно ж це факторіал. Факторіал - це зазвичай твір всіх чисел від 1 до, так що наприклад, але у факторіала є одна особливість:, а отже у нас тепер 13 одиниць, а з ними вже можна працювати. І до речі, поки не пізно, зверну увагу на те, що в умові завдання я згадав прості математичні операції. Якби можна було використовувати, наприклад, логарифми, то завдання вже вирішена тому будь-яке натуральне число можна виразити через логарифми, коріння, і три двійки (доказ), а відповідно рішення нашої задачі виглядало б ось так:
Зведення в ступінь
На жаль, числа 2, 3 і 5 йдуть «по собівартості» (тобто щоб зробити 5 потрібно 5 нулів), і відповідно в 13 нулів ми ну ніяк не вкладемося: для вирішення вище потрібно аж 20 нулів!
Відповідно нашим першочерговим завданням стає пошук більш «дешевих» чисел, і тут на допомогу приходять ...
факторіали
Факторіали дають нам не тільки одиниці з якими можна працювати, але також дешеві великі числа. Наприклад, а це значить що за три нуля ми можемо отримати не тільки 3 але також, і так далі. Якщо форма записи означає що число вимагає для запису нулів, то ми отримаємо такі значення:
Більші значення (з точки зору вартості) краще не чіпати. І скажу відразу, що навіть деякі із значень вище ми зможемо згодом трохи поліпшити.
На жаль, рішення вище вимагає на один нуль більше, ніж у нас є.
Це досить безглузде заняття тому двома нулями зайві 10 не набрати, але, по крайней мере, ми виловили той факт, що можливо варто спробувати:
подвійний факторіал
Подвійний факторіал - це теж твір всіх чисел від 1 до, але з кроком 2, тому що наприклад. Само по собі це кардинально змінює картину, і я хочу звернути вашу увагу на два рівності:
, тобто вісімка стала «дешевше» на один нуль.
Але щось тут не так: 42 нам далося пекельною працею, ми заплатили за нього аж 7 нулів. На один нуль поменше і все вийде. Насправді ж, і ось, ура, у нас готове перше рішення:
субфакторіал
Різних факториалов буває багато і субфакторіал - це такий особливий тип факторіала, який визначає кількість заворушень порядку. Вираховується він так
оптимізація завдання
Комусь може здатися, що 13 нулів - це межа мрій, але немає - ось наприклад пара рішень, де використовуються тільки 12 нулів: