Ответ
15588
Задание 16 ЕГЭ по информатике
Что проверяет: Рекурсивные алгоритмы
Задание 16 ЕГЭ по информатике проверяет тему «рекурсивные алгоритмы». Ниже вы найдёте 4 варианта с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n при n ≤ 2
F(n) = F(n − 1) + 2 · F(n − 2) при n > 2
Чему равно значение функции F(12)?
Ответ
2048
Считаем по порядку, каждый раз используя два предыдущих значения:
F(1) = 1, F(2) = 2, F(3) = 2 + 2 = 4, F(4) = 4 + 4 = 8, F(5) = 8 + 8 = 16, F(6) = 16 + 16 = 32, F(7) = 64, F(8) = 128, F(9) = 256, F(10) = 512, F(11) = 1024, F(12) = 1024 + 2 · 512 = 2048.
Ответ — 2048.
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n / 2) + n, если n чётное
F(n) = F(n − 1) + 3, если n нечётное и n > 1
Чему равно значение функции F(64)?
Ответ
127
Число 64 — степень двойки, поэтому всё время работает только вторая строка: аргумент каждый раз делится пополам.
F(64) = F(32) + 64, F(32) = F(16) + 32, F(16) = F(8) + 16, F(8) = F(4) + 8, F(4) = F(2) + 4, F(2) = F(1) + 2 = 3.
Разворачиваем обратно: F(4) = 7, F(8) = 15, F(16) = 31, F(32) = 63, F(64) = 127. Ответ — 127.
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n ≤ 1
F(n) = n · F(n − 1) − 1 при n > 1
Чему равно значение функции F(8)?
Ответ
11359
Считаем последовательно: F(1) = 1, F(2) = 2 · 1 − 1 = 1, F(3) = 3 · 1 − 1 = 2, F(4) = 4 · 2 − 1 = 7, F(5) = 5 · 7 − 1 = 34.
Дальше: F(6) = 6 · 34 − 1 = 203, F(7) = 7 · 203 − 1 = 1420, F(8) = 8 · 1420 − 1 = 11359. Ответ — 11359.
Теория к заданию 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 входит в ЕГЭ по информатике. Это единственная страница сайта, где собраны все варианты этого номера: текст условия, картинка задания, правильный ответ, разбор решения и теория с алгоритмом. Остальные номера открываются в списке выше, а их перечень с темами есть в списке заданий ЕГЭ по информатике.