ЕГЭ 16 · Рекуррентные выражения
Вычисление рекурсивной функции
(С. Чайкин) Алгоритм вычисления значения функции F(n), где n — целое число, задан следующими соотношениями:
F(n) = { n, если n < 10,; F(n % 10) + F(n // 10), если n ≥ 10 }
Определите количество натуральных значений n, меньших 263, для которых F(n) = 159.
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Разбор
Заметим, что F(n) вычисляет сумму цифр десятичной записи числа, поэтому сделаем рекурсивную функцию, которая будет считать
количество числовых последовательностей, не превышающих 2^{63}-1, сумма элементов которых равна 159.
Пусть эта функция f(s, l, fl), где s — сумма элементов, l — длина оставшейся части последовательности, fl — "особый флаг".
Главная сложность задачи — ограничить выбор элементов в рекурсии, чтобы находить только числа, которые меньше верхней границы.
Одним из возможных способов решения является ограничение следующей цифры. Для примера изменим наше ограничение с 2^{63} на 2^4. Очевидно, что на первом месте последовательности может быть только 2 цифры (0 и 1). Если выбрать 0, то следующая цифра может быть любой, так как наше число никак не сможет превысить верхнюю границу. Если же выбрать 1, следующая цифра не может быть больше 5, так как в ином случае у нас могут быть числа не менее 16. Таким образом, зная текущую цифру, мы можем заранее сказать, какое ограничение будет у следующей цифры. Если хотя бы одна цифра в записи меньше граничной, все последующие цифры могут принимать значение от 0 до 9. Чтобы правильно работать с этим ограничением и нужен параметр fl.
from functools import * # граничное значениеa = list(map(int, str(2**63-1))) @cachedef f(s, l, fl): # если последовательность нужной длины, проверяем, что сумма нам подходит, # и выходим из рекурсии. if l == 0: return s == 159 # проверяем ограниченные подпоследовательности большей длины return sum(f(s+x, l-1, fl and (x == a[-l])) for x in range([10, a[-l]+1][fl])) # ответ - количество ограниченных последовательностей необходимой длиныprint(f(0, len(a), 1))