ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Рекурсия и рекуррентные зависимости.
Учебные темы: Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов.
| КЭС: | 3.7 Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов 3.16 Динамическое программирование как метод решения задач с сохранением промежуточных результатов. Задачи, решаемые с помощью динамического программирования: вычисление рекурсивных функций, подсчёт количества вариантов, задачи оптимизации 3.17 Понятие об объектно-ориентированном программировании. Объекты и классы. Свойства и методы объектов. Объектно-ориентированный анализ. Разработка программ на основе объектно-ориентированного подхода. Инкапсуляция, наследование, полиморфизм |
| Тип ответа: | Краткий ответ |
Ответ: 262124
Дано: аргумент n — целое неотрицательное число. Правила вычисления:
F(n) = 0 при n ≤ 1.
F(n) = n + 12 + F(n − 1) при n ≥ 2 и n нечётно.
F(n) = 2 · F(n − 1) + 1 при n ≥ 2 и n чётно.
Найти R = F(33).
Рекурсия ссылается только на меньшие аргументы. Поэтому вычисляем значения по возрастанию n, начиная с базы. Для каждого нового n сначала определяем его чётность, затем выбираем ровно соответствующую формулу. Значения предыдущих аргументов уже известны; менять местами чётную и нечётную ветви нельзя.
F(0) = 0.
F(1) = 0.
F(2) = 2 · F(2 − 1) + 1 = 2 · 0 + 1 = 1.
F(3) = 3 + 12 + F(3 − 1) = 3 + 12 + 1 = 3.
F(4) = 2 · F(4 − 1) + 1 = 2 · 3 + 1 = 7.
F(5) = 5 + 12 + F(5 − 1) = 5 + 12 + 7 = 10.
F(6) = 2 · F(6 − 1) + 1 = 2 · 10 + 1 = 21.
F(7) = 7 + 12 + F(7 − 1) = 7 + 12 + 21 = 25.
F(8) = 2 · F(8 − 1) + 1 = 2 · 25 + 1 = 51.
F(9) = 9 + 12 + F(9 − 1) = 9 + 12 + 51 = 56.
F(10) = 2 · F(10 − 1) + 1 = 2 · 56 + 1 = 113.
F(11) = 11 + 12 + F(11 − 1) = 11 + 12 + 113 = 119.
F(12) = 2 · F(12 − 1) + 1 = 2 · 119 + 1 = 239.
F(13) = 13 + 12 + F(13 − 1) = 13 + 12 + 239 = 246.
F(14) = 2 · F(14 − 1) + 1 = 2 · 246 + 1 = 493.
F(15) = 15 + 12 + F(15 − 1) = 15 + 12 + 493 = 501.
F(16) = 2 · F(16 − 1) + 1 = 2 · 501 + 1 = 1003.
F(17) = 17 + 12 + F(17 − 1) = 17 + 12 + 1003 = 1012.
F(18) = 2 · F(18 − 1) + 1 = 2 · 1012 + 1 = 2025.
F(19) = 19 + 12 + F(19 − 1) = 19 + 12 + 2025 = 2035.
F(20) = 2 · F(20 − 1) + 1 = 2 · 2035 + 1 = 4071.
F(21) = 21 + 12 + F(21 − 1) = 21 + 12 + 4071 = 4082.
F(22) = 2 · F(22 − 1) + 1 = 2 · 4082 + 1 = 8165.
F(23) = 23 + 12 + F(23 − 1) = 23 + 12 + 8165 = 8177.
F(24) = 2 · F(24 − 1) + 1 = 2 · 8177 + 1 = 16355.
F(25) = 25 + 12 + F(25 − 1) = 25 + 12 + 16355 = 16368.
F(26) = 2 · F(26 − 1) + 1 = 2 · 16368 + 1 = 32737.
F(27) = 27 + 12 + F(27 − 1) = 27 + 12 + 32737 = 32751.
F(28) = 2 · F(28 − 1) + 1 = 2 · 32751 + 1 = 65503.
F(29) = 29 + 12 + F(29 − 1) = 29 + 12 + 65503 = 65518.
F(30) = 2 · F(30 − 1) + 1 = 2 · 65518 + 1 = 131037.
F(31) = 31 + 12 + F(31 − 1) = 31 + 12 + 131037 = 131053.
F(32) = 2 · F(32 − 1) + 1 = 2 · 131053 + 1 = 262107.
F(33) = 33 + 12 + F(33 − 1) = 33 + 12 + 262107 = 262124.
Требуемое значение: R = F(33) = 262124.
Проверка. Начальные значения совпадают с базой из условия. Каждая следующая строка использует только уже вычисленные значения и свою ветвь по чётности. Повторный расчёт по зависимостям от искомого аргумента к базовым даёт тот же результат 262124. Никакие значения в таблице не округляются.
Ответ: 262124.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF7C0639.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.