Question

Вам необходимо подсчитать сумму S(n) = 1 - 2 + 3 - 4 + … + (-1)n+1 *n. Напишите программу, которая находит ответ за минимальное время и использует наименьший объем оперативной памяти. Входные данные: одно целое число n (1 ≤ n ≤ 109) Выходные данные: ответ S(n)

Answer 1

Если следовать алгоритму вычисления, представленному в формуле, то программа будет такая:

var
  n,i,s: shortint ;
begin
  write ('N=');
  readln (n);
  s:=0;
  for i:=1 to n do 
    if i mod 2 =0 
      then s:=s-i
      else s:=s+i;
  print (s)
end.

Если же посмотреть на формулу внимательно и выявить закономерность, то можно увидеть, что 

1) вычитаются только четные числа. И после каждого вычитания результат равен ровно половине вычитаемого числа (со знаком минус)
2) прибавляются только нечетные числа И прибавление идет вслед за вычитанием (кроме 1), т.е. можно к результату последнего вычитания (см.п.1) просто прибавить N.

Также учитываем, что целые числа занимают меньше памяти, чем вещественные, поэтому для программы используем самый маленький целый тип с отрицательными значениями shortint (от -128 до 127, что в данном случае нас вполне устраивает).

Помним, что значение переменной целого типа не может быть результатом деления, поэтому вместо обычного деления используем деление нацело (N div 2)

Итак:При нечетном N результат = -N div 2,
При четном N: (так как у нас целочисленное деление, то N div 2 будет равно (N-1) div 2) результат будет = -(N div 2) + N или N-(N div 2)
Т.е. вся программа сведена всего к двум операциям по разным веткам условного оператора, что сделает ее быстрее и экономичнее. К тому же не надо выделять память для переменной-счетчика.

var
  n,s: shortint;
begin
  write ('N=');
  readln (n);
  if n mod 2 =0
    then s:=-n div 2
    else s:=n-(n div 2);
  print (s)
end.

Можно увидеть и другую закономерность, что каждое сложение и идущее за ним вычитание дают одинаковый результат с разными знаками, т.е. при четном N также s=-N div 2, а при нечетном -  s=N div 2+1. Но большой разницы это не даст.