Задание 23. Информатика. 2022-1
- Просмотры: 27
- Изменено: 14 сентября 2024
Исполнитель Увеличитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
Первая команда увеличивает число на экране на \(2\), вторая увеличивает это число на \(7\). Программа для исполнителя Увеличитель — это последовательность команд. Сколько существует программ, которые число \(5\) преобразует в число \(49\)?
Решение:
Python
def f(n, target):
if n == target:
return 1
elif n > target:
return 0
else:
return f(n+2, target) + f(n+7, target)
print(f(5, 49))
Аналитическое решение
Числа \(5\) и \(49\) - нечётные. Для сохранения чётности нужно всё время прибавлять чётные числа. Это могут быть либо двойки, либо чётное число семёрок.
Итак, первая возможность - это прибавить \(22\) двойки к \(5\).
Вторая группа команд, это прибавить две \(7\) и \(15\) двоек. Всего - \(17\) слагаемых. Расположить две \(7\) на \(17\) позициях можно \(C^{2}_{17} = 136\) способами.
Следующая группа команд состоит из четырёх \(7\) и восьми \(2\). Всего таких программ \(C^{4}_{12} = 495\).
Наконец, последняя возможность - это прибавить шесть раз \(7\) и одну \(2\). Всего таких программ \(7\).
Собирая всё вместе, общее количество программ будет \(1+136+495+7 = 639\).
Ответ: 639