Обработка последовательностей чисел
Содержание
Случай последовательности с заданным количеством элементов
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
Числа, выделенные серым, вообще не считываются. Полученный ответ как раз соответствует выделенным «наборам». Но это неправильный ответ.
Входные данные введены верно — в соответствии с условием задачи. Но наш алгоритм обрабатывает их некорректно, потому что мы считываем не все числа из набора. Исправим:
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()
в конец итерации. Таким образом, даже если обработка текущего набора досрочно прекратилась, оставшиеся данные в потоке ввода будут пропущены. В начале следующей итерации пользователю придется снова задавать числа набора.
Тогда лог работы может быть таким:
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
Обратите внимание, что первый раз пользователь ввел числа всех наборов, но они были пропущены. Вводить данные придется в начале каждой итерации.