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

[ПБХ]

Если пользоваться "определением из Wikipedia", которое, строго говоря, неприменимо в Вашем случае, то каждый элемент любого массива является локальным максимумом.

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

[underdog]

[...moderated...500000...Privet....]

[Izh]

Если пользоваться "определением из Wikipedia", которое, строго говоря, неприменимо в Вашем случае, то каждый элемент любого массива является локальным максимумом.

Я, видимо, понимаю это определение не так, как вы. Как, по
вашему, это определение будет работать, для
последовательности 1, 2, 3? Впрочем, это уже оффтопик.

[ПБХ]

Если пользоваться "определением из Wikipedia", которое, строго говоря, неприменимо в Вашем случае, то каждый элемент любого массива является локальным максимумом.

Я, видимо, понимаю это определение не так, как вы. Как, по
вашему, это определение будет работать, для
последовательности 1, 2, 3? Впрочем, это уже оффтопик.

Не знаю, насколько это - оффтопик. Вы все-таки автор следующего пассажа:

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

После этого Вы дали неверное определение, а потом его еще неверно применили. Ну да ладно. Отвечу на Ваш вопрос.

Последовательность - это функция натурального аргумента. То есть в Вашем примере Вы рассматриваете функцию
a(1) = 1;
a(2) = 2;
a(3) = 3.

a(2) = 2 будет локальным максимумом (x_0 = 2, a(x_0) = 2) согласно данному Вами определению, потому что если взять \eps = 0.5, то неравенство

| x - x_0 | < \eps

имеет только одно решение в области определения функции a(), а именно такие решения Вы рассматриваете, т.к. иначе f(x) из определения локального максимума не определено. Это решение x = 2. Тогда

a(x) <= a(x_0)

Ч.т.д.

[Taffi]

Вы, случайно, не физик?

Нет. А Вы не проподователь ВУЗа? Что-то мне этот топик напомнил про веселые студенческие годы

[vm__]

Вы, случайно, не физик?

А Вы не проподователь ВУЗа?

А нет ли среди уважаемой публики кого в очках-пиджаке-шляпе?

[Izh]

После этого Вы дали неверное определение, а потом его еще неверно применили. Ну да ладно. Отвечу на Ваш вопрос.

Это не мое определение, а Wikipedi-и. И ... можно я не буду
с вами спорить? Обращу ваше внимание только на
следующий факт из той же Wikipedi-и:

The concepts of maxima and minima are not restricted to
functions whose domain is the real numbers. One can talk about
global maxima and global minima for real-valued functions whose
domain is any set. In order to be able to define local maxima and
local minima, the function needs to take real values, and the
concept of neighborhood must be defined on the domain of the
function. A neighborhood then plays the role of the set of x such
that |x - x*| < ε.

[Izh]

Вы, случайно, не физик?

Нет. А Вы не проподователь ВУЗа? Что-то мне этот топик напомнил про веселые студенческие годы

Нет. Хотя мысли про то, чтобы свалить в академию активно
бродят в голове.

[ПБХ]

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

Я сказал в точности то, что сказал. А именно, что данное в теме определение было как минимум "нестандартным" по отношению к последовательностям. (Неверными определения быть скорее всего не могут.) А кроме этого, что в терминах того определения, Ваше понимание локального максимума было неверным.

[AndreyT]

Про отстутствие форматирования вообще
говорить не хочеться.

Все! Интервью завалено! Аднозначно!

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

Простите, но тогда уж надо было бы придраться и к отсутствию комментариев, и к тому, что интервьюируемый не предоставил сиситему unit-тестов для выполнения тестрования написанного им кода, а также к тому, что код был написан без педварительного предоставления в специально заточенные инстанции соответствующего дизайн-документа.

[AndreyT]

Code: Select all

unsigned int num_local_maximums( const int array[], size_t size );

Кстати, уже за такой прототип - no hire.

Если вы уж использовали 'size_t' для передачи размера массива, то и результат надо вызвращать в 'size_t'. Это если это достаточно generic функция (каковой в принципе она и должна быть в подобных задачах).

В более specific функциях же не должно быть 'size_t' ни там, ни там.

[AndreyT]

Я бы реализовывал эту функцию так (при условии подсчета количества максимальных плато, в том числе ширины 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; ; rise = !rise)
    {
      assert(n > 0);

      for (++a, --n; n > 0; ++a, --n)
        if (rise ? *(a - 1) > *a : *(a - 1) < *a)
          break;

      if (n == 0)
        break;

      c += rise;
    }
  }

  return c;
}

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

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

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 тут нет.

[AndreyT]

В качестве в какой-то мере "принципиально отличного" варианта можно предложить вариант с поиском "полустрогого излома":

Code: Select all

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

  if (n > 2)
  {
    const int *p1, *p2, *p3;
                                               
    for (n -= 2, p1 = a, p2 = p1 + 1, p3 = p2 + 1; n > 0; 
           --n, p1 = p2, p2 = p3, ++p3)
      if (*p1 <= *p2 && *p2 > *p3)
        ++c;
  }

  return c;
}

Это вариант в таком виде, несмотря на свою компактность, страдает определенной [формальной] неоптимальностью. Её можно устранить ценой некоторой потери компактности кода.

[8K]

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

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

[Dimchik]

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

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

Вся наука на решетке построена на "дискретных производных". Миллион задач в конечных разностях.