ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Рекурсия и рекуррентные зависимости.
Учебные темы: Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов.
| КЭС: | 3.7 Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов 3.16 Динамическое программирование как метод решения задач с сохранением промежуточных результатов. Задачи, решаемые с помощью динамического программирования: вычисление рекурсивных функций, подсчёт количества вариантов, задачи оптимизации 3.17 Понятие об объектно-ориентированном программировании. Объекты и классы. Свойства и методы объектов. Объектно-ориентированный анализ. Разработка программ на основе объектно-ориентированного подхода. Инкапсуляция, наследование, полиморфизм |
| Тип ответа: | Краткий ответ |
Ответ: 4049
Дано: аргумент n — натуральное число. Правила вычисления:
F(n) = 3 при n = 1.
F(n) = n + 2 + F(n − 1) при n ≥ 2.
Найти R = F(2023) − F(2021).
Используем разность значений, чтобы сократить общий остаток рекурсии. Если 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 = 1, число раскрытий k = 2. Раскрываем значения до общего остатка F(2021):
F(2023) = 2023 + 2 + 2022 + 2 + F(2021).
После вычитания F(2021) остаются только добавленные слагаемые:
R = 2023 + 2 + 2022 + 2 = 2025 + 2024 = 4049.
Все раскрываемые аргументы удовлетворяют условию рекуррентной ветви. До начального значения доходить не нужно: одинаковый остаток сократился точно. Проверка прямым заполнением значений функции от базы даёт F(2023) = 2051322, F(2021) = 2047273. Их разность равна 4049, что подтверждает сокращение.
Ответ: 4049.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFEFFD84.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.