Задание 23. Информатика. 2022-4
- Просмотры: 52
- Изменено: 24 ноября 2024
Исполнитель Увеличитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
Первая команда увеличивает число на экране на \(2\), вторая увеличивает это число на \(10\). Программа для исполнителя Увеличитель — это последовательность команд. Сколько существует программ, которые число \(7\) преобразует в число \(121\)?
Решение:
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(7, 121))
Второй способ
Чтобы получить из \(7\) число \(121\), можно прибавить \(57\) раз двойку.
Можно один раз прибавить \(10\) и \(52\) раза прибавить \(2\). Всего таких программ будет \( C^{1}_{53} = 53\). И т.д.
Получаем формулу $$ C^{0}_{57} + C^{1}_{53} + C^{2}_{49} + \ldots + C^{11}_{13}$$
Python 3.8+
import math
s = 0
for i in range(12):
s += math.comb(57 - i*4, i)
print(s)
Ответ: 4615966