Задача "Сумма нечетных чисел"

[назад]

Вычислить сумму всех нечетных чисел из интервала [a, b]. Например, сумма нечетных чисел из интервала [2, 9] равна 3 + 5 + 7 + 9 = 24.

Вход. Два целых числа a и b (0 £ a £ b £ 300).

Выход. Сумма всех нечетных чисел из интервала [a, b].

Пример входа

2 9

Пример выхода

24

Решение. Элементарные вычисления. 

По условию на числа a и b наложены ограничения, при которых искомая сумма будет лежать в пределах типа integer. При a = 0 и b = 300 сумма будет наибольшей и равной 22500, что меньше 32767 (максимального значения типа integer). Можно воспользоваться циклической программой:

program summa;

var

  a,b,i,sum: integer;

begin

  sum:=0;

  readln(a,b);

  for i:=a to b do

    if i mod 2 <> 0 then sum:= sum + i;

  writeln(sum);

end.

Приведенная программа циклическая, но можно результат вычислить и математически.

Пересчитаем значения a и b так, чтобы a равнялось наименьшему нечетному числу из интервала [a, b], а b – наибольшему. То есть если a четно, то увеличим его на 1. Если b четно, то уменьшим его на 1. Если a или b было четным, то исходный интервал [a, b] изменится, но при этом сумма его нечетных чисел останется такой же как и сумма нечетных чисел исходного интервала.

Если a > b, то искомая сумма рана 0. Хоть по условию задачи имеет место неравенство a £ b, но после выше приведенного преобразования интервала [a, b] может получиться a > b. Такая ситуация может, например, возникнуть на интервале [4; 4] (a = b = 4). После преобразования получим a = 5, b = 3.

Сумму всех нечетных чисел из интервала [a, b] считаем по формуле суммы арифметической прогрессии. Поскольку значения a и b нечетные (после преобразования исходного интервала), то количество нечетных чисел в интервале [a, b] равно (b - a) / 2 + 1, а сумма всех нечетных чисел равна

Не забываем, что целочисленное деление в Паскале совершается оператором div. Программа подсчета при помощи приведенной формулы имеет вид:

program summa;

var

  a,b,i,res:integer;

begin

  readln(a,b);

  if (a mod 2 = 0) then Inc(a);

  if (b mod 2 = 0) then Dec(b);

  if (b < a) then res := 0

  else res := (a + b) * ((b - a) div 2 + 1) div 2;

  writeln(res);

end.

Приведенная программа синтаксически верна, но попробуйте запустить ее на критических значениях a и b, то есть при a = 0 и b = 300. Ответом будет значение -10268. Что же произошло?

Вычисления в Паскале происходят слева направо, то есть при выполнении операции

res := (a + b) * ((b - a) div 2 + 1) div 2;

сначала произойдет умножение в скобках (a + b) * ((b - a) div 2 + 1), а потом результат разделится нацело на 2. А результат в скобках при малых a и больших b превосходит значение 32767, происходит переполнение!

Для решения проблемы сначала надо один из сомножителей разделить на 2, а потом результат умножить на второй множитель. Переполнения не будет. Это все равно что выражение x * y / c вычислять как x / c * y. Математически выражения дают один результат. Но при вычислении на языке программирования первое выражение может давать переполнение, а второе нет. При этом во втором выражении множитель x должен обязательно нацело делиться на c.

Поскольку числа a и b после преобразования интервала нечетные, то их сумма делится на 2, и выражение можно переписать в виде

res := (a + b) div 2 * ((b - a) div 2 + 1);

Оптимальная и правильная программа примет вид:

program summa;

var

  a,b,i,res:integer;

begin

  readln(a,b);

  if (a mod 2 = 0) then Inc(a);

  if (b mod 2 = 0) then Dec(b);

  if (b < a) then res := 0

  else res := (a + b) div 2 * ((b - a) div 2 + 1);

  writeln(res);

end.

 [назад]