§3. Класс задач «Обработка последовательностей»

В данном классе формулировка всех задач начинается со слов: «Вводится последовательность чего-нибудь…». Для простоты будем считать, что чисел - с ними мы умеем работать, но в общем случае это необязательно так. Далее нам нужно оценить какое-то свойство данной последовательности. Например, сколько в ней нулей, является ли она возрастающей (каждое следующее число больше предыдущего) и т. д. Причём, для оценки данного свойства, сохранение всей последовательности в памяти не требуется.

Общий алгоритм решения задач этого класса таков: мы считываем очередной элемент последовательности, обрабатываем его так, как поставлено в задаче, и после про него забываем. Для реализации данного алгоритма нам придётся поместить оператор ввода внутрь цикла.

Рассмотрим стандартные шаблоны решения задач данного класса:

шаблон Тип 1:

 Количество элементов в последовательности известно заранее (`N`).

        readln(N);

     for j:=1 to N do begin

       read(a);

      {Содержательна обработка}

     end;

Обращаем внимание, что внутрь оператора цикла обязательно помещается оператор read, а не readln. Дело в том, что, как правило, числа будут вводиться в строчку и оператор ввода будет на каждом шаге забирать из буфера по `1` числу. Оператор  readln при этом ещё удаляет из буфера всё лишнее до конца строки, поэтому числа прочитаны не будут. Количество элементов последовательности, как правило, задаётся отдельным числом в первой строке, поэтому его логичнее читать оператором readln.

Рассмотрим примеры задач данного класса.

Задача 1

Вводится натуральное число `N`, а затем `N` натуральных чисел, сумму которых необходимо вычислить.

Решение

var i,N,a,s:integer;

begin

  readln(N);

       s:=0;

  for i:=1 to N do begin

         read(a);

    s:=s+a;

       end;

  writeln(s)

end.

Задача 2

Вводится натуральное число `N`, а затем `N` целых чисел. Выведите `"YES"`, если среди введенных чисел есть хотя бы один ноль, или `"NO"` в противном случае.

Решение

var n,i,k,a,s:integer;

begin

  s:=0;

  readln(n);

  for i:=1 to n do begin

    read(a);

    if a=0 then k:=k+1;

  end;

if k<>0

  then writeln('YES')

  else writeln('NO')

end.

Теперь рассмотрим второй тип задач из класса «Обработка последовательностей», когда количество элементов неизвестно заранее, но известен признак конца.

Признак конца - это служебный элемент, который в саму последовательность не входит. При обработке числовых последовательностей чаще всего признаком конца является ноль (но может быть и любое другое число). Наиболее распространённая ошибка - обработать признак конца как содержательный элемент (например, при расчёте среднего арифметического элементов последовательности). Поэтому порядок действий должен быть таким:

1) Считывание

2) Проверка на признак конца

3) Содержательная обработка

За 3 пунктом алгоритм замыкается в цикл. Выход из цикла - на втором пункте, в случае положительного ответа. Соответственно, шаблон алгоритма должен отражать данную логику действий.

Шаблон для типа 2:

  read(a);

     while a<>0 do begin

       {содержательная обработка};

       read(a)

     end;         

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

Задача 3

Программа получает на вход последовательность целых неотрицательных чисел. Ноль - признак конца. Вывести количество членов последовательности (не считая завершающего числа `0`).

Решение

var a,k:integer;

begin

  read(a);

  k:=0;

  while a<>0 do begin

    k:=k+1;

    read(a);

  end;

  writeln(k);

end.

Задача 4

Вводится последовательность целых чисел. Ноль - признак конца. Вывести, сколько элементов данной последовательности больше (строго) предыдущего элемента.

Решение

При решении этой задачи нам нужно будет сохранять в отдельную переменную значение предыдущего числа перед вводом нового. Приведём код программы.

var a,pr,k:integer;

begin

  read(a);

  pr:=a;

  k:=0;

  while a<>0 do begin

    if (a > pr) then k:=k+1;

    pr:=a;

    read(a);

  end;

  writeln(k);

end.

Задача 5

Вводится последовательность натуральных чисел. Ноль - признак конца. Вывести значение максимального элемента.

Решение

Это очень важная эталонная задача, которую обязательно надо уметь решать. Для поиска максимума применяется следующая стратегия. Нужно каждый элемент сравнить с текущим значением максимума и, если элемент оказался больше, то обновить текущее значение максимума. Рассмотрим код программы.  

var a,m:integer;

begin

  read(a);

  m:=a;

  while a<>0 do begin

    if (a > m) then m:=a;

    read(a);

  end;

  writeln(m);

end.

При решении этой задачи ещё остался вопрос корректной инициализации. В общем случае есть два способа.

Первый вариант - в качестве начального значения максимума брать «минус бесконечность» (для минимума - плюс бесконечность). Под «минус бесконечностью» в данном случае понимается некое число, которое гарантированно меньше чем любой элемент, который может нам встретиться. Инициализация бесконечностью допустима, если мы заранее знаем диапазон элементов последовательности. Это её недостаток, зато она пишется в один оператор присваивания.

Второй вариант - в качестве начального значения брать первый подходящий элемент последовательности. В случае глобального максимума берётся просто первый элемент последовательности. Сложнее в ситуации, когда первый элемент может оказаться неподходящим.

Задача 6

Найти максимальный чётный элемент последовательности в предположении, что он существует.

Решение

var a,m:integer;

begin

  read(a);

  while (a<>0)and(a mod 2 <> 0) do read(a);

  m:=a;

  while a<>0 do begin

    if (a mod 2 = 0)and(a>m) then m:=a;

    read(a);

  end;

  writeln(m);

end.