16 номер. Рекурсия
Отношение значений рекурсивной функции
Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = n + 3 при n ≤ 18
F(n) = (n // 3) · F(n // 3) + n - 12 при n > 18 кратных 3
F(n) = F(n-1) + n^2 + 5 при n > 18 не кратных 3
Здесь «//» обозначает деление нацело. Определите количество натуральных значений n из отрезка [1; 1 000] для которых все цифры значения F(n) чётные.
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
Искомая величина: Здесь «//» обозначает деление нацело. Определите количество натуральных значений n из отрезка [1; 1 000] для которых все цифры значения F(n) чётные.
Выпишите базовые значения и границы каждой ветви. Для конкретного аргумента сначала выберите применимое условие, затем подставляйте рекуррентную формулу этой ветви; базовый случай имеет приоритет перед дальнейшим раскрытием.
Если переходы используют меньшие аргументы, заполняйте значения по возрастанию от базовой области. При повторных обращениях используйте сохранённый результат: это позволяет избежать многократного обхода одних и тех же ветвей рекурсии.
Чётность проверяйте для текущего аргумента каждого вызова. Переход на n−1 меняет чётность, переход на n−2 сохраняет её; нельзя продолжать раскрытие одной и той же ветвью только потому, что исходный аргумент был чётным.
Перед вычислением больших значений раскройте рекуррентные формулы в числителе до аргумента знаменателя. Если возникает общий ненулевой множитель, вынесите и сократите его. Сокращать можно общий множитель всего числителя, а не отдельное слагаемое суммы.
После вычисления функции проверяйте требуемое свойство отдельно для каждого допустимого аргумента. Если диапазон слишком велик для перебора, используйте структуру рекурсии и подсчёт состояний; простой подсчёт различных значений функции не равен числу подходящих аргументов.
Ответ: 16.