Однородная группа (или серия) – это непрерывная последовательность элементов массива, обладающая одним и тем же заданным свойством. Например, серия положительных элементов, серия нечетных элементов и т.п.
Однородные группы можно разделить на два типа:
- группы, для которых можно четко указать признаки начала и конца группы;
- группы, для которых суждение о выполнении заданного свойства может быть сделано лишь в целом по их составу.
Поиск групп (серий) первого типа производился в примерах 2 и 3 предыдущего раздела. По отношению к массиву это может быть, например, серия положительных элементов. Здесь признаком начала группы является индекс первого положительного элемента, а признаком конца группы – индекс ближайшего неположительного элемента.
Примером группы второго типа является серия элементов, симметричных относительно своей середины. Здесь нельзя по значению одного элемента указать начало или конец группы, но можно определить, является ли подмассив, начиная с i-го элемента и кончая j-ым элементом, симметричным относительно своей середины.
Рассмотрим вначале методику поиска групп первого типа. Алгоритм функционирования программы в этом случае сводится к следующему.
1. Для искомой группы ставятся в соответствие две переменные: переменная k1, определяющая позицию первого элемента группы, и переменная k2, индицирующая конец группы (позицию элемента, непосредственно следующего за последним элементом группы). В этом случае длина группы (количество входящих в нее элементов) равна k2 - k1. Поиск очередной группы производится, начиная с позиции k2+1, где k2 определяет конечную границу предыдущей группы. Поиск конца текущей группы осуществляется, начиная с позиции k1+1, где k1 определяет начало данной группы.
2. В программу включаются две функции, осуществляющие поиск начала и конца группы по соответствующим признакам. Для серии положительных элементов, как было выше указано, признаком начала группы является выполнение условия , признаком конца группы - . Если при обращении к функции поиска соответствующий признак не найден, то ее выходное значение принимается равным нулю. Обозначим для общности имена этих функций SignBegin(k:integer):integer и SignEnd(k:integer):integer, где k - позиция начала поиска.
3. Общий поиск осуществляется в цикле While под управлением булевской переменной Cond, сохраняющей значение true до тех пор, пока продолжается поиск.
4. На старте общего поиска переменной k2 присваивается нулевое значение, переменной Cond - значение true.
5. В начальной части цикла While определяется положение очередной группы: k1:=SignBegin(k2+1).
Если k1 = 0, то это означает, что в массиве таких групп больше нет. Тогда переменной Cond присваивается значение false, что ведет к прекращению работы цикла While.
6. Если k1 > 0, то производится поиск конца группы: k2 := SignEnd(k1+1).
Если k2 = 0, то это означает, что последний элемент массива принадлежит искомой группе. Тогда переменной k2 присваивается значение n+1, где n - количество элементов в массиве, а переменной Cond - значение false.
7. В соответствии с условием задачи производится обработка группы, ограниченной значениями переменных k1 и k2.
Пример 1. В целочисленном массиве определить положение наиболее длинной группы отрицательных элементов, причем в состав группы должно входить не менее трех элементов.
Пусть нам задан массив . Признаком начала группы является истинность отношения , признаком ее конца - истинность отношения .
Program GroupSearch1;
ConstNmax = 500;
Type Ar = array[1..Nmax] of integer;
Vari,k1,k2,n,
l, { размер группы }
lmax, { размер наиболее длинной группы }
kmax : integer; { позиция начального элемента группы }
Cond : boolean;
X : Ar;
{ ----------------------------- }
FunctionSignBegin(k:integer):integer;
Vari : integer;
Begin
SignBegin:=0;
Fori:=k to n do
If x[i]<0 then
Begin
SignBegin:=i; Exit
End;
End{ SignBegin };
{ ----------------------------- }
Function SignEnd(k:integer):integer;
Var i : integer;
Begin
SignEnd:=0;
For i:=k to n do
Ifx[i]>=0 then
Begin
SignEnd:=i; Exit
End;
End{ SignEnd };
{ ----------------------------- }
Begin
Ввод n, X
k2:=0; Cond:=true; lmax:=0;
WhileCond do
Begin
k1:=SignBegin(k2+1);
Ifk1=0 then
Cond:=false
Else
Begin
k2:=SignEnd(k1+1);
If k2=0 then
Begin
k2:=n+1; Cond:=false
End;
l:=k2-k1;
If (l>2) and(l>lmax) then
Begin
lmax:=l; kmax:=k1
End;
End;
End;
Печать lmax, kmax
End.
В этой программе нужно обратить внимание на следующее.
Если в исходном массиве нет отрицательных элементов, то переменной kmax не будет присвоено никакого значения. Тогда в общем случае на печать будет выдано некоторое случайное значение этой переменной.
Отмеченную выше ситуацию называют использованием неопределенной переменной, т.е. переменной, которой в процессе работы программы не присвоено никакого конкретного значения. В реальных программах поиск такого рода ошибки может потребовать значительных затрат времени на отладку программы.
Чтобы избежать неопределенности по отношению к переменной kmax, в программе GroupSearch1 достаточно до начала цикла While установить kmax:=0.
Некоторой модификацией группы первого типа является такая, в которой для определения ее начала и конца необходимо анализировать не один элемент, а два смежных элемента.
Пример 2. В целочисленном массиве определить наиболее длинную серию элементов, строго упорядоченных по возрастанию.
В искомой серии должно выполняться отношение
.
Следовательно, признаком начала серии является выполнение условия , признаком конца – выполнение условия .
Program GroupSearch2;
ConstNmax = 500;
Type Ar = array[1..Nmax] of integer;
Vari,k1,k2,n,
l, { размер группы }
lmax, { размер наиболее длинной группы }
kmax : integer; { позиция начального элемента группы }
Cond : boolean;
X : Ar;
{ ----------------------------- }
FunctionSignBegin(k:integer):integer;
Vari : integer;
Begin
SignBegin:=0;
Fori:=k to n-1 do
If x[i]<x[i+1] then
Begin
SignBegin:=i; Exit
End;
End{ SignBegin };
{ ----------------------------- }
Function SignEnd(k:integer):integer;
Var i : integer;
Begin
SignEnd:=0;
For i:=k to n-1 do
Ifx[i]>=x[i+1] then
Begin
SignEnd:=i; Exit
End;
End{ SignEnd };
{ ----------------------------- }
Begin
Ввод n, X
lmax:=0; kmax:=0;
k2:=0; Cond:=true;
WhileCond do
Begin
k1:=SignBegin(k2+1);
Ifk1=0 then
Cond:=false
Else
Begin
k2:=SignEnd(k1+1);
If k2=0 then
Begin
k2:=n; Cond:=false
End;
l:=k2-k1+1;
If l>lmax) then
Begin
lmax:=l; kmax:=k1
End;
End;
End;
Печать lmax, kmax
End.
Следует отметить, что в этой программе, в отличие от предыдущей, переменная k2 определяет индекс последнего элемента серии, а не индекс элемента, расположенного после последнего элемента серии. Поэтому при k2 = 0 программа устанавливает k2 := n.
Рассмотрим теперь методику поиска групп второго типа. Здесь алгоритм поиска сводится к следующему.
1. Разработать функцию, определяющую выполнение заданного свойства для подмассива, начиная с элемента, имеющего индекс k1, и заканчивая элементом с индексом k2.
2. В основной программе перебирать все возможные подмассивы и, обращаясь к вышеназванной функции, определять, выполнено ли для данного подмассива заданное свойство.
Пример 3.В целочисленном массиве определить положение наиболее длинной серии, симметричной относительно своей середины.
Program GroupSearch3;
ConstNmax = 500;
Type Ar = array[1..Nmax] of integer;
Vari,j,n,
l, { размер группы }
lmax, { размер наиболее длинной группы }
kmax : integer; { позиция начального элемента группы }
, признаком конца группы - 
. Если при обращении к функции поиска соответствующий признак не найден, то ее выходное значение принимается равным нулю. Обозначим для общности имена этих функций SignBegin(k:integer):integer и SignEnd(k:integer):integer, где k - позиция начала поиска.
. Признаком начала группы является истинность отношения 
, признаком ее конца - истинность отношения 
.
.
, признаком конца – выполнение условия 
.