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

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

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: , где берётся целочисленное деление. Перебираем от 1 до 999 и ищем первое , для которого .

def f(n):
    # База: F(0) = 1
    if n == 0:
        return 1
    # Рекурсивная формула для n > 0:
    return f(0) + f((n - 1) // 3) + f((n - (n - 1) // 3 - 1))

# Ищем минимальное n с F(n) == 1001
# Можно брать диапозон и больше, т.к. делаем выход при нахождении
for n in range(1, 1000):
    if f(n) == 1001:
        print(n)   # Выводим значение и выходим
        break