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