ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Рекурсия и рекуррентные зависимости.
Учебные темы: Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов.
| КЭС: | 3.7 Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов 3.16 Динамическое программирование как метод решения задач с сохранением промежуточных результатов. Задачи, решаемые с помощью динамического программирования: вычисление рекурсивных функций, подсчёт количества вариантов, задачи оптимизации 3.17 Понятие об объектно-ориентированном программировании. Объекты и классы. Свойства и методы объектов. Объектно-ориентированный анализ. Разработка программ на основе объектно-ориентированного подхода. Инкапсуляция, наследование, полиморфизм |
| Тип ответа: | Краткий ответ |
Ответ: 4042
Дано: аргумент n — натуральное число. Правила вычисления:
F(n) = 3 при n ≤ 2.
F(n) = n + F(n − 2) при n ≥ 3.
Найти R = F(2022) − F(2018).
Используем разность значений, чтобы сократить общий остаток рекурсии. Если F(n) = a(n) + F(n − h), то F(n) − F(n − h) = a(n). Для нескольких шагов:
F(n) − F(n − kh) = a(n) + a(n − h) + … + a(n − (k − 1)h).
Каждое промежуточное значение F входит один раз со знаком плюс и один раз со знаком минус, поэтому сокращается.
Здесь h = 2, число раскрытий k = 2. Раскрываем значения до общего остатка F(2018):
F(2022) = 2022 + 2020 + F(2018).
После вычитания F(2018) остаются только добавленные слагаемые:
R = 2022 + 2020 = 2022 + 2020 = 4042.
Все раскрываемые аргументы удовлетворяют условию рекуррентной ветви. До начального значения доходить не нужно: одинаковый остаток сократился точно. Проверка прямым заполнением значений функции от базы даёт F(2022) = 1023133, F(2018) = 1019091. Их разность равна 4042, что подтверждает сокращение.
Ответ: 4042.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF0E2072.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.