Решение. Рождественская песнь Диккенса (#73)
Ответ: 9 подходов
Решение
Перейдём в двоичную систему счисления.
Заметим, что:
1) При умножении на два количество единиц в двоичной записи числа не меняется, так как умножение на два в двоичной системе счисления равносильно приписыванию справа нулю. При прибавлении единицы количество единиц в двоичной записи числа увеличивается не более, чем на одну.
2) Прибавление единицы к числу, отличному от (2ⁿ-1), не увеличивает количество разрядов в нём. Если же после прибавления единицы мы получаем число 2ⁿ (n > 1), то это означает, что мы пришли к нему не оптимальным образом, так как к числу 2ⁿ (n > 1) оптимальным образом нужно приходить удвоением.
3) В оптимальном случае при прибавлении единицы количество цифр, используемое в двоичной записи числа, не меняется.
Итак, переведём число 73 в двоичную систему счисления: 73 = 1001001. Из пунктов 1) 2) 3) следует, что для получения этого числа требуется не менее 3+6=9 подходов. Вот они: 1 2 4 8 9 18 36 72 73. Следовательно, понадобится 9 подходов.
Замечание: для нахождения оптимальной последовательности операций удобно начинать с конца. Если число на данном шаге чётно, то делим на два. Если нечётно, то уменьшаем на единицу. И так далее до нуля. Обратная последовательность и будет оптимальной.
