Задание 16 ЕГЭ по информатике — Рекуррентные выражения: ручная свёртка
Разбор номера «Рекуррентные выражения: ручная свёртка»: как устроено задание, настоящие формулировки из тренажёра с подсказками и официальным решением. Окно практики открывается сразу — без регистрации и онбординга.
Задание 16 (№16 — Рекуррентные выражения: ручная свёртка) — вопрос первой части экзамена по информатике: короткий ответ, который проверяется автоматически. Ниже — реальные формулировки из тренажёра с подсказками и разбором; проверка работает прямо на этой странице.
Окно примера ниже — то же, что в приложении: подсказки по одной, автопроверка ответа и разбор.
Примеры задания 16
№ 16Пример 1краткий ответ★★★★★1 первичный балл
Алгоритм вычисления функции F(n), где n — целое неотрицательное число, задан следующим соотношением: F(n) = 2 × n, если n < 10; F(n) = F(n − 2) + 3, если n ≥ 10. Чему равно значение F(44)? В ответе запишите целое число.
Подсказка 1. Спускайтесь по рекурсии до базового случая: каждый шаг уменьшает аргумент на 2 и прибавляет 3.
Подсказка 2. Начальный аргумент чётный, поэтому вы дойдёте до чётного базового значения n = 8, где F(8) = 16.
Подсказка 3. Шагов от 44 до 8 будет 18: F(44) = 16 + 3 × 18.
Функция G(n) вычисляется следующим образом: G(n) = 1, если n < 3; G(n) = G(n − 1) + G(n − 3), если n ≥ 3. Сколько раз вызывается функция G (включая вызовы с базовым случаем) при вычислении G(15), если результаты промежуточных вызовов не используются? В ответе запишите целое число.
Подсказка 1. Заведите таблицу: T(n) — число вызовов при вычислении G(n); для базового случая это один вызов.
Подсказка 2. Для n ≥ 3 рекурсивный вызов делает сам вызов плюс вызовы для n − 1 и n − 3.