Question

Исполнитель Калькулятор имеет две команды: Прибавь 1, Умножь на 2 Первая команда увеличивает число на 1, вторая умножает число на 2. Например, первая команда преобразует число 5 в число 6, вторая преобразует число 5 в число 10. Сколько существует программ для этого исполнителя, преобразующих число 2 в число 15?

Answer 1

Ответ:

Начнем рассуждать с конца. Последнее число, к которому можно применить обе команды - это 7. Значит от числа 8 остается только прибавлять единицы. Суммарное число команд от 8 - 1. Далее из 7 можно получить 8 и 14, и из 8, и из 14 только прибавление единиц, значит суммарнное число команд из 7 - 2. Из 6 получаем 7 и 12. Выяснили, что из 7 две команды, из 12 одна, значит суммарно из 6 - 3. Из 5 получаем 6 и 10, выяснили, что из 6 три команды, из 10 только прибавление единиц, значит одна, из 5 - 4 команды. Из 4 получим либо 5, либо 8, как ранее посчитано из 5 четыре команды, из 8 одна, значит из 4 - 5 команд. Из 3 получаем или 4 или 6, как ранее доказано, из 4 пять команд, из 6 три команды, значит суммарно из 3 - 8 команд. И из 2, с которой начинаем по условию получаем либо число 3 (8 команд), либо число 4 (5 команд), значит в сумме 113 вариаций программ.

Объяснение: Ответ: 13 программ.

Answer 2

Существует несколько программ для этого исполнителя, которые преобразуют число 2 в число 15.

Программа 1: Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1, Прибавь 1

Программа 2: Умножь на 2, Умножь на 2, Умножь на 2, Умножь на 2, Умножь на 2, Умножь на 2, Умножь на 2, Умножь на 2, Умножь на 2, Умножь на 2, Умножь на 2

Программа 3: Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1

Программа 4: Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1, Умножь на 2, Прибавь 1

И так далее. В общем случае, для преобразования числа 2 в число 15 с помощью данного исполнителя можно составить различные программы, которые последовательно применяют команды "Прибавь 1" и "Умножь на 2". Количество программ будет равно 2^(15-2) = 2^13 = 8192.