Участник:Тихмонатор Тестбот/Полигон3

Материал из Anekdot.me
Перейти к: навигация, поиск

Предисловие. Пусть нам надо посчитать . Можно, кончено, считать в лоб, высчитывая по очереди все факториалы и складывая их. Однако зачем заставлять компьютер перемножать, допустим, первые 50 чисел (высчитывая ), если до этого мы считали , и нам нужно всего лишь домножить это дело на 50? Поэтому логичнее куда-то запоминать значения посчитанного факториала , чтобы потом умножить его на . В результате мы получим цикл вида for(int i=1; i<=n; i++){a=a*i; s=s+a;} Здесь  — высчитываемая сумма,  — «хранилище» наших факториалов.

Ту же идею попытаемся использовать, высчитывая выражение . Только если в примере выше нам удалось обойтись одним «хранилищем» (там, где мы запоминали факториалы), то здесь их понадобится несколько.

Распишем произведение : . В примере с факториалами нам надо было посчитать сумму штучек вида , а здесь — произведение штучек вида . Идея та же, только сложнее. И, как в примере мы вычисляли факториал числа через , так и здесь попробуем выразить через .

Для этого распишем сумму: . Обозначим это выражение за .

Теперь распишем то, что мы хотим получить, то есть сумму . Если внимательно посмотреть, то первые слагаемых у этих двух сумм практически одинаковы, отличается лишь степень при : в она на единичку больше. Кроме того, в имеется лишнее слагаемое . Получается, что . Обозначим за .

Вот тут появляется отличие от примера с факториалами. Там мы обходились одним «хранилищем» посчитанных ранее значений, с помощью содержимого которого получали новое слагаемое. Алгоритм был таков: взять число из «хранилища», слегка его изменить (домножить на  — получить актуальный факториал), прибавить результат к сумме. В этом же примере таких хранилищ необходимо два — в одном будет храниться число , в другом — . Удлиняется и алгоритм: мы возьмём число , изменим его, чтобы получить , затем возьмём , с помощью посчитанного уже превратим в , и затем умножим произведение, которое мы высчитываем, на . Каким образом превращать в , мы уже знаем: . Осталось выяснить, как превращать в .

Имеем:

. Но можно заметить, что первый множитель является , поэтому .

Вот мы и установили, как выражается через . Теперь мы можем задать значения и , после чего по имеющимся формулам и найти и  — так мы найдём первый множитель. По тем же самым формулам, но уже используя и , мы находим и  — второй множитель. Действуя так далее до , мы находим все множители, входящие в состав произведения, которое нам необходимо посчитать.

Ну а цикл вообще должен иметь следующий вид:

for (int i=1;i<=n;i++)
{
s=s*x*(n-i+1)/(i*i);
r=r*x+s;
p=p*r;
}