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

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

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

1)

2) , если и чётное

3) , если нечётное

Необходимо найти минимальное , для которого . Для этого перебираем значения от 0 вверх, вычисляем по определению, и при первом совпадении с 12 выводим найденное и останавливаем перебор.

def F(n):
    # База: F(0) = 0
    if n == 0:
        return 0
    # Чётный n > 0: F(n) = F(n // 2)
    if n > 0 and n % 2 == 0:
        return F(n // 2)
    # Нечётный n: F(n) = 1 + F(n - 1)
    if n % 2 == 1:
        return 1 + F(n - 1)

# Перебор для поиска минимального n, где F(n) == 12
for i in range(5000):
    if F(i) == 12:
        # Выводим минимальное найденное n и останавливаемся
        print(i)
        break