Алгоритм вычисления значения функции 
, где 
— целое неотрицательное число, задан следующими соотношениями:
, если 
чётно;
, если 
нечётно.
Назовите минимальное значение 
, для которого 
.
Решение динамикой:
f = [0]*4097
for n in range(1, 4097):
if n == 0:
f[n] = 0
elif n > 0 and n % 2 == 0:
f[n] = f[n//2]
else:
f[n] = 1 + f[n-1]
if f[n] == 12:
print(n)
Решение рекурсией:
def F(n):
if n == 0:
return 0
if n % 2 == 0 and n > 0:
return F(n / 2)
if n % 2 != 0:
return 1 + F(n - 1)
i = 0 # Начинаем проверять числа с 0
while F(i) != 12: # Пока не нашли нужное число i
i += 1 # Увеличиваем его на 1
print(i)
Ответ: 4095