ЕГЭ информатика, задание 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
Решить это задание в боте @infkostbot
Ещё задания по теме
- Алгоритм вычисления значения функции F(n), где n — натуральное число, задан…
- Алгоритм вычисления значения функции F(n), где n — натуральное число, задан…
- Алгоритм вычисления значения функции F(n), где n — натуральное число, задан…
- Алгоритм вычисления значения функции F(n), где n — натуральное число, задан…