ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Рекурсия и рекуррентные зависимости.
Учебные темы: Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов.
| КЭС: | 3.7 Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов 3.16 Динамическое программирование как метод решения задач с сохранением промежуточных результатов. Задачи, решаемые с помощью динамического программирования: вычисление рекурсивных функций, подсчёт количества вариантов, задачи оптимизации 3.17 Понятие об объектно-ориентированном программировании. Объекты и классы. Свойства и методы объектов. Объектно-ориентированный анализ. Разработка программ на основе объектно-ориентированного подхода. Инкапсуляция, наследование, полиморфизм |
| Тип ответа: | Краткий ответ |
Ответ: 648
Дано: аргумент n — натуральное число. Правила вычисления:
F(n) = 1 при n ≤ 2.
F(n) = F(n − 1) + n − 1 при n ≥ 3 и n чётно.
F(n) = F(n − 2) + 2 · n − 2 при n ≥ 3 и n нечётно.
Найти R = F(36).
Рекурсия ссылается только на меньшие аргументы. Поэтому вычисляем значения по возрастанию n, начиная с базы. Для каждого нового n сначала определяем его чётность, затем выбираем ровно соответствующую формулу. Значения предыдущих аргументов уже известны; менять местами чётную и нечётную ветви нельзя.
F(1) = 1.
F(2) = 1.
F(3) = F(3 − 2) + 2 · 3 − 2 = 1 + 2 · 3 − 2 = 5.
F(4) = F(4 − 1) + 4 − 1 = 5 + 4 − 1 = 8.
F(5) = F(5 − 2) + 2 · 5 − 2 = 5 + 2 · 5 − 2 = 13.
F(6) = F(6 − 1) + 6 − 1 = 13 + 6 − 1 = 18.
F(7) = F(7 − 2) + 2 · 7 − 2 = 13 + 2 · 7 − 2 = 25.
F(8) = F(8 − 1) + 8 − 1 = 25 + 8 − 1 = 32.
F(9) = F(9 − 2) + 2 · 9 − 2 = 25 + 2 · 9 − 2 = 41.
F(10) = F(10 − 1) + 10 − 1 = 41 + 10 − 1 = 50.
F(11) = F(11 − 2) + 2 · 11 − 2 = 41 + 2 · 11 − 2 = 61.
F(12) = F(12 − 1) + 12 − 1 = 61 + 12 − 1 = 72.
F(13) = F(13 − 2) + 2 · 13 − 2 = 61 + 2 · 13 − 2 = 85.
F(14) = F(14 − 1) + 14 − 1 = 85 + 14 − 1 = 98.
F(15) = F(15 − 2) + 2 · 15 − 2 = 85 + 2 · 15 − 2 = 113.
F(16) = F(16 − 1) + 16 − 1 = 113 + 16 − 1 = 128.
F(17) = F(17 − 2) + 2 · 17 − 2 = 113 + 2 · 17 − 2 = 145.
F(18) = F(18 − 1) + 18 − 1 = 145 + 18 − 1 = 162.
F(19) = F(19 − 2) + 2 · 19 − 2 = 145 + 2 · 19 − 2 = 181.
F(20) = F(20 − 1) + 20 − 1 = 181 + 20 − 1 = 200.
F(21) = F(21 − 2) + 2 · 21 − 2 = 181 + 2 · 21 − 2 = 221.
F(22) = F(22 − 1) + 22 − 1 = 221 + 22 − 1 = 242.
F(23) = F(23 − 2) + 2 · 23 − 2 = 221 + 2 · 23 − 2 = 265.
F(24) = F(24 − 1) + 24 − 1 = 265 + 24 − 1 = 288.
F(25) = F(25 − 2) + 2 · 25 − 2 = 265 + 2 · 25 − 2 = 313.
F(26) = F(26 − 1) + 26 − 1 = 313 + 26 − 1 = 338.
F(27) = F(27 − 2) + 2 · 27 − 2 = 313 + 2 · 27 − 2 = 365.
F(28) = F(28 − 1) + 28 − 1 = 365 + 28 − 1 = 392.
F(29) = F(29 − 2) + 2 · 29 − 2 = 365 + 2 · 29 − 2 = 421.
F(30) = F(30 − 1) + 30 − 1 = 421 + 30 − 1 = 450.
F(31) = F(31 − 2) + 2 · 31 − 2 = 421 + 2 · 31 − 2 = 481.
F(32) = F(32 − 1) + 32 − 1 = 481 + 32 − 1 = 512.
F(33) = F(33 − 2) + 2 · 33 − 2 = 481 + 2 · 33 − 2 = 545.
F(34) = F(34 − 1) + 34 − 1 = 545 + 34 − 1 = 578.
F(35) = F(35 − 2) + 2 · 35 − 2 = 545 + 2 · 35 − 2 = 613.
F(36) = F(36 − 1) + 36 − 1 = 613 + 36 − 1 = 648.
Требуемое значение: R = F(36) = 648.
Проверка. Начальные значения совпадают с базой из условия. Каждая следующая строка использует только уже вычисленные значения и свою ветвь по чётности. Повторный расчёт по зависимостям от искомого аргумента к базовым даёт тот же результат 648. Никакие значения в таблице не округляются.
Ответ: 648.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFD9A32B.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.