Вам необходимо подсчитать сумму S(n) = 1 - 2 + 3 - 4 + … + (-1)n+1 *n. Напишите программу, которая находит ответ за минимальное время и использует наименьший объем оперативной памяти. Входные данные: одно целое число n (1 ≤ n ...
Вам необходимо подсчитать сумму S(n) = 1 - 2 + 3 - 4 + … + (-1)n+1 *n. Напишите программу, которая находит ответ за минимальное время и использует наименьший объем оперативной памяти.
Входные данные: одно целое число n (1 ≤ n ≤ 109)
Выходные данные: ответ S(n)
Ответ(ы) на вопрос:
Гость
Если следовать алгоритму вычисления, представленному в формуле, то программа будет такая:
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. Но большой разницы это не даст.
Не нашли ответ?
Похожие вопросы