Условие: № 8479 (Уровень: Базовый)
(В. Рыбальченко) Исполнитель Великий Изменитель преобразует число, записанное на доске. У Великого Изменителя есть три команды:
1. Вычти 5
2. Вычти 4
3. Раздели на 2
Первая команда уменьшает число на 5, вторая команда уменьшает его на 4, третья команда применяется только к четным числам и делит их на 2.
Сколько существует программ, для которых при исходном числе 100 результатом является число 2, а траектория вычислений обязательно содержит числа 73, 22 и не содержит число 50?
def f(a, b):
if a < b or a == 50:
return 0
elif a == b:
return 1
else:
if a % 2 == 0:
return f(a - 5, b) + f(a - 4, b) + f(a // 2, b)
else:
return f(a - 5, b) + f(a - 4, b)
print(f(100, 73) * f(73, 22) * f(22, 2))
Комментарии к коду программы:
- def f(a, b): - Создаем функцию f, которая принимает два аргумента: a - траектория движения, b - точка выхода.
- if a < b or a == 50: - Проверяем, меньше ли значение a значения b или равно ли значение a 50 (траектория не содержит).
- return 0 - Возвращаем значение 0, если идя по траектории мы проскакиваем точку выхода b или попадаем на 50.
- elif a == b: - Проверяем, равно ли значение a значению b.
- return 1 - Возвращаем значение 1, если идя по траектории мы попадаем в нашу точку выхода b.
- else: - В противном случае мы находимся в пути, значит вызываем рекурсию.
- if a % 2 == 0: - Проверяем, является ли значение a четным числом.
- return f(a - 5, b) + f(a - 4, b) + f(a // 2, b) - Возвращаем сумму результатов выражения f(a - 5, b), f(a - 4, b) и f(a // 2, b), если условие в строке 7 верно.
- else: - В противном случае.
- return f(a - 5, b) + f(a - 4, b) - Возвращаем сумму результатов выражений f(a - 5, b) и f(a - 4, b), если условие в строке 9 верно.
- print(f(100, 73) * f(73, 22) * f(22, 2)) - Выводим на экран результат произведения результатов трех вызовов функции f.
Почему умножение? Потому что траектории будут пересекаться, если из 100 в 73 есть 2 пути, а из 72 в 22 будет 3 пути, то суммарно у нас будет 2*3=6 путей.
def f(a, b):
if a <= b or a == 50:
return a == b
if a % 2 == 0:
return f(a - 5, b) + f(a - 4, b) + f(a // 2, b)
else:
return f(a - 5, b) + f(a - 4, b)
print(f(100, 73) * f(73, 22) * f(22, 2))
