У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 1,
2. прибавь 4.
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 4. Программа для Удвоителя — это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 15?
Для сложения справедлив коммутативный (переместительный) закон, значит, порядок команд в программе не имеет значения для результата.
Обе команды увеличивают исходное число, поэтому количество команд не может превосходить 15 — 3 = 12. При этом минимальное количество команд — 3 (т. к. [15 − 3]/4 = 3).
Команд может быть 3, 6, 9 или 12. Трём командам соответствует набор 222 (1 вариант расположения), шести командам — набор 221111 (15 возможных вариантов расположения: это число перестановок с повторениями P6(2,4) = 5!/(2! · 3!)), девяти командам — набор 21...1 (9 возможных вариантов расположения) 12 командам — 11...1 (1 вариант расположения). Всего имеем 26 программ.
Ответ: 26.
Приведём другое решение на языке Python.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
else:
return f(x + 1, y) + f(x + 4, y)
print(f(3, 15))