Задание 16 ЕГЭ по информатике — Рекуррентные выражения: ручная свёртка
Разбор номера «Рекуррентные выражения: ручная свёртка»: как устроено задание, настоящие формулировки из тренажёра с подсказками и официальным решением. Окно практики открывается сразу — без регистрации и онбординга.
Задание 16 (№16 — Рекуррентные выражения: ручная свёртка) — вопрос первой части экзамена по информатике: короткий ответ, который проверяется автоматически. Ниже — реальные формулировки из тренажёра с подсказками и разбором; проверка работает прямо на этой странице.
Окно примера ниже — то же, что на сайте: подсказки по одной, автопроверка ответа и разбор.
Примеры задания 16
№ 16Пример 1краткий ответ★★★★★1 первичный балл
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = n + 1 при n ≤ 2; F(n) = 2 · F(n − 1) + F(n − 2) при n > 2. Чему равно значение функции F(4)? В ответе запишите только натуральное число.
Подсказка 1. Найди начальные значения и рекуррентную формулу: с них начинается вся свёртка.
Подсказка 2. Вычисляй значения по возрастанию номера, записывая промежуточные результаты и проверяя формулу на небольшом n.
Подсказка 3. Если спрашивают количество чисел, веди счётчик по подходящим n; типичная ошибка — применить рекуррентную формулу при n меньше граничного.
Разбор.
Решение. Последовательно находим: F(1) = 2; F(2) = 3; F(3) = 6 + 2 = 8; F(4) = 16 + 3 = 19. Таким образом, F(4) = 19. Ответ: 19. Приведём другое решение на языке Python. def F(n): if n 2: return 2*F(n - 1) + F(n - 2) print(F(4))
Ответ.
19
№ 16Пример 2краткий ответ★★★★★1 первичный балл
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n чётно; F(n) = 2 · F(n − 2), если n > 1 и при этом n нечётно. Чему равно значение функции F(26)?
Подсказка 1. Найди начальные значения и рекуррентную формулу: с них начинается вся свёртка.
Подсказка 2. Вычисляй значения по возрастанию номера, записывая промежуточные результаты и проверяя формулу на небольшом n.
Подсказка 3. Если спрашивают количество чисел, веди счётчик по подходящим n; типичная ошибка — применить рекуррентную формулу при n меньше граничного.
Разбор.
Решение. Приведём программу на Паскале, решающий данную задачу: var n: longint; function F(n: longint): longint; begin if n = 1 then F := 1 else if ((n mod 2) = 0) then F := n + F(n - 1) else if (((n mod 2) = 1) and (n > 1)) then F := 2 * F(n - 2); end; begin n := F(26); writeln(n); end. Приведём аналитическое решение. Заметим, что значения функции от нечётных n являются значениями степеней двойки: F(1) = 1, F(3) = 2, F(5) = 4 и так далее. Значит, F(25) = 4096. Тогда F(26) = 26 + 4096 = 4122. Ответ: 4122. Приведём другое решение на языке Python. def F(n): if n == 1: return 1 if n % 2 == 0: return n + F(n - 1) if n % 2 != 0 and n > 1: return 2 * F(n - 2) print(F(26))
Ответ.
4122
Как устроена практика в тренажёре
Опыт за каждое решение
Чистое решение без подсказок ценится выше: опыт, уровни и серии растут с каждым заданием, а не за клики.
Ошибки не пропадают
Нерешённое возвращается в работу над ошибками — тренажёр приведёт к заданию снова, пока оно не закроется без помощи.
Прогноз балла
После нескольких решённых номеров тренажёр показывает прогнозный балл и говорит, какие темы подтянуть, чтобы его поднять.
Закрепи задание 16 в тренажёре
Окно практики откроется сразу — без имени и онбординга. Прогресс сохранится, как только укажешь имя.