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

[KP580BE51]

unsigned int num_local_maximums( const int array[], size_t size )
for(i = 1; i < size; i++) {
}
return n;
}

Форматирования нет. Еще одно интервью завалено.

[dimp]

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

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

[kostia00]

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

Каково ваше определение: что считается сранвением? if (x) где x - bool, это тоже сравнение по-моему.

[KP580BE51]

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

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

[Izh]

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

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

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

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

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

point x* is a local (or relative) maximum of a function f if there exists some ε > 0 such that f(x*) ≥ f(x) for all x with |x-x*| < ε. On a graph of a function, its local maxima will look like the tops of hills.

То есть по этому определению, если у вас есть две соседние
(попадающие в ε-окрестность друг друга) точки, значения функции которых равны и одна из которых является
локальным максимумом, то другая также должна быть
локальным максимумом.

[Izh]

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

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

Вы меня опередили.

[KP580BE51]

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

Ну и хорошо. Удачи в поиске телепатов.

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

Вы спорите с правильностью решения задачи.

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

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

То есть по этому определению, если у вас есть две соседние
(попадающие в ε-окрестность друг друга) точки, значения функции которых равны и одна из которых является
локальным максимумом, то другая также должна быть
локальным максимумом.

Еще раз. Удачи в поиске телепатов.

[Иоп]

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

ППКС!
Не знаю как в программировании, а в нашей области, если потенциальный работодатель задаст подобную задачку на интервью, то потенциальный сотрудник его пошлет лесом. Потому что любая работа - это сотрудничество. И если работодатель позволяет себе неточности в постановке задачи, но требует точности в решении, то сотрудничества не получится! Мы называем это профессиональной этикой, которой похоже нет в программировании.

[KP580BE51]

ППКС!
Не знаю как в программировании, а в нашей области, если потенциальный работодатель задаст подобную задачку на интервью, то потенциальный сотрудник его пошлет лесом. Потому что любая работа - это сотрудничество. И если работодатель позволяет себе неточности в постановке задачи, но требует точности в решении, то сотрудничества не получится! Мы называем это профессиональной этикой, которой похоже нет в программировании.

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

[Izh]

Ну и хорошо. Удачи в поиске телепатов.

Интересно то, что довольно много народу решило эту
задачку правильно.

Вы спорите с правильностью решения задачи.

Разумеется. Она не работает для массива нулевой длины.

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

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

[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-и, то нет. Вы, случайно, не физик?