16 номер. Рекурсия
Вычисление рекурсивной функции
(М. Попков) Организатор новогоднего праздника занимается планированием программы для гостей. Существует функция F(n), которая позволяет посчитать стоимость праздника в рублях в зависимости от количества людей n:
F(n) = n при n ≤ 5;
F(n) = 2n - 8 + F(n - 2) + F(n - 1) // 8, если n > 5.
Сколько рублей необходимо выделить, если праздновать будут 163 человека?
Здесь // - обозначает целочисленное деление.
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
Искомая величина: Сколько рублей необходимо выделить, если праздновать будут 163 человека?
Выпишите базовые значения и границы каждой ветви. Для конкретного аргумента сначала выберите применимое условие, затем подставляйте рекуррентную формулу этой ветви; базовый случай имеет приоритет перед дальнейшим раскрытием.
Если переходы используют меньшие аргументы, заполняйте значения по возрастанию от базовой области. При повторных обращениях используйте сохранённый результат: это позволяет избежать многократного обхода одних и тех же ветвей рекурсии.
После вычисления функции проверяйте требуемое свойство отдельно для каждого допустимого аргумента. Если диапазон слишком велик для перебора, используйте структуру рекурсии и подсчёт состояний; простой подсчёт различных значений функции не равен числу подходящих аргументов.
Ответ: 5614207.