11.3 Алгоритмы накопления суммы и произведения

Применяются, когда требуется сложить или перемножить выбранные данные. В общем виде эти широко применяемые алгоритмы можно описать так:

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

2. до цикла переменной-сумме присвоить начальное значение 0, а произведению – значение 1;

3. в теле цикла, если очередной элемент данных t отвечает условию суммирования или перемножения, сумма накапливается оператором вида s:=s+t;, а произведение – оператором вида p:=p*t;

Очевидно, почему начальное значение произведения – единица, а не ноль. После оператора p:=0; оператор p:=p*t;, расположенный в теле цикла, будет возвращать только нули.

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

Для поиска арифметического среднего необходимо сначала найти сумму s и количество k положительных значений функции. Составим следующую программу:

var x,f,s,p:real;

k:integer;

begin

s:=0;

k:=0;

p:=1;

x:=-5;

while x<=5+1e-6 do begin

if x<0 then f:=sqr(ln(abs(x)))

else if x>0 then f:=sin(sqr(x))

else f:=0;

if f>0 then begin

s:=s+f;

k:=k+1;

end;

if f<>0 then p:=p*f;

x:=x+0.5;

end;

s:=s/k; {теперь в s - искомое среднее}

writeln ('Среднее положительных =',s:10:6);

writeln ('Произведение ненулевых=',p:10:6);

reset (input); readln;

end.

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

скидки нет, если общая стоимость < 10000 руб.;

скидка = 5%, если общая стоимость - от 10000 до 20000 руб.;

скидка = 7%, если общая стоимость - свыше 20000 руб.

После начисления скидки выводится окончательная стоимость покупки.

Обозначив общую стоимость покупки s, а цену очередного товара – t, напишем следующую программу:

var s,t:real;

begin

writeln;

s:=0; {начальное значение суммы!}

repeat

writeln ('Введите стоимость товара или 0 для завершения ввода:');

{$I-}read(t);{$I+}

if (IoResult<>0) or (t<0) then begin

writeln ('Ошибка! Повторите ввод');

continue;

end;

if t=0 then break;

{Округляем t до 2 знаков после запятой - на случай, если есть копейки}

t:=Round (t*100) / 100;

s:=s+t; {накопление суммы!}

until false;

{Начисление скидки и вывод ответа}

writeln ('Стоимость без скидки:',s:8:2);

if s>20000 then s:=s-s*0.07

else if s>10000 then s:=s-s*0.05;

writeln ('Стоимость со скидкой:',s:8:2);

writeln ('Спасибо за покупку!');

reset (input); readln;

end.

Тип данных real выбран для s и t не случайно – выбор integer ограничил бы диапазон обрабатываемых значений и не позволил в удобном виде ввести копейки. Проверки корректности ввода, делаемые программой, знакомы по предыдущим примерам и поэтому не закомментированы.

12. Типовые алгоритмы поиска максимума и минимума

В этой главе мы изучим простейшие статистические алгоритмы, главный из которых – определение максимального и минимального значения на множестве данных.

Рассмотрим алгоритм в общем виде:

1. описать для каждого максимума и минимума по одной переменной того же типа, что анализируемые данные;

2. до цикла максимуму присваивается либо заведомо малое для анализируемых данных значение, либо первый элемент данных; минимуму присваивается либо заведомо большое для анализируемых данных значение, либо первый элемент данных;

3. в теле цикла каждый подходящий для поиска элемент данных t обрабатывается операторами вида: if t>max then max:=t; - для максимума; if t<min then min:=t; - для минимума, где max и min – переменные для максимума и минимума соответственно.

Шаг 2 этого алгоритма требует комментариев, которые мы сделаем на примере поиска максимума. Очевидно, что сам алгоритм несложен – каждый элемент данных t последовательно сравнивается с ячейкой памяти max и, если обнаружено значение t, большее текущего значения max, оно заносится в max оператором max:=t;. Как мы помним, после описания на шаге 1 переменной max, ее значение еще не определено, и может оказаться любым – откуда следует необходимость задания начального значения. Представим, что после выбора начального значения max, равного нулю, при анализе встретились только отрицательные значения элементов t. В этом случае условие t>max не выполнится ни разу и ответом будет max, равное нулю, что неправильно! Выбор заведомо малого начального значения max (например, значение -1E30, т.е. -10³⁰, вряд ли встретится в любых реальных данных) гарантирует, что условие t>max выполнится хотя бы раз и максимум будет найден. Альтернативный способ – присвоить max значение отдельно вычисленного первого элемента последовательности данных. В этом случае ответ либо уже найден, если первый элемент и есть максимальный, либо будет найден в цикле.

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

Перейдем к примерам.

Пр. Для функции y(x)=sin²(x), найти минимальное среди положительных и максимальное значения.

Обозначив искомые значения min и max соответственно, составим следующую программу:

var x,y,max,min:real;

begin

x:=-pi/3;

max:=-2;

min:=2; {эти начальные значения - заведомо малое и большое для синуса}

while x<=pi/3+1e-6 do begin

y:=sqr(sin(x));

if y>0 then {ищем min только среди положительных!}

if y<min then min:=y;

if y>max then max:=y;

x:=x+pi/24;

end;

writeln ('Минимум =',min:8:2);

writeln ('Максимум=',max:8:2);

reset (input); readln;

end.

В следующем примере дополнительно сохраним значения аргументов функции, для которых найдены минимум и максимум.

Пр. Последовательность T(k) задана соотношениями T(k)=max(sin k, cos k), k=1,2,…,31. Найти номера максимального и минимального элементов последовательности.

Поиск номеров не избавит нас от необходимости поиска значений. Поэтому, кроме переменных min и max, нам понадобятся две целочисленные переменные для хранения номеров минимального и максимального значений, обозначим их kmin и kmax соответственно. Обратите также внимание, что на каждом шаге цикла дополнительно потребуется находить максимальное из значений sin(k) и cos(k), для занесения его в t.

var t,max,min:real;

k,kmin,kmax:integer;

begin

min:=1e30; {не определяя заведомо большого и малого для этих данных значений,}

max:=-1e30;{задаем "надежные" значения, близкие к плюс и минус бесконечности}

for k:=1 to 31 do begin

if sin(k)>cos(k) then t:=sin(k)

else t:=cos(k);

if t<min then begin

{по условию нужны 2 оператора - сохранение нового мин. значения}

{и сохранение номера элемента, отсюда операторные скобки!}

min:=t; kmin:=k;

end;

if t>max then begin

max:=t; kmax:=k;

end;

end;

writeln ('Номер мин. элемента =',kmin);

writeln ('Номер макс. элемента=',kmax);

reset (input); readln;

end.