ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Рекурсия и рекуррентные зависимости.
Учебные темы: Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов.
| КЭС: | 3.7 Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов 3.16 Динамическое программирование как метод решения задач с сохранением промежуточных результатов. Задачи, решаемые с помощью динамического программирования: вычисление рекурсивных функций, подсчёт количества вариантов, задачи оптимизации 3.17 Понятие об объектно-ориентированном программировании. Объекты и классы. Свойства и методы объектов. Объектно-ориентированный анализ. Разработка программ на основе объектно-ориентированного подхода. Инкапсуляция, наследование, полиморфизм |
| Тип ответа: | Краткий ответ |
Ответ: 3194
Дано: аргумент n — натуральное число. Правила вычисления:
F(n) = 2 при n ≤ 2.
F(n) = F(n − 2) + F(n − 1) − n при n ≥ 3 и n чётно.
F(n) = F(n − 1) − F(n − 2) + 2 · n при n ≥ 3 и n нечётно.
Найти R = F(32).
Рекурсия ссылается только на меньшие аргументы. Поэтому вычисляем значения по возрастанию n, начиная с базы. Для каждого нового n сначала определяем его чётность, затем выбираем ровно соответствующую формулу. Значения предыдущих аргументов уже известны; менять местами чётную и нечётную ветви нельзя.
F(1) = 2.
F(2) = 2.
F(3) = F(3 − 1) − F(3 − 2) + 2 · 3 = 2 − 2 + 2 · 3 = 6.
F(4) = F(4 − 2) + F(4 − 1) − 4 = 2 + 6 − 4 = 4.
F(5) = F(5 − 1) − F(5 − 2) + 2 · 5 = 4 − 6 + 2 · 5 = 8.
F(6) = F(6 − 2) + F(6 − 1) − 6 = 4 + 8 − 6 = 6.
F(7) = F(7 − 1) − F(7 − 2) + 2 · 7 = 6 − 8 + 2 · 7 = 12.
F(8) = F(8 − 2) + F(8 − 1) − 8 = 6 + 12 − 8 = 10.
F(9) = F(9 − 1) − F(9 − 2) + 2 · 9 = 10 − 12 + 2 · 9 = 16.
F(10) = F(10 − 2) + F(10 − 1) − 10 = 10 + 16 − 10 = 16.
F(11) = F(11 − 1) − F(11 − 2) + 2 · 11 = 16 − 16 + 2 · 11 = 22.
F(12) = F(12 − 2) + F(12 − 1) − 12 = 16 + 22 − 12 = 26.
F(13) = F(13 − 1) − F(13 − 2) + 2 · 13 = 26 − 22 + 2 · 13 = 30.
F(14) = F(14 − 2) + F(14 − 1) − 14 = 26 + 30 − 14 = 42.
F(15) = F(15 − 1) − F(15 − 2) + 2 · 15 = 42 − 30 + 2 · 15 = 42.
F(16) = F(16 − 2) + F(16 − 1) − 16 = 42 + 42 − 16 = 68.
F(17) = F(17 − 1) − F(17 − 2) + 2 · 17 = 68 − 42 + 2 · 17 = 60.
F(18) = F(18 − 2) + F(18 − 1) − 18 = 68 + 60 − 18 = 110.
F(19) = F(19 − 1) − F(19 − 2) + 2 · 19 = 110 − 60 + 2 · 19 = 88.
F(20) = F(20 − 2) + F(20 − 1) − 20 = 110 + 88 − 20 = 178.
F(21) = F(21 − 1) − F(21 − 2) + 2 · 21 = 178 − 88 + 2 · 21 = 132.
F(22) = F(22 − 2) + F(22 − 1) − 22 = 178 + 132 − 22 = 288.
F(23) = F(23 − 1) − F(23 − 2) + 2 · 23 = 288 − 132 + 2 · 23 = 202.
F(24) = F(24 − 2) + F(24 − 1) − 24 = 288 + 202 − 24 = 466.
F(25) = F(25 − 1) − F(25 − 2) + 2 · 25 = 466 − 202 + 2 · 25 = 314.
F(26) = F(26 − 2) + F(26 − 1) − 26 = 466 + 314 − 26 = 754.
F(27) = F(27 − 1) − F(27 − 2) + 2 · 27 = 754 − 314 + 2 · 27 = 494.
F(28) = F(28 − 2) + F(28 − 1) − 28 = 754 + 494 − 28 = 1220.
F(29) = F(29 − 1) − F(29 − 2) + 2 · 29 = 1220 − 494 + 2 · 29 = 784.
F(30) = F(30 − 2) + F(30 − 1) − 30 = 1220 + 784 − 30 = 1974.
F(31) = F(31 − 1) − F(31 − 2) + 2 · 31 = 1974 − 784 + 2 · 31 = 1252.
F(32) = F(32 − 2) + F(32 − 1) − 32 = 1974 + 1252 − 32 = 3194.
Требуемое значение: R = F(32) = 3194.
Проверка. Начальные значения совпадают с базой из условия. Каждая следующая строка использует только уже вычисленные значения и свою ветвь по чётности. Повторный расчёт по зависимостям от искомого аргумента к базовым даёт тот же результат 3194. Никакие значения в таблице не округляются.
Ответ: 3194.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF3E7B68.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.