ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Рекурсия и рекуррентные зависимости.
Учебные темы: Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов.
| КЭС: | 3.7 Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов 3.16 Динамическое программирование как метод решения задач с сохранением промежуточных результатов. Задачи, решаемые с помощью динамического программирования: вычисление рекурсивных функций, подсчёт количества вариантов, задачи оптимизации 3.17 Понятие об объектно-ориентированном программировании. Объекты и классы. Свойства и методы объектов. Объектно-ориентированный анализ. Разработка программ на основе объектно-ориентированного подхода. Инкапсуляция, наследование, полиморфизм |
| Тип ответа: | Краткий ответ |
Ответ: 114243
Дано: аргумент n — натуральное число. Правила вычисления:
F(n) = 1 при n ≤ 2.
F(n) = F(n − 2) − F(n − 1) при n ≥ 3 и n чётно.
F(n) = 2 · F(n − 1) − F(n − 2) при n ≥ 3 и n нечётно.
Найти R = F(31).
Рекурсия ссылается только на меньшие аргументы. Поэтому вычисляем значения по возрастанию n, начиная с базы. Для каждого нового n сначала определяем его чётность, затем выбираем ровно соответствующую формулу. Значения предыдущих аргументов уже известны; менять местами чётную и нечётную ветви нельзя.
F(1) = 1.
F(2) = 1.
F(3) = 2 · F(3 − 1) − F(3 − 2) = 2 · 1 − 1 = 1.
F(4) = F(4 − 2) − F(4 − 1) = 1 − 1 = 0.
F(5) = 2 · F(5 − 1) − F(5 − 2) = 2 · 0 − 1 = -1.
F(6) = F(6 − 2) − F(6 − 1) = 0 − (−1) = 1.
F(7) = 2 · F(7 − 1) − F(7 − 2) = 2 · 1 − (−1) = 3.
F(8) = F(8 − 2) − F(8 − 1) = 1 − 3 = -2.
F(9) = 2 · F(9 − 1) − F(9 − 2) = 2 · (−2) − 3 = -7.
F(10) = F(10 − 2) − F(10 − 1) = (−2) − (−7) = 5.
F(11) = 2 · F(11 − 1) − F(11 − 2) = 2 · 5 − (−7) = 17.
F(12) = F(12 − 2) − F(12 − 1) = 5 − 17 = -12.
F(13) = 2 · F(13 − 1) − F(13 − 2) = 2 · (−12) − 17 = -41.
F(14) = F(14 − 2) − F(14 − 1) = (−12) − (−41) = 29.
F(15) = 2 · F(15 − 1) − F(15 − 2) = 2 · 29 − (−41) = 99.
F(16) = F(16 − 2) − F(16 − 1) = 29 − 99 = -70.
F(17) = 2 · F(17 − 1) − F(17 − 2) = 2 · (−70) − 99 = -239.
F(18) = F(18 − 2) − F(18 − 1) = (−70) − (−239) = 169.
F(19) = 2 · F(19 − 1) − F(19 − 2) = 2 · 169 − (−239) = 577.
F(20) = F(20 − 2) − F(20 − 1) = 169 − 577 = -408.
F(21) = 2 · F(21 − 1) − F(21 − 2) = 2 · (−408) − 577 = -1393.
F(22) = F(22 − 2) − F(22 − 1) = (−408) − (−1393) = 985.
F(23) = 2 · F(23 − 1) − F(23 − 2) = 2 · 985 − (−1393) = 3363.
F(24) = F(24 − 2) − F(24 − 1) = 985 − 3363 = -2378.
F(25) = 2 · F(25 − 1) − F(25 − 2) = 2 · (−2378) − 3363 = -8119.
F(26) = F(26 − 2) − F(26 − 1) = (−2378) − (−8119) = 5741.
F(27) = 2 · F(27 − 1) − F(27 − 2) = 2 · 5741 − (−8119) = 19601.
F(28) = F(28 − 2) − F(28 − 1) = 5741 − 19601 = -13860.
F(29) = 2 · F(29 − 1) − F(29 − 2) = 2 · (−13860) − 19601 = -47321.
F(30) = F(30 − 2) − F(30 − 1) = (−13860) − (−47321) = 33461.
F(31) = 2 · F(31 − 1) − F(31 − 2) = 2 · 33461 − (−47321) = 114243.
Требуемое значение: R = F(31) = 114243.
Проверка. Начальные значения совпадают с базой из условия. Каждая следующая строка использует только уже вычисленные значения и свою ветвь по чётности. Повторный расчёт по зависимостям от искомого аргумента к базовым даёт тот же результат 114243. Никакие значения в таблице не округляются.
Ответ: 114243.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF4D7975.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.