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