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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Новая страница: «Случай последовательности с заданным количеством элементов <source lang="Pascal">begin // Предварите…»)
 
(Случай последовательности с заданным количеством элементов)
 
(не показано 10 промежуточных версий 2 участников)
Строка 1: Строка 1:
Случай последовательности с заданным количеством элементов
+
====Случай последовательности с заданным количеством элементов====
 
<source lang="Pascal">begin
 
<source lang="Pascal">begin
 
   // Предварительные действия
 
   // Предварительные действия
 
   // ...
 
   // ...
   Read(N);
+
   N := ReadInteger;        // или Read(N);
 
   for var i := 1 to N do
 
   for var i := 1 to N do
 
   begin
 
   begin
 
     // Ввод очередного элемента последовательности
 
     // Ввод очередного элемента последовательности
     Read(a);
+
     var a := ReadInteger;  //или ReadReal, или Read(a);
 
     // Обработка очередного элемента последовательности
 
     // Обработка очередного элемента последовательности
 
     // ...
 
     // ...
Строка 15: Строка 15:
 
end.</source>
 
end.</source>
  
Случай последовательности, заканчивающейся нулем
+
====Случай последовательности, заканчивающейся нулем====
 
<source lang="Pascal">begin
 
<source lang="Pascal">begin
 
   // Предварительные действия
 
   // Предварительные действия
Строка 22: Строка 22:
 
   begin
 
   begin
 
     // Ввод очередного элемента последовательности  
 
     // Ввод очередного элемента последовательности  
     Read(a);
+
     var a := ReadInteger; // или ReadReal
 
     if a = 0 then
 
     if a = 0 then
 
       break; // Выход из цикла при обнаружении последнего элемента
 
       break; // Выход из цикла при обнаружении последнего элемента
 +
 
     // Обработка очередного элемента последовательности
 
     // Обработка очередного элемента последовательности
 
     // ...  
 
     // ...  
Строка 31: Строка 32:
 
   // ...  
 
   // ...  
 
end.</source>
 
end.</source>
 +
 +
== Особенности «досрочного» завершения обработки ==
 +
Рассмотрим задачу:
 +
Дана последовательность ненулевых целых чисел, признак её завершения — число 0.
 +
Найти номер первого элемента последовательности, кратного 5. Если таких элементов нет, вывести -1.
 +
Например:
 +
    0 >>> -1
 +
    4, 0 >>> -1
 +
    25, 0 >>> 1
 +
    3, 6, 7,  8, 0 >>> -1
 +
    3, 5, 2, 25, 0 >>> 2
 +
 +
Как решать такую задачу? Нас интересует только первое число, удовлетворяющее условию «кратно 5-ти», поэтому первый алгоритм, который приходит в голову, выглядит так:
 +
<source lang="Pascal">
 +
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.
 +
</source>
 +
Считываем числа последовательности, пока она не закончится, либо не найдется подходящий элемент. Если такой элемент нашелся — выходим из цикла.
 +
 +
Действительно, зачем выполнять «лишние» итерации и обрабатывать числа, если ответ на задачу уже известен? Однако, следует обратить внимание на одну особенность этой задачи: ''каждый элемент набора программа получает извне''. Интерфейс взаимодействия программы и источника данных ''может быть'' таким, что ''досрочное прекращение чтения приведет к ошибке''.
 +
 +
В нашем случае программа получает данные из консоли — от пользователя, поэтому особых проблем пока не видно.
 +
 +
==== Случай обработки нескольких наборов ====
 +
Рассмотрим задачу: <br />
 +
<code>Дано целое число K (> 0), а также K наборов ненулевых целых чисел. Признак окончания набора — число 0. <br />
 +
Для каждого набора найти и вывести номер первого элемента, кратного 5. Если таких элементов нет, вывести -1.</code>
 +
 +
Как и в предыдущей задаче, для каждого набора нужно найти первый элемент, удовлетворяющий условию. Используем в решении тот же подход:
 +
<source lang="Pascal">
 +
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.
 +
</source>
 +
 +
Проверим решение на следующих входных данных: <br />
 +
<code>Input K: '''3'''  <br />
 +
Input sequences: <br />
 +
'''8 4 5 -2 6 0 -4 -5 6 7 0 1 2 3 4 0'''</code>
 +
 +
Мы ввели три набора, которые соответствуют ''условию задачи'':
 +
(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
 +
 +
В чем причина? «Виноват» наш досрочный выход. Как только мы нашли первый подходящий элемент в первой последовательности, ''чтение данных первого набора прекращается''. Программа переходит на вторую итерацию внешнего цикла и снова ищет первый элемент, удовлетворяющий условию. При этом данные, которые считываются на этой итерации, могут все еще принадлежать первому набору. Поэтому с точки зрения программы «наборы» выглядят так: <br />
 +
<tt><font color="blue">8 4 5</font><font color="green"> -2 6 0</font><font color="navy"> -4 -5</font><font color="grey"> 6 7 0 1 2 3 4 0</font></tt> <br />
 +
Числа, выделенные серым, вообще не считываются. Полученный ответ как раз соответствует выделенным «наборам». Но это '''неправильный''' ответ.
 +
 +
Входные данные введены верно — в соответствии с условием задачи. Но наш алгоритм обрабатывает их некорректно, потому что мы считываем не все числа из набора. Исправим:
 +
<source lang="Pascal">
 +
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 notFound := true;
 +
    var a: integer;
 +
    while true do
 +
    begin
 +
      a := ReadInteger();
 +
      // конец набора
 +
      if a = 0 then
 +
        break;
 +
      // ответ найден, досрочный выход
 +
      if notFound and (a mod 5 = 0) then
 +
      begin
 +
        resInd := i;
 +
        notFound := false;
 +
      end;
 +
      i += 1;
 +
    end;
 +
    WritelnFormat('Sequence {0}: {1,3}', j, resInd);
 +
  end;
 +
end.
 +
</source>
 +
Мы добавили логическую переменную <code>notFound</code>, которая показывает, найден ли уже ответ на вопрос задачи. Можно обойтись без неё, используя в качестве условия выражение <code>resInd = -1</code>.
 +
 +
Если же вы очень хотите использовать <code>break</code> и не считывать все числа, необходимо ''обеспечить правильный ввод каждого набора''. То есть при переходе к следующей итерации на вход должен поступать следующий набор. Мы можем заставить пользователя вводить новый набор на каждой следующей итерации, если добавим <code>readln()</code> в конец итерации. Таким образом, даже если обработка текущего набора досрочно прекратилась, оставшиеся данные в потоке ввода будут пропущены. В начале следующей итерации пользователю придется снова задавать числа набора.
 +
 +
<source lang="Pascal">
 +
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;
 +
    readln();
 +
    WritelnFormat('Sequence {0}: {1,3}', j, resInd);
 +
  end;
 +
end.
 +
</source>
 +
 +
Тогда лог работы может быть таким:<br />
 +
<code>Input K: '''3''' <br />
 +
Input sequences:<br />
 +
'''8 4 5 -2 6 0 -4 -5 6 7 0 1 2 3 4 0'''<br />
 +
Sequence 1:  3<br />
 +
'''-4 -5 6 7 0'''<br />
 +
Sequence 2:  2<br />
 +
'''1 2 3 4 0'''<br />
 +
Sequence 3:  -1</code>
 +
 +
Обратите внимание, что первый раз пользователь ввел числа всех наборов, но они были пропущены. Вводить данные придется в начале каждой итерации.
  
 
[[Категория:Основы программирования]]
 
[[Категория:Основы программирования]]

Текущая версия на 16:32, 13 октября 2014

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

begin
  // Предварительные действия
  // ...
  N := ReadInteger;        // или Read(N);
  for var i := 1 to N do
  begin
    // Ввод очередного элемента последовательности
    var a := ReadInteger;  //или ReadReal, или 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
Числа, выделенные серым, вообще не считываются. Полученный ответ как раз соответствует выделенным «наборам». Но это неправильный ответ.

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

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 notFound := true;
    var a: integer;
    while true do
    begin
      a := ReadInteger();
      // конец набора
      if a = 0 then
        break;
      // ответ найден, досрочный выход
      if notFound and (a mod 5 = 0) then
      begin
        resInd := i;
        notFound := false;
      end;
      i += 1;
    end;
    WritelnFormat('Sequence {0}: {1,3}', j, resInd);
  end;
end.

Мы добавили логическую переменную notFound, которая показывает, найден ли уже ответ на вопрос задачи. Можно обойтись без неё, используя в качестве условия выражение resInd = -1.

Если же вы очень хотите использовать break и не считывать все числа, необходимо обеспечить правильный ввод каждого набора. То есть при переходе к следующей итерации на вход должен поступать следующий набор. Мы можем заставить пользователя вводить новый набор на каждой следующей итерации, если добавим readln() в конец итерации. Таким образом, даже если обработка текущего набора досрочно прекратилась, оставшиеся данные в потоке ввода будут пропущены. В начале следующей итерации пользователю придется снова задавать числа набора.

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;
    readln();
    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
Sequence 1: 3
-4 -5 6 7 0
Sequence 2: 2
1 2 3 4 0
Sequence 3: -1

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