Главная › Информатика › №16 · Рекурсия

ЕГЭ информатика, задание 16: №16 · Рекурсия

Алгоритм вычисления значения функции F(n), где n — натуральное число:

F(n) = n при n < 3;

F(n) = F(n − 1) + 2 · F(n − 2) при n ≥ 3.

Чему равно значение F(10)?

Показать ответ и разбор
Ответ: 512

Считаем по порядку снизу вверх: F(1) = 1, F(2) = 2, F(3) = 2 + 2 = 4, F(4) = 4 + 4 = 8, F(5) = 16 … каждый раз удвоение, то есть F(n) = 2ⁿ⁻¹. F(10) = 2⁹ = 512. В Python для больших n добавляй @lru_cache, иначе рекурсия будет считаться очень долго.

Потренируйся в боте. Такие задания с разбором, статистика по темам и работа над ошибками: бесплатно в Telegram.
Решить это задание в боте @infkostbot

Ещё задания по теме