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

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

• \(F(0) = 0\)
• \(F(n) = 1,\) когда \(1 \leqslant n < 3,\)
• \(F(n) = F(n - 1) + F(n - 2),\) когда \(n \geqslant 3.\)

Определите четыре последние цифры числа \(F(47).\)

F = {0: 0}
for n in range(1, 48):
    F[n] = 1 if n < 3 else F[n - 1] + F[n - 2]
print(F[47] % 10_000)