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