Как посчитать сумму чисел на промежутке от a до b, без цикла?

Question

[alphasigma]

Столкнулся с этой задачей еще давно и так и не дает покоя. Понятно, что циклом решить это затратно по времени, но я нашел и другой выход – арифметическая прогрессия, но тут начало не с 1, а с произвольного элемента, так что тут стандартной формулой не получится.

Конкретизирую вопрос:
Как математически посчитать сумму например от 47 до 72, т.е. 47 + 48+ 49 … + 72 ?

Comments

[alphasigma]

sum = (1+b)*b/2;
sum2 = (1+a)*a/2;
result =sum - sum2;

Почти правильно... У меня тоже было такое решение, но при малых a, формула делает ошибку и при стандартных 1 до 100 выдает 1049(должен 1050), при 2 до 5 выдает 12(должно 14).
Если к результату прибавлять a то уже при 5 до 10 будет неверный ответ 60 (должно быть 55).
Можно условия навешать, но может есть более элегантная формула?

[tsarevfs]

Вы по вашей формуле сумма не включает a. Отсюда и ошибка на 1.

[Владлен Грачев]

Во-первых, есть комментарии к ответу. Во-вторых, ничего не путаете?
Нужно вместо a использовать (a-1):
от 1 до 100: (1+100)*100/2 - (1+0)*0/2 = 5050
от 2 до 5: (1+5)*5/2 - (1+2)*2/2 = 12
от 5 до 10: (1+10)*10/2 - (1+4)*4/2 = 45 (Откуда у вас 55 и 60 - непонятно)

[tsarevfs]

a + (a + 1) + ... + b = (b - a + 1) * (b + a) / 2
я вспоминаю эту формулу так:
a + (a + 1) + ... + (b - 1) + b =
= a + 0 + a + 1 + a + 2 + ... + a + (b - a) =
= a * (b - a + 1) + (0 + 1 + 2 + .. + (b - a)) =
= a * (b - a + 1) + (b - a) * (b - a + 1) / 2 =
= (b + a) * (b - a + 1) / 2

Answer 1

[ManWithBear]

Стандартной формулой тут получится.
S = (a1+an)*n/2, где a1 - первый член, an - последний, n - количество членов последовательности
Имеем (47+72)*26/2 = 1547

Итого ваша формула: S = (a+b)(b-a+1)/2

Comments

[Izhak]

Я бы немного расширил ответ. Требуется вычислить сумму от a до b с шагом d
Эту сумму можно представить как n*a+0+1+...+(n-1)=n*a+(n-1)*(n-1+1)/2=n*a+n*(n-1)/2=n*(a+(n-1)/2) учитывая, что n=b-a+1, получаем (b-a+1)*(a+(b-a+1-1)/2)=(b-a+1)*(2a+b-a)/2=(b-a+1)*(a+b)/2

[alphasigma]

@Izhak вы шаг d забыли вставить в формулу, но мысль интересная!

[Izhak]

:) ru.wikipedia.org/wiki/%C0%F0%E8%F4%EC%E5%F2%E8%F7%...

[ManWithBear]

@Izhak если нужно более подробно, то как вы правильно дали ссылку, всё описанно в вики с доказательствами, а переписывать сюда википедию по-моему бессмысленно :)

[garro]

S = (a + b) * (b - a + 1) / 2
Мне кажется это не будет работать при a > b.
Наверно нужно принимать модуль выражения, типа ( |b - a| + 1).
Что думаете?

Answer 2

[Андрей]

result = ((b+1)*b-(a-1)*a) div 2;
a=1 b=100 result=5050 (именно столько и должно быть, а не 1050)
a=2 b=5 result=14 (2+3+4+5=14)
a=5 b=10 result=45 (5+6+7+8+9+10=45)

Comments

[Саша Слипкер]

дааа вот оно) на яве с лонгом

Answer 3

[Владлен Грачев]

Как математически посчитать сумму например от 47 до 72, т.е. 47 + 48+ 49 … + 72 ?

Высчитать сумму первых 72 членов арифметической прогрессии и вычесть из нее сумму первых 46 членов арифметической прогрессии.