Question

Исполнитель Калькулятор имеет следующую систему команд: 1)прибавь 1 и 2)умножь на 2. С первой из них исполнитель увеличивает число на экране на 2,с второй - в 2 раза 1)Выясните, сколько разных программ, преобразующих число 1 в число 20 можно составить для этого исполнителя. 2)Сколько среди них таких программ,у которых в качестве промежуточного результата обязательно получается число 15? 3)Сколько среди них таких программ,у которых в качестве промежуточного результата никогда не получается 12?

Answer 1

Чтобы решить эту задачу, нам нужно составить последовательности команд, которые преобразуют число 1 в число 20. Для каждой команды 1) (прибавить 1) или 2) (умножить на 2) у нас есть два возможных варианта действий.

1) Чтобы получить число 20, нам нужно 19 раз применить команду 1) и один раз команду 2). Существует два варианта: первым применить команду 1) и затем команду 2), или сначала применить команду 2) и затем команду 1). Поскольку для каждой из 19 команд 1) у нас есть два возможных варианта действия, общее количество программ равно 2^19 = 524288.

2) Теперь рассмотрим программы, в которых в качестве промежуточного результата обязательно получается число 15. Чтобы получить число 15, нам нужно 14 раз применить команду 1) и один раз команду 2). Следовательно, для каждой из 14 команд 1) у нас есть два возможных варианта действия. Общее количество программ, у которых в качестве промежуточного результата получается число 15, равно 2^14 = 16384.

3) Теперь рассмотрим программы, у которых в качестве промежуточного результата никогда не получается число 12. Чтобы промежуточный результат никогда не был равен 12, нам необходимо исключить последовательности команд, которые содержат команду 2) (умножение на 2), так как применение этой команды может привести к числу 12. Значит, нам нужно составить последовательности команд только из команды 1) (прибавить 1).

Чтобы преобразовать число 1 в число 12, нам нужно 11 раз применить команду 1). Следовательно, для каждой из 11 команд 1) у нас есть два возможных варианта действия. Общее количество программ, у которых в качестве промежуточного результата никогда не получается число 12, равно 2^11 = 2048.

Таким образом, ответы на ваши вопросы:
1) Количество программ, преобразующих число 1 в число 20, равно 524288.
2) Количество программ, у которых в качестве промежуточного результата обязательно получается число 15, равно 16384.
3) Количество программ, у которых в качестве промежуточного результата никогда не получается число 12, равно 2048.