Задача № 44. Проверить, является ли последовательность пилообразной

Формулировка. Дана последовательность из трех и более натуральных чисел, ограниченная вводом нуля. Проверить, является ли эта последовательность пилообразной.

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

Пример такой последовательности: 14 12 18 7 10 2. Покажем, что данная последовательность соответствует определению: ее 1-й член (14) мы не рассматриваем, так как он имеет всего один соседний член; 2-й член (12) меньше соседних: 1-го (14) и 3-го (18); 3-й член (18) больше 12 и 7, 7 меньше 18 и 10, 10 больше 7 и 2, а последний элемент 2 мы также не рассматриваем. Эту запись можно формализовать, если между каждыми двумя соседними членами последовательности поставить знак отношения между их величинами («>» или «<»). В связи с этим приведенный выше пример можно проиллюстрировать так: 14 > 12 < 18 > 7 < 10 > 2. При этом характерно направление значков, показывающее, что каждый элемент либо меньше, либо больше соседних. При этом если мы выпишем сами знаки сравнения, то получим символьное сочетание > < > < >. А если выписать эти символы в столбик, становится понятно, почему такая последовательность названа пилообразной.

Решение. Исследуем свойства пилообразной последовательности. В определении сказано, что все ее элементы (кроме двух крайних) меньше либо больше соседних. Конкретизируем это понятие: любую тройку рядом стоящих элементов (левый элемент, центральный элемент, правый элемент) в данной последовательности мы будем называть «зубом».

Например, для указанного выше примера зубьями будут являться тройки 14 12 18, 12 18 7, 18 7 10 и 7 10 2. Каждый зуб удовлетворяет условию, данному в определении, следовательно, последовательность является пилообразной. Очевидно, что если все зубья в некоторой последовательности удовлетворяют данному условию, то эта последовательность является пилообразной.

Найдем некоторые свойства «правильных зубьев», то есть таких, которые отвечают заданному определению. Для этого формализуем рассуждения над элементами зуба, обозначив их как L (левый элемент, от англ. left – левый), M (средний элемент, от англ. medium – средний), R (правый элемент, от англ. right – правый).

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

I случай (средний элемент меньше крайних):

Здесь знак обозначает конъюнкцию (логическое «и»), а обозначает логическое следование (то есть, из выражения, которое стоит левее знака , следует выражение, стоящее правее знака ).

II случай (средний элемент больше крайних):

Итак, в обоих случаях мы составили две разности, которые для удобства обозначили (1) и (2). В I-ом случае (1) и (2) всегда строго больше 0, а во II-ом случае – строго меньше 0.

Составим произведение выражений (1) и (2) и обозначим его как (3): (M – L) * (M – R). В I-ом случае оно всегда положительно как произведение отрицательных чисел, во II-ом случае – также всегда положительно как произведение положительных чисел.

Что же следует из этого выражения? А то, что если результат его вычисления – положительное число, то тройка элементов L, M, R образует «правильный зуб». И как мы помним, если все тройки соседних элементов последовательности образуют «правильные зубья», то она является пилообразной.

Так как в условии задачи на вход подается как минимум три элемента, мы можем прочитать их в одном операторе:

read(L, M, R);

Затем мы входим в цикл с предусловием R < > 0. В этом цикле мы должны исследовать каждую тройку L, M, R по свойству (3):

while R <> 0 do begin

if (L - M) * (R - M) <= 0 then break;

L:= M;

M:= R;

read(R)

end;

На каждом шаге цикла мы сначала исследуем уже имеющуюся тройку (оператор 1 в теле цикла), и если выражение (3) оказывается равно или меньше нуля, то выходим из цикла, так как нашли «неправильный зуб», который нарушает условие пилообразной последовательности, в силу чего дальнейшая проверка бессмысленна. Затем нам нужно «сдвинуть» последовательность: например, если в переменных L, M, R у нас соответственно хранились 4-й, 5-й и 6-й элементы последовательности, которые мы уже проверили, то с помощью оператора L:= M мы переносим 5-й элемент в L, а с помощью M:= R переносим 6-й элемент в M. Далее мы вводим 7-й элемент в R, после чего в тройке L, M, R у нас содержатся соответственно 5-й, 6-й и 7-й элементы, проверка которых на соответствие условию будет произведена на следующем шаге цикла.

На последнем шаге цикла последовательность будет в очередной раз «сдвинута» и в R будет введено число 0, после чего должен быть выведен результат. В связи с этим возможно два варианта попадания на этот этап:

a) в цикле был осуществлен выход через break. А это значит, что в переменных L, M, и R в данном случае как раз находится «неправильный зуб» и можно обойтись выводом значения выражения (L – M) * (R – M) > 0, которое как раз даст значение false:

writeln((L - M) * (R - M) > 0);

b) последовательность была проверена до конца, и выход из цикла был осуществлен по вводу в R нуля. Но здесь нужно учесть, что при этом в тройке L, M, R теперь находится «несуществующий зуб» (так как 0 не входит в саму последовательность и не должен учитываться при проверке), который может и не быть «правильным».

Самый простой выход в этом случае – если переменная R равна 0, то заменить R на L. Это приведет к тому, что в выводимом на экран выражении (3) мы перемножаем не (1) и (2), а (1) и (1), что повлечет вывод true, так как мы получаем произведение одинаковых ненулевых чисел, которое всегда положительно. Значит, перед выводом выражения на экран необходима следующая вставка:

if R = 0 then R:= L;

Код:

К слову, данная задача может быть обобщена и на случай, когда длина вводимой последовательности не имеет ограничений снизу, то есть, последовательность может также быть пустой или содержать один член (для двух членов она будет работать корректно – это легко проверить). Для этого можно выполнить контроль ввода в зависимости от значений первых двух вводимых элементов и провести инициализацию значений для вывода необходимого для вырожденных случаев ответа.