Давайте рассмотрим забавную поучительную задачку с неожиданным решением. Есть разные системы счисления (мы рассматриваем обычные, позиционные, по степеням данного натурального основания), какая самая экономная?
Как это обычно бывает, надо уточнить задачу, определив понятие "экономная". Если понимать это так, что числа короче записываются, то ответа нет: чем больше основание, тем короче запись чисел.
Но цифр надо больше! Для двоичной цифр две, а для шестнадцатеричной их шестнадцать. Вот давайте возьмем некое целое количество n картонок и на них напишем цифры: столько полных наборов, сколько поместится. И сложим из них разные числа.
Если вдруг кто не в курсе, что такое позиционная система счисления. Это способ записи числа ограниченным набором символов — цифр. В системе счисления с основанием d мы делим число на d нацело и остаток есть цифра в данном разряде. Делим 42 на 3, получаем 14 и в остатке нуль: в самом правом разряде нолик. Делим 14 на 3, получаем 4 и в остатке 2: в следующем разряде двойка. Делим 4 на 3, получаем 1 и в остатке 1: в третьем разряде единичка. Делим 1 на 3, получаем нуль и в остатке 1. В итоге 42 в троичной системе есть 1120. Это означает, что 42=3³+3²+2∙3+0∙1=27+9+2∙3+0.
Так можно записать любое число, используя всего три цифры: 0, 1 и 2. Меньше всего цифр в двоичной системе, а сверху ограничений нет.
Есть еще экзотические системы: факториальная, фибоначчиева, с отрицательными цифрами... множество их! В другой раз расскажу.
Такая задача имеет смысл. Из 30 картонок можно сложить 15 двоичных наборов (числа до "2 в 15-ой степени" исключительно, то есть до 32767), 10 троичных (числа до 59049) и три десятичных (всего до 999). Шестнадцатеричных чисел даже два комплекта не наберем, то есть числа даже до 255 не сможем выписать!
Явно не десятичная система самая экономная! Пока что лучше всех троичная.
Можно поставить задачу иначе, но мы рассмотрим такую.
Выбрав основание d, мы имеем n/d комплектов (надо предполагать, что одно делится на другое), а из m комплектов можно сложить d^m чисел. В итоге мы ищем максимум функции целочисленного аргумента d и фиксированным числом n:
Теперь проделаем такой трюк, который греет сердце "непрерывника". Заменим аргумент d на непрерывный, обозначив его x, и ищем максимум функции уже непрерывного аргумента.
Можно использовать аппарат дифференциального исчисления. Если ответ получится целочисленный, он все равно ответ. Если решение дробное, надо проверить двух целочисленных соседей. Если у функции много максимумов и минимумов, могут быть проблемы... но будут проблемы — будем их решать.
Находим производную и приравниваем нулю:
Поскольку функция сама нулю не равна, как и квадрат в знаменателе, то x=e единственное решение. Нетрудно проверить, что это точка максимума, а значит, других максимумов быть не может, как и минимумов и точек перегиба. И что приятно, от n результат не зависит.
А делаем мы это, применяя теорему Ферма (нет, не ту, что Великая): "в точке максимума и минимума производная равна нулю (если есть)". Поэтому решение надо искать среди нулей производной. А их обычно немного.
У нас d целое, то есть надо проверить два значения, полученные округлением числа x=e вниз и вверх. Разобранный выше пример показывает, что d=3 экономнее, чем d=2. И частный пример дает общее решение, потому что результат от n не зависит!
Итак, самая экономная система счисления — троичная.
Давайте еще раз остановимся на важных моментах. Сначала ставим задачу: очевидный ответ "отвали, решения нет" и зануд, которым не нравится результат, сразу отгоняем подальше. Ставим задачу которую можно решить, и решаем, а потом будем думать, что это нам дает, и дает ли.
Потом уходим от дискретной задачи, которую решить трудно, заменяя ее эквивалентной непрерывной, которую решить можно. При этом теоретически возможны сюрпризы, но получается функция с одним максимумом, который один и есть, как на него не смотри.
Применяем аппарат производных по наработанной схеме. Получаем абсудный ответ в стиле "полтора землекопа", но не отчаиваемся, а используем полученную информацию о монотонности функции слева и справа от найденной точки: инами словами, при уменьшении и при увеличении аргумента значение функции убывает. Поэтому целочисленное решение "где-то рядом".
Значит ли полученный результат, что надо срочно переходить на десятичную систему? Нет, конечно. Он значит ровно то, что сформулировано. Тридцать картонок позволят записать более всего чисел в троичном коде, и всё. На втором месте двоичная.
Троичная система пригождается иногда. Например, она позволяет описать Канторово множество. Оно получается из отрезка рекурсивно удалением средних частей: от 1/3 до 2/3 (концы оставляем). В троичном коде удаляются числа, содержащие в своей записи единички, а остаются те, что составлены из нулей и двоек. Правда, надо договориться насчет чисел с единичкой в периоде. Заменив двойки на единички и толкуя результат как двоичное разложение, мы получаем взаимно-однозначное отображение Канторова множества на весь отрезок. Что забавно, ибо при построении Канторова множества выкидывается вся длина. Подробнее я расскажу в отдельной заметке.
А мораль сей басни проста: смотреть надо не столько на доказательства оптимальности, сколько на постановку задачи! Потому что доказать легко: задачу правильно поставить трудно. А так "оптимизаторы" вам заоптимизируют всё, что угодно, и всё будет правильно, как в том анекдоте.
