Задание №16: Вычисление рекурсивных функций
Основные типы и прототипы задания №16:
Рекурсивные соотношения с мемоизацией
Глубокая рекурсия
Сумма цифр и чётность
Условие задания
Алгоритм вычисления функции F(n), где n – неотрицательное число, задан следующими соотношениями:
F(n) = 0, если n = 0Найдите количество таких чисел в диапазоне от 189 456 678 до 567 654 321, для которых F(n) не делится на 7.
F(n) = F(n–1) + 5·n.
Ответ:
270141174
Решение на Python: Считаем по остаткам вместо перебора
a = 189456678 b = 567654321 total = 0 for r in range(7): n = 700 + r if 5 * n * (n + 1) // 2 % 7 != 0: first = a + (r - a) % 7 total += (b - first) // 7 + 1 print(total)
Этот код разобран по шагам в разборе задания №16: там же типичные ошибки и лайфхаки.