Задание EGEINF5F1A93: Рекурсия и рекуррентные зависимости

Дано: аргумент n — целое число. Правила вычисления:
F(n) = n при n ≤ 9.
F(n) = (n − 2) · F(n − 5) при n ≥ 10.
Найти R = F(3220) − 2 · F(3215)F(3210).

Здесь соседние значения функции отличаются известным множителем. Полностью вычислять огромные значения не требуется: выразим все числители через значение функции в знаменателе. Из рекуррентного правила следует F(n) = a(n) · F(n − h), где a(n) — множитель из условия, h — шаг аргумента. Повторяя подстановку, получаем произведение этих множителей и одно общее значение F. Все используемые аргументы находятся в рекуррентной ветви.

Положим C = F(3210). В этой задаче C положительно: последовательное уменьшение аргумента с шагом 5 приводит к положительному начальному значению, а все множители до него положительны. Поэтому деление на C и его сокращение допустимы.

F(3215) = 3213 · F(3210) = 3213 · 1 · C = 3213 · C.
F(3220) = 3218 · F(3215) = 3218 · 3213 · C = 10339434 · C.

Подставляем полученные выражения в исходную дробь и сокращаем общий множитель C. Коэффициенты при C подставляются вместо соответствующих F:
R = 10339434 − 2 · 32131 = 10333008. Результат уже целый, поэтому его целая часть совпадает с ним.

Проверка. У каждого раскрытого значения аргумент уменьшается ровно на шаг из условия. Отношения F(n) к предыдущему значению равны заданным множителям. Независимый расчёт отношений с точной рациональной арифметикой даёт 10333008; округление при делении не использовалось.

Ответ: 10333008.