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

Дана рекурсия ; если и чётно, то ; если нечётно, то . Требуется найти минимальное , для которого . Для решения динамикой создадим список для хранения значение функции, где каждому i-тому элементу соответсвует . Последовательно заполним список и выведем значение, если .

Динамическое решение

f = [0] * 4097  # f[n] будет хранить F(n)
for n in range(1, 4097):
    # База для n = 0
    if n == 0:
        f[n] = 0
    # Чётное n
    elif n > 0 and n % 2 == 0:
        f[n] = f[n//2]
    # Нечётное n
    else:
        f[n] = 1 + f[n-1]
    # Если находим n, при котором f(n) = 12
    if f[n] == 12:
        # Пишем значение
        print(n)
        break

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

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

def F(n):
    # База для n = 0
    if n == 0:
        return 0
    # Чётное n
    if n % 2 == 0 and n > 0:
        return F(n // 2)
    # Нечётное n
    if n % 2 != 0:
        return 1 + F(n - 1)
i = 0  # Начинаем проверять числа с 0
while F(i) != 12:  # Пока не нашли нужное число i
    i += 1  # Увеличиваем его на 1
print(i)