Задание 1. Тип заданий 27: разработка программы.
  • Задание:

    Специальная камера, установленная на перекрёстке, фиксирует количество проезжающих автомобилей, и каждую минуту по каналу связи передаёт неотрицательное целое число — количество автомобилей, проехавших перекрёсток за эту минуту. Известно, что за минуту перекрёсток может проехать не более 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.

Поделиться:
 
Комментарии (0)

Нет комментариев. Ваш будет первым!

Перевести число из в Результат: 510 = 1012