Nickolay.info. Алгоритмы. Количество монотонных цепочек значений в массиве

Под монотонной цепочкой будем понимать последовательность соседних значений элементов массива, каждое из которых больше или равно (меньше или равно) предыдущего, например, в массиве, состоящем из элементов (3, 1, -1, 5, 5, 6, 2) таких цепочек три - (3, 1, -1), (-1, 5, 5, 6) и (6, 2). Если в исходном массиве нет соседних одинаковых элементов, найти количество монотонных цепочек значений в нём очень легко:

#include <stdio.h>

void main () {
 const int n=10;
 int a[n]={5,4,7,1,2,5,6,4,2,-1};
 int i,k=1;
 for (i=1; i<n-1; i++)
  if ((a[i]-a[i-1])*(a[i+1]-a[i])<0) { k++; printf ("%d ",i); }
  //Если a[i]-a[i-1] и a[i+1]-a[i] противоположны по знаку - новая цепочка
 printf ("\nКоличество цепочек=%d",k);
 getchar();
}

Здесь дополнительно печатается номер элемента i, на котором произошла смена цепочки.

Когда в массиве есть соседние одинаковые элементы, задача усложняется лишь немного.

#include <stdio.h>

void main () {
 const int n=10;
 int a[n]={5,5,7,1,2,5,5,4,2,-1};
 int i,k=1,z=0,j=n;
 for (i=1; i<n; i++) {
  if (a[i]==a[i-1]) continue; //Идем по массиву, пока нет разных соседних элементов
  z=(a[i-1]<a[i]?1:-1); //Знак цепочки - убывает (-1) или растет (1)
  j=i+1; //Номер элемента, с которого начинаем анализ
  break;
 }
 for (i=j; i<n; i++) {
  if (a[i]<a[i-1]) {
   if (z==1) { k++; z=-1; }
  }
  if (a[i]>a[i-1]) {
   if (z==-1) { k++; z=1; }
  }
 }
 printf ("\nКоличество цепочек=%d",k);
 getchar();
}

Рейтинг@Mail.ru

вверх гостевая; E-mail