Обработка последовательностей чисел

Материал из Вики ИТ мехмата ЮФУ
Версия от 13:25, 19 октября 2013; Juliet (обсуждение | вклад) (Особенности «досрочного» завершения обработки)

Перейти к: навигация, поиск

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

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.

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

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

Дано целое число N (N ≥ 0), а также последовательность из N целых чисел. 
Найти номер первого элемента последовательности, кратного 5. Если таких элементов нет, вывести -1.
Например:
   N = 0 >>> -1
   N = 1; 4 >>> -1
   N = 1; 25 >>> 1
   N = 4; 3, 6, 7, 8 >>> -1
   N = 4; 3, 5, 2, 25 >>> 2

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

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

  Writeln('Input numbers of sequence: ');
  var resInd := -1;
  var a: integer;
  for var i := 1 to N do
  begin
    a := ReadInteger();
    if a mod 5 = 0 then
    begin
      resInd := i;
      break;
    end;
  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}', j, resInd);
  end;
end.

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