Задание: Специальная камера, установленная на перекрёстке, фиксирует количество проезжающих автомобилей, и каждую минуту по каналу связи передаёт неотрицательное целое число — количество автомобилей, проехавших перекрёсток за эту минуту. Известно, что за минуту перекрёсток может проехать не более 100 автомобилей. Необходимо найти в заданной серии показаний максимальное количество автомобилей, проехавших перекрёсток в течение пяти подряд идущих минут. Максимальное количество показаний, которое может передать камера, не превышает 1440.
Напишите на любом языке программирования программу для решения поставленной задачи. Для получения максимального результата программа должна быть эффективна по времени и по используемой памяти.
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество переданных показаний. Гарантируется, что N>5. В каждой из следующих N строк задаётся одно положительное целое число – очередное показание камеры.
Пример входных данных:
8
5
12
27
10
4
50
7
16
Программа выводит только одно число – наибольшее количество автомобилей, проехавших перекресток за пять подряд идущих минут.
Пример выходных данных для приведённого выше примера входных данных:
103
Решение: Решение на 2 балла:
Первый вариант решения заключается в том, чтобы объявить массив с максимально возможным количеством элементов — 1440:
var a: array[1..1440] of byte;
Далее вводится значение N и считаются данные в массив:
for i:=1 to N do
readln(a[i]);
Теперь с помощью вложенных циклов (один цикл внутри другого) будем находить сумму пяти текущих элементов, и сравнивать её с максимальным значением. При этом каждый повтор первого цикла переменную S будем обнулять:
for i:=1 to N-4 do
begin
for j:=0 to 4 do
s := s+a[i+j];
if s > max then
max := s;
s := 0;
end;
Выводим значение переменной max:
writeln(max);
Полное решение:
var
a: array[1..1440] of byte;
i, j, N, max, s: integer;
begin
readln(N);
for i:=1 to N do
readln(a[i]);
max := 0; s := 0;
for i:=1 to N-4 do
begin
for j:=0 to 4 do
s := s+a[i+j];
if s > max then
max := s;
s := 0;
end;
writeln(max);
end.
Данная программа не является эффективной по памяти, так как хранит все введенные данные.
Решение на 4 балла:
Для решения задания мы можем не использовать такой огромный массив, достаточно хранить в памяти всего пять значений, сумму которых мы находим:
var a: array[1..5] of byte;
Сначала введем N и считаем в массив первые пять значений, при этом сразу можно найти и их сумму:
readln(n);
for i:=1 to 5 do
begin
readln(a[i]);
s := s+a[i];
end;
Сразу же присвоим переменной max значение s:
max := s;
Теперь введём оставшиеся значения. Для этого будем использовать последний (пятый) элемент массива, предварительно сдвинув все элементы на один влево:
for i:=6 to N do
begin
for j:=1 to 4 do //сдвиг массива
a[j] := a[j+1];
readln(a[5]);
Первое, что приходит в голову — просто посчитать сумму элементов с помощью вложенного цикла, но можно поступить лучше. Сумму элементов мы можем посчитать, вычтя из предыдущей суммы первый элемент до сдвига, и прибавив к ней введённый элемент после сдвига:
То есть теперь код будет выглядеть так:
for i:=6 to N do
begin
s := s — a[1];
for j:=1 to 4 do
a[j] := a[j+1];
readln(a[5]);
s := s + a[5]
Остаётся сравнить значение переменной s с max:
if s > max then
max :=s;
Полное решение:
var
a: array[1..5] of integer;
s, i, j, max, N: integer;
begin
readln(n);
s := 0;
for i:=1 to 5 do
begin
readln(a[i]);
s := s+a[i];
end;
max := s;
for i:=6 to N do
begin
s := s — a[1];
for j:=1 to 4 do
a[j] := a[j+1];
readln(a[5]);
s := s + a[5];
if s > max then
max :=s;
end;
writeln(max);
end.