Задачка про локальные максимумы

[KP580BE51]

Не обижайтесь, пожалуйста, просто только что увидел увидел эту задачку. А про математическую подготовку - сразу в глаза бросилось....

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

[KirAleks]

Я бы реализовывал эту функцию так (при условии подсчета количества максимальных плато, в том числе ширины 1, без учета плато на краях массива)
...

Code: Select all

size_t num_local_maximums(const int a[], size_t n)
{
  size_t c = 0;

  if (n > 2)
  {
    unsigned char rise;

    for (++a, --n, rise = *(a - 1) < *a; n > 0; ++a, --n)
      if (rise ? *(a - 1) > *a : *(a - 1) < *a)
      {
        c += rise;
        rise = !rise;
      }
  }

  return c;
}

Но... хм.. может еще чего-то не дотестировал...

Стоит, однако, заметить, что принципиальных отличий от варианта Taffi тут нет.

Я вот предлагаю принципиально новый вариант НА ПОРУГАНИЕ который действительно использует ОДНО !!! сравнение на шаг. Естественно не учитываем проверку на границы массива.
Для простоты чтения конструкции привожу его в алгоритмическом виде. Прошу заметить что все приведeнное ниже можно легко модернизировать для потока данных.
Специально для К155ЛА3 : число сбросов процессорной очереди, которое приводит к тормозам (зависит это на самом деле от ВЫПОЛНЕНИЯ инструкции jmp, а не от операции сравнения -как вы писали- однако действительно при сравнении обычно jmp-подобная инструкция вставляется в негативную ветвь ) здесь прямо пропорционально числу экстремумов в массиве.
А ну и сложность алгоритма соот-но T(n)=n+C;

Code: Select all

size_t num_local_maximums(const int a[], size_t n) 
{ 
  size_t maxc = 0; 
  unsigned int i = 2;
  if (n>2) {
      if (a[1]<a[0])  goto label1;
      label2:
      while ( i<=n ) {
         if (a[i]<a[i-1]) {
           maxc++;
           goto label1;
         }
         i++  ;
      }
      label1:
      while ( i<=n ) {
         if (a[i]>=a[i-1]) {
           goto label2;
         };
         i++;
      }
  }

 return maxc;
}

[Izh]

Code: Select all

size_t num_local_maximums(const int a[], size_t n) 
{ 
  size_t maxc = 0; 
  unsigned int i = 2;
  if (n>2) {
      if (a[1]<a[0])  goto label1;
      label2:
      while ( i<=n ) {            <-------------
         if (a[i]<a[i-1]) {         <-------------
           maxc++;
           goto label1;
         }
         i++  ;
      }
      label1:
      while ( i<=n ) {             <-------------
         if (a[i]>=a[i-1]) {       <-------------
           goto label2;
         };
         i++;
      }
  }

 return maxc;
}

С ходу вижу грубую ошибку. Что произойдет, когда i достигнет n?

[KirAleks]

....
Для простоты чтения конструкции привожу его в алгоритмическом виде. Прошу заметить что все приведeнное ниже можно легко модернизировать для потока данных.
.....

2 Izh : Ваша оценка, как вы ее сами назвали "с ходу", не является по оценкой по существу.

Code: Select all

 while ( i<=n ) 

- алгоритмическая проверка конца массива. Сущьность не в том чтобы оценить выходит ли индекс за границы массива, а в реализации алгоритма позволяющего за ОДНО СРАВНЕНИЕ отсечь локальные екстремумы.

Есть ли какие-то замечания по поводу работы самого алгоритма?
Тут фактически второе статическое сравнение заменено двумя операторами goto.

[Izh]

2 Izh : Ваша оценка, как вы ее сами назвали "с ходу", не является по оценкой по существу.

Code: Select all

 while ( i<=n ) 

- алгоритмическая проверка конца массива. Сущьность не в том чтобы оценить выходит ли индекс за границы массива, а в реализации алгоритма позволяющего за ОДНО СРАВНЕНИЕ отсечь локальные екстремумы.

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

Одним из важнейших критериев "хорошести" алгоритма, на мой взгляд, является его работоспособность. Если он не работает, то о чем можно говорить?

Есть ли какие-то замечания по поводу работы самого алгоритма?

Замечания есть. Дайте только, пожалуйста, определение локального максимума, которым Вы пользовались.