Задание 23. Информатика. 2022-3
- Просмотры: 12
- Изменено: 16 сентября 2024
Исполнитель Увеличитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
Первая команда увеличивает число на экране на \(2\), вторая увеличивает это число на \(10\). Программа для исполнителя Увеличитель — это последовательность команд. Сколько существует программ, которые число \(5\) преобразует в число \(141\)?
Решение:
Python
def f(n, target):
if n == target:
return 1
elif n > target:
return 0
else:
return f(n+2, target) + f(n+10, target)
print(f(5, 141))
Второй способ
Чтобы получить из \(5\) число \(141\), можно прибавить \(68\) раз двойку.
Можно один раз прибавить \(10\) и \(63\) раза прибавить \(2\). Всего таких программ будет \( C^{1}_{64} = 64\). И т.д.
Получаем формулу $$ C^{0}_{68} + C^{1}_{64} + C^{2}_{60} + \ldots + C^{13}_{16}$$
Python 3.8+
import math
s = 0
for i in range(14):
s += math.comb(68 - i*4, i)
print(s)
Ответ: 101770120