Question

У исполнителя Вычислитель две команды, которым присвоены номера: 1) прибавь 1, 2) прибавь 4, 3) умножь на 3. Первая из них увеличивает число на экране на 1, вторая – на 4, третья – увеличивает его в 3 раза. Программа для Вычислителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 16?

Answer 1

Ответ: 136.

Код на языке Python:

def f(x, y):

   if x > y:

       return 0

   if x == y:

       return 1

   else:

       return f(x + 1, y) + f(x + 4, y) + f(x * 3, y)

print(f(1, 16))

Answer 2

Для того чтобы число 1 преобразовать в число 16 с использованием заданных команд (прибавить 1, прибавить 4, умножить на 3), нужно определить количество способов достичь этой цели. Мы можем использовать команды в разном порядке, и нам нужно учесть все возможные перестановки команд.

1. Первым шагом мы должны увеличить число на 1. Есть только один способ сделать это: "прибавь 1".

2. Далее нам нужно увеличить число 5 раз (16 - 1 = 15). Мы можем использовать "прибавь 4" и "умножь на 3" в произвольном порядке. Это эквивалентно нахождению количества перестановок из 5 элементов, в которых 2 элемента одинаковы (прибавление 4) и 3 элемента одинаковы (умножение на 3).

Количество таких перестановок можно вычислить с помощью биномиального коэффициента.

C(5, 2) - количество способов выбрать 2 из 5 для "прибавь 4". C(3, 3) - количество способов выбрать 3 из 3 для "умножь на 3".

C(5, 2) * C(3, 3) = 10 * 1 = 10 способов.

Итак, есть 10 разных программ, которые могут преобразовать число 1 в число 16, используя заданные команды.