Тип 23 № 8670 
Оператор присваивания и ветвления. Перебор вариантов, построение дерева. Поиск количества программ по заданному числу
i
Исполнитель Увеличитель345 преобразует число, записанное на экране. У исполнителя три команды, которым присвоены номера:
1. Прибавь 3.
2. Прибавь 4.
3. Прибавь 5.
Первая из них увеличивает число на экране на 3, вторая увеличивает это число на 4, а третья — на 5. Программа для исполнителя Увеличитель345 — это последовательность команд.
Сколько есть программ, которые число 22 преобразуют в число 42?
Решение. Заметим, что все операции только лишь прибавляют некоторую константу к числу. Поэтому не важно, в каком порядке выполнять некоторый данный набор команд. Пусть x — количество первых команд, y — вторых, а z — третьих. Составим уравнение:
А именно — найдём с его помощью все наборы команд, которые подходят под условие. И уже для каждого набора в отдельности подсчитаем количество возможных перестановок.
Найдём все решения уравнения: (0, 5, 0), (4, 2, 0), (1, 3, 1), (5, 0, 1), (2, 1, 2), (0, 0, 4).
Количество перестановок для данного набора посчитаем по формуле подсчёта перестановок с повторениями:
Пусть каждого вида команд a, b и с. Тогда всего перестановок из этих команд будет 
Найдём теперь ответ на задачу, просуммировав ответы для каждого набора:
Ответ: 73.
Приведём другое решение на языке Python.
def f(x, y):
if x > y:
return 0
if x == y:
return 1
else:
return f(x + 3, y) + f(x + 4, y) + f(x + 5, y)
print(f(22, 42))
Ответ: 73
PDF-версии: