C++: максимальная и минимальная цепочка элементов с чередованием признака

Алгоритм проверки чередования признака в массиве - вещь хорошая, но не даёт ответа на вопрос, где именно началась серия и какова наибольшая или наименьшая длина серии элементов, на которой признак чередуется.

Если ищем максимальную цепочку (например, чисел, меняющих знак по отношению к своим соседям в массиве), соответствующая функция будет достаточно проста:

#define SIGN(a) ((a)<0?-1:((a)>0?1:0))

void max_alternating_series (int n, int *a, int &start, int &maxlen) {
 int z=SIGN(a[0]),i=1,len,s;
 start=-1;maxlen=0;
 while (i<n) {
  while (SIGN(a[i])==z) {
   z=SIGN(a[i]); i++; if (i==n) return;
  }
  s=i-1; len=1;
  while (SIGN(a[i])!=z) {
   len++; z=SIGN(a[i]); i++; if (i==n) break;
  }
  if (len>maxlen) { maxlen=len; start=s; }
 }
}

На вход функции подаётся размерность массива n и указатель на целочисленный массив a, результаты возвращаются через параметры start (номер элемента, с которого начинается серия, нумерация с нуля) и maxlen (максимальная длина цепочки).

С минимальной длиной цепочки всё не так однозначно. Например, для массива (-1, -1, 2, -3, 4, 4) что считать минимальной длиной серии - (-1, 2, -3, 4) или (-1, 2)? Поскольку второй случай тривиален - любая смена знака даст серию длиной 2, и это будет ответ, рассмотрим только первый - пока смена знака продолжается, серия не заканчивается.

Но в этом случае поиск минимальной цепочки мало чем отличается от максимальной, просто реализуем стандартный алгоритм поиска минимума вместо максимума:

void min_alternating_series (int n, int *a, int &start, int &minlen) {
 int z=SIGN(a[0]),i=1,len,s;
 start=-1;minlen=n+1;
 while (i<n) {
  while (SIGN(a[i])==z) {
   z=SIGN(a[i]); i++; if (i==n) return;
  }
  s=i-1; len=1;
  while (SIGN(a[i])!=z) {
   len++; z=SIGN(a[i]); i++; if (i==n) break;
  }
  if (len<minlen) { minlen=len; start=s; }
 }
}

Напишем тестовую программку для обеих функций:

#include <stdio.h>

void test (int n, int *a) {
 int start,len;
 printf ("\n");
 for (int i=0; i<n; i++) printf ("%d ",a[i]);
 min_alternating_series (n,a,start,len);
 printf ("\nMIN Start=%d, Len=%d",start,len);
 max_alternating_series (n,a,start,len);
 printf ("\nMAX Start=%d, Len=%d",start,len);
}

int main () {
 const int n=8;
 int a[n]={1,-2,3,-4,5,-6,7,-8};
 test (n,a);
 int b[n]={1,2,3,-4,5,-6,7,-8};
 test (n,b);
 int c[n]={1,2,3,4,5,6,7,-8};
 test (n,c);
 int d[n]={-1,2,3,4,5,6,7,8};
 test (n,d);
 int e[n]={1,2,3,4,5,-6,7,-8};
 test (n,e);
 int f[n]={-1,2,-3,4,5,6,7,8};
 test (n,f);
 int g[n]={1,2,-3,4,0,6,7,8};
 test (n,g);
 int h[n]={1,-2,3,4,-4,6,7,-8};
 test (n,h);
 int i[n]={-1,2,3,-4,5,6,-7,8};
 test (n,i);
 int j[n]={1,-2,3,-4,-5,6,0,-8};
 test (n,j);
 int k[n]={0,1,0,1,1,1,0,1};
 test (n,k);
 getchar();
 return 0;
}

И посмотрим, что она выдаёт:

1 -2 3 -4 5 -6 7 -8
MIN Start=0, Len=8
MAX Start=0, Len=8
1 2 3 -4 5 -6 7 -8
MIN Start=2, Len=6
MAX Start=2, Len=6
1 2 3 4 5 6 7 -8
MIN Start=6, Len=2
MAX Start=6, Len=2
-1 2 3 4 5 6 7 8
MIN Start=0, Len=2
MAX Start=0, Len=2
1 2 3 4 5 -6 7 -8
MIN Start=4, Len=4
MAX Start=4, Len=4
-1 2 -3 4 5 6 7 8
MIN Start=0, Len=4
MAX Start=0, Len=4
1 2 -3 4 0 6 7 8
MIN Start=1, Len=5
MAX Start=1, Len=5
1 -2 3 4 -4 6 7 -8
MIN Start=6, Len=2
MAX Start=0, Len=3
-1 2 3 -4 5 6 -7 8
MIN Start=0, Len=2
MAX Start=2, Len=3
1 -2 3 -4 -5 6 0 -8
MIN Start=0, Len=4
MAX Start=0, Len=4
0 1 0 1 1 1 0 1
MIN Start=5, Len=3
MAX Start=0, Len=4

Как видите, некоторые тесты (где искомая цепочка смены знаков не единственна) отличаются.

Ноль в массиве считается сменой знака. Если это не так, поменяйте макрос SIGN. Если есть несколько одинаковых серий, функции найдут первую из них. Для поиска последней серии поменяйте в них проверки if (len<minlen) на if (len<=minlen) и if (len>maxlen) на if (len>=maxlen)

Вместо SIGN можно написать другой макрос (функцию) проверки нужного свойства у очередного элемента массива.

15.11.2013, 21:51 [10263 просмотра]