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

[8K]

Производная для последовательностей вообще не определена.

Ну, уж если интегралы берут по дискретной мере, то неужели для производных ничего не придумали?

Столько много слов - я прям теряюсь. Вы имели в виду интеграл Лебега по дискретной мере?

Не берите в голову. Это все слова, что я запомнил с курса мат.анализа.

[Иоп]

Вот это сильно!!! Можно хоть сейчас в Юмор переносить!

[TheKonst]

про неусточивость вообще ничего не знаю

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

Весточка из родных пенатов.

Черт побери, 8К! Я искал ету книгу где только мог! Вот уж спасибо за ссылку!

[IvanGrozniy]

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

Тем не менее все это не имеет никакого отношения к определению локального максимума (минимума) у дискретного сигнала.

Браво
Я уж и забывать начал и все никак вспомнить не мог точное определение производной.

[Flash-04]

мои 5 центов. мое сильное убеждение, что подобные задачи создаются не с целью раскрыть таланты интервьюируемого, а чтобы его завалить можно было сильно это мне напоминает дополнительные задачи на институстких экзаменах

[IvanGrozniy]

мои 5 центов. мое сильное убеждение, что подобные задачи создаются не с целью раскрыть таланты интервьюируемого, а чтобы его завалить можно было сильно это мне напоминает дополнительные задачи на институстких экзаменах

Кто позже всех завалилися тот молодец и будет работать. Справедливо?

[Flash-04]

Кто позже всех завалилися тот молодец и будет работать. Справедливо?

работать будет тот кого не завалят а насчет справедливости, меня проинформировали что такого явления в природе нет

[KirAleks]

Определение максимума в математике достаточно однозначно - это точка в которой первая производная меняет знак.

Определение локального максимума функции действительно однозначно, но никакой "производной" там нет, вобще говоря, производная может быть вобще неопределена в этой точке, как тогда говорить о том, что она "меняет знак". Точка x0 является локальным максимумом f(x), если существует такое e>0, что для любого x, |x-x0|<e, выполняется f(x0)>=f(x)

http://en.wikipedia.org/wiki/Extremum

a maximal extremum (maximal turning point or relative maximum) is one where the derivative of the function changes from positive to negative;

В этом смысле что искать точку где array[i-1]- array[i] "changes from positive to negative" более правильно. математически, а не по мнению "lzh"

По вашему ответу становится ясно что математический анализ в Университете вам не преподавали. Я целиком поддерживаю определение Dimpa (в математическом смысле)

[KP580BE51]

По вашему ответу становится ясно что математический анализ в Университете вам не преподавали. Я целиком поддерживаю определение Dimpa (в математическом смысле)

Вы над этим думали 2 месяца?

[KirAleks]

По вашему ответу становится ясно что математический анализ в Университете вам не преподавали. Я целиком поддерживаю определение Dimpa (в математическом смысле)

Вы над этим думали 2 месяца?

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

[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 ) 

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

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

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

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

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