16.01 Одна функция

Рекурсивное решение

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление. Если , то . Если , то . Нужно перебрать все натуральные из диапазона , вычислить и проверить, заканчивается ли число на в шестнадцатеричной системе. Это то же, что и .

def f(n):
    if n < 32:
        # Для n < 32:
        return n ** 2 + 15
    else:
        # Для n >= 32:
        return f(n // 2) + 15 + f(n - 1)

# Cчётчик подходящих n
ans = 0
# Перебор всех n от 1 до 100 включительно
for i in range(1, 100 + 1):
    # Проверяем, что последняя цифра в hex-формате равна ’F’ (т.е. 15)
    if f(i) % 16 == 15:
        ans += 1

print(ans)