Задание 16. Информатика. ЕГЭ. Поляков-5731

(А. Кабанов) Алгоритм вычисления значения функции \(F(n),\) где \(n\) – натуральное число, задан следующими соотношениями:

• \(F(n) = n,\) если \(n \geqslant 10~000,\)
• \(F(n) = n \, / \, 4 + F(n \, / \, 4 + 2),\) если \(n < 10~000\) и \(n\) делится на \(4,\)
• \(F(n) = 1 + F(n + 2),\) если \(n < 10~000\) и \(n\) не делится на \(4.\)

Чему равно значение выражения \(F(174) - F(3)?\)

F = {n: n for n in range(10_000, 10_050)}

for n in range(9999, 0, -2):
    F[n] = 1 + F[n + 2]
for n in range(4, 10_000, 8):
    F[n] = n // 4 + F[n // 4 + 2]
for n in range(8, 10_000, 8):
    F[n - 6] = 1 + F[n - 4]
    F[n] = n // 4 + F[n // 4 + 2]
    F[n - 2] = 1 + F[n]
    
print(F[174] - F[3])