Задание 16 ЕГЭ по информатике

Что проверяет: Рекурсивные алгоритмы

Задание 16 ЕГЭ по информатике проверяет тему «рекурсивные алгоритмы». Ниже вы найдёте 1 вариант с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.

Ответ

15588

Теория к заданию 16 ЕГЭ по информатике: рекурсивные алгоритмы

Заданы рекуррентные соотношения, и нужно вычислить значение функции при большом аргументе.

Что нужно знать

Рекурсия имеет базовый случай (условие остановки) и рекуррентный шаг.
Прямое разворачивание для больших аргументов невозможно, поэтому нужна формула или закономерность.
Если шаг уменьшает аргумент на 2 и прибавляет 1, значение растёт линейно: число шагов до базы равно (n − база) / 2.
Чётность аргумента определяет, на каком именно значении сработает базовый случай.
После нахождения G(n) значение F(n) считается подстановкой в первое соотношение.

Рекурсия

Базовый случай задаёт значение функции при малых аргументах. С него начинается вычисление.
Рекуррентное соотношение выражает F(n) через значения при меньших аргументах.
Считайте снизу вверх: заполняйте таблицу значений от базового случая, а не раскрывайте рекурсию сверху.
Часто ответ подчиняется простой формуле: проверьте первые 5-6 значений на арифметическую или геометрическую прогрессию.
Если функция вызывает себя дважды, число вызовов растёт экспоненциально, поэтому считайте значения, а не вызовы, если не спрашивают обратное.
Вопрос «сколько раз будет вызвана функция» решается отдельной рекуррентой для количества вызовов.
Короткая программа с таблицей значений надёжнее ручного счёта при больших n.
Проверяйте базовый случай отдельно: его часто теряют.

Как решать задание 16

Определите базовый случай и рекуррентный шаг.
Посчитайте несколько значений вручную и найдите закономерность.
Выведите формулу для произвольного n, учитывая чётность.
Подставьте нужный аргумент и вычислите значение внутренней функции.
Подставьте результат во внешнюю функцию и запишите ответ.

Разбор примера

F(1) = 1; F(n) = F(n−1) + 2n при n > 1. Найдите F(5).

Начинаем с базового случая: F(1) = 1.
F(2) = F(1) + 2·2 = 1 + 4 = 5.
F(3) = F(2) + 2·3 = 5 + 6 = 11.
F(4) = F(3) + 2·4 = 11 + 8 = 19.
F(5) = F(4) + 2·5 = 19 + 10 = 29.

Ответ29

Частые ошибки

Не учитывают чётность аргумента и промахиваются мимо базового случая.
Останавливают разворачивание рекурсии на неверном условии.

Задание 16 входит в ЕГЭ по информатике. На этой странице собраны все варианты этого номера, которые разобраны на сайте: условие, правильный ответ и разбор решения. Остальные номера открываются в списке выше, а целиком все задания ЕГЭ по информатике с ответами собраны на странице предмета.