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

[Izh]

unsigned int num_local_maximums( const int array[], size_t size )
{
BOOL bGrow = FALSE;
unsigned int n = 0, i;

for(i = 1; i < size; i++) {
if (array[i] >= array[i-1])
bGrow = TRUE;
else if (bGrow) {
n++;
bGrow = FALSE;
}
}
return n;
}

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

[Gabo]

К решению Taffi надо добавить в начало

Code: Select all

   if(size < 2)
      return size;

[Izh]

К решению Taffi надо добавить в начало

Code: Select all

   if(size < 2)
      return size;

При той интерпретации локального максимума, которой
он пользуется, то не надо. Иначе решение не будет
консистетным. Его определение можно уточнить так:
Локальный максимум это элемент, который больше своих
соседей и не лежащий на краях массива. То есть если у
вас только один элемент в массиве, то он не может быть
локальным максимумом. Любопытно, однако, что данное
определение, которое использовано уже в двух
решениях не очень очевидно. Так как:

1. Не очевидно поведение на краях массива.
2. Игнорируются плоские локальные максимумы.

[Taffi]

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

Сейчас - да.

2. Игнорируются плоские локальные максимумы.

Ну не совсем. Для "0 1 1 1 0" вернет 1.

[Izh]

2. Игнорируются плоские локальные максимумы.

Ну не совсем. Для "0 1 1 1 0" вернет 1.

Если понимать под локальным экстремумом точку, где
производная меняет знак, то вы правы. Если пользоваться
определением из Wikipedi-и, то нет. Вы, случайно, не физик?

[ПБХ]

Если пользоваться "определением из 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-тестов для выполнения тестрования написанного им кода, а также к тому, что код был написан без педварительного предоставления в специально заточенные инстанции соответствующего дизайн-документа.