Записки репетитора

Алгоритм вычисления значения функции $F(n)$, где $n \in N$, задан следующими соотношениями:

$F(n) = n!$, если $n \ge 5000$,

$F(n) = 2 · F(n + 1) / (n + 1)$, если $1 \le n \le 5000$.

Чему равно значение выражения $1000 \cdot F(7) / F(4)$?

Примечание. Факториал числа $n$, который обозначается как $n!$, вычисляется по формуле $n!=1·2·…·n$.

Сразу видим, что данная рекурсивная функция вычисляться «в лоб» на компьютере не будет, даже на python, где целое число может иметь большую длину.

Рассмотрим $n = 4999$

В этом случае функция будет вычисляться так:

$F(4999) = 2\cdot \frac{F(5000)}{5000}$

Мы помним, что $F(5000) = 5000!$

Поэтому $F(4999) = 2\cdot \frac{5000!}{5000}$

Теперь пусть $n=4998$

$F(4998) = 2\cdot \frac{F(4999)}{4999} = 2\cdot \frac{2\cdot \frac{5000!}{5000}}{4999} = 2\cdot 2\cdot \frac{5000!}{4999\cdot 5000}$

Теперь пусть $n=4997$

$F(4997) = 2^3 \cdot \frac{5000!}{4998 \cdot 4999\cdot 5000}$

Можем вывести теперь формулу для произвольного $n<5000$.

$F(n) = 2^{5000-n}n!$

Теперь можем посчитать ответ:

$1000 \cdot F(7) / F(4) = 1000\cdot\frac{2^{5000-7}7!}{2^{5000-4}4!} = 1000\cdot 5\cdot 6\cdot 7/8 = 26250$