Обработка последовательностей чисел — различия между версиями

Версия 15:48, 19 октября 2013

Случай последовательности с заданным количеством элементов

begin
  // Предварительные действия
  // ...
  Read(N);
  for var i := 1 to N do
  begin
    // Ввод очередного элемента последовательности
    Read(a);
    // Обработка очередного элемента последовательности
    // ...
  end;
  // Вывод результатов обработки
  // ...
end.

Случай последовательности, заканчивающейся нулем

begin
  // Предварительные действия
  // ... 
  while True do // Бесконечный цикл
  begin
    // Ввод очередного элемента последовательности 
    var a := ReadInteger; // или ReadReal
    if a = 0 then
      break; // Выход из цикла при обнаружении последнего элемента

    // Обработка очередного элемента последовательности
    // ... 
  end;
  // Вывод результатов обработки
  // ... 
end.

Особенности «досрочного» завершения обработки

Рассмотрим задачу:

Дана последовательность ненулевых целых чисел, признак её завершения — число 0.
Найти номер первого элемента последовательности, кратного 5. Если таких элементов нет, вывести -1.
Например:
   0 >>> -1
    4, 0 >>> -1
   25, 0 >>> 1
   3, 6, 7,  8, 0 >>> -1
   3, 5, 2, 25, 0 >>> 2

Как решать такую задачу? Нас интересует только первое число, удовлетворяющее условию «кратно 5-ти», поэтому первый алгоритм, который приходит в голову, выглядит так:

begin
  Writeln('Input numbers of sequence: ');
  var resInd := -1;
  var i := 1;
  var a: integer;
  while true do
  begin
    a := ReadInteger();
    // конец набора
    if a = 0 then
      break;
    // ответ найден, досрочный выход
    if a mod 5 = 0 then
    begin
      resInd := i;
      break;
    end;
    i += 1;
  end;
  WritelnFormat('Result = {0}', resInd);
end.

Считываем числа последовательности, пока она не закончится, либо не найдется подходящий элемент. Если такой элемент нашелся — выходим из цикла.

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

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

Случай обработки нескольких наборов

Рассмотрим задачу:
Дано целое число K (> 0), а также K наборов ненулевых целых чисел. Признак окончания набора — число 0.
Для каждого набора найти и вывести номер первого элемента, кратного 5. Если таких элементов нет, вывести -1.

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

begin
  Write('Input K: ');
  var K := ReadInteger();
  Assert(K > 0);

  Writeln('Input sequences: ');
  for var j := 1 to K do
  begin
    var resInd := -1;
    var i := 1;
    var a: integer;
    while true do
    begin
      a := ReadInteger();
      // конец набора
      if a = 0 then
        break;
      // ответ найден, досрочный выход
      if a mod 5 = 0 then
      begin
        resInd := i;
        break;
      end;
      i += 1;
    end;
    WritelnFormat('Sequence {0}: {1,3}', j, resInd);
  end;
end.

Проверим решение на следующих входных данных:
Input K: 3
Input sequences:
8 4 5 -2 6 0 -4 -5 6 7 0 1 2 3 4 0

Мы ввели три набора, которые соответствуют условию задачи:

(1)  8  4 5 -2 6 0
(2) -4 -5 6 7  0
(3)  1  2 3  4 0

Ответ должен быть таким:

(1)  3
(2)  2
(3) -1

Но мы получим такой:

Sequence 1:   3
Sequence 2:  -1
Sequence 3:   2

В чем причина? «Виноват» наш досрочный выход. Как только мы нашли первый подходящий элемент в первой последовательности, чтение данных первого набора прекращается. Программа переходит на вторую итерацию внешнего цикла и снова ищет первый элемент, удовлетворяющий условию. При этом данные, которые считываются на этой итерации, могут все еще принадлежать первому набору. Поэтому с точки зрения программы «наборы» выглядят так:
8 4 5 -2 6 0 -4 -5 6 7 0 1 2 3 4 0
Числа, выделенные серым, вообще не считываются. Полученный ответ как раз соответствует выделенным «наборам». И это неправильный ответ.