Тип 23 № 11123 
Оператор присваивания и ветвления. Перебор вариантов, построение дерева. Поиск количества программ по заданному числу
i
Исполнитель Вычитатель преобразует число, которое записано на экране. У исполнителя Вычитатель две команды, которым присвоены номера.
1. Вычти 2.
2. Вычти 5.
Первая из них уменьшает число на экране на 2, вторая уменьшает его на 5. Программа для Вычитателя — это последовательность команд. Сколько есть программ, которые число 22 преобразуют в число 2?
Решение. Для вычитания справедлив коммутативный (переместительный) закон, значит, порядок команд в программе не имеет значения для результата.
Обе команды уменьшают исходное число, поэтому количество команд не может превосходить (22 — 2)/2 = 10. При этом минимальное количество команд — 4 (так как [22 − 2] : 5 = 4). Заметим, что 22 — чётное и 2 — четное. Поскольку команда 2 вычитает нечётное число, то команда 2 должна встречаться чётное число раз.
Иначе говоря, команд может быть от четырёх, до десяти.
Четырём командам соответствует набор 2222.
При помощи пяти команд нельзя преобразовать число 22 в число 2.
При помощи шести команд нельзя преобразовать число 22 в число 2.
Семи командам соответствует набор 111 1122. (21 возможный вариант расположения: это число перестановок с повторениями P7(2,5) = 7! / (2! · 5!)).
При помощи восьми команд нельзя преобразовать число 22 в число 2.
При помощи девяти команд нельзя преобразовать число 22 в число 2.
Десяти командам соответствует набор 11 1111 1111.
Всего имеем 23 программы.
Ответ: 23.
Приведём другое решение на языке Python.
def f(x, y):
if x < y:
return 0
if x == y:
return 1
else:
return f(x - 2, y) + f(x - 5, y)
print(f(22, 2))
Ответ: 23
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем