Исполнитель Увеличитель245 преобразует число, записанное на экране. У исполнителя три команды, которым присвоены номера:
1. Прибавь 2
2. Прибавь 4
3. Прибавь 5
Первая из них увеличивает число на экране на 2, вторая увеличивает это число на 4, а третья — на 5. Программа для исполнителя Увеличитель245 — это последовательность команд. Сколько есть программ, которые число 31 преобразуют в число 51?
Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения для результата.
Все команды увеличивают исходное число, поэтому количество команд не может превосходить (51 − 31)/2 = 10. При этом минимальное количество команд — 4.
Таким образом, команд может быть 4, 5, 6, 7, 8, 9 или 10. Порядок команд не имеет значения.
Рассмотрим все возможные наборы и вычислим количество вариантов рассположения команд в них.
Набор 11 1111 1111 имеет один возможный вариант.
Набор 11 1111 112 — 9 вариантов.
Набор 11 1111 22 — 28 возможных вариантов расположения: это число перестановок с повторениями 8!/(6!·2!).
Набор 11 112 22 — 35 вариантов.
Набор 11 22 22 — 15 вариантов.
Набор 2 22 22 — 1 вариант.
Набор 3 33 3 — 1 вариант.
Набор 11111 33 — 21 вариант.
Набор 22133 — 30 вариантов.
Набор 211133 — 60 вариантов.
Всего имеем: 1 + 9 + 28 + 35 + 15 + 1 + 1 + 21 + 30 + 60 = 201 программа.
Ответ: 201.
Приведём другое решение на языке Python.
def f(x, y):
if x > y:
return 0
if x == y:
return 1
else:
return f(x + 2, y) + f(x + 4, y) + f(x + 5, y)
print(f(31, 51))