Привет всем.
Помогите получить алгоритм следующей задачи.
Последовательность назвается пилообразной, если a1<a2>a3<a4>...>ak или a1>a2<a3>a4<...<ak.
В массиве А(m) найти самую длиную пилооброзную последовательность.
Буду благодарен.
Николай.
Здравствуйте, Nick_2003, Вы писали:
N_>Последовательность назвается пилообразной, если a1<a2>a3<a4>...>ak или a1>a2<a3>a4<...<ak.
N_>В массиве А(m) найти самую длиную пилооброзную последовательность.
А в чем тут проблема?
Я думаю так ( это не тестировалось ) :
int start = 0, end = 0;
for(int n = 1; n < count - 1; ++n)
{
int n1 = n;
while(((a[n - 1] > a[n]) == (a[n] < a[n + 1])
|| (a[n - 1] < a[n]) == (a[n] > a[n + 1]))
&& n < count - 1)
++n;
if(n - n1 > start - end)
{
start = n1 - 1;
end = n;
}
while(((a[n - 1] >= a[n]) == (a[n] >= a[n + 1])
&& n < count - 1)
++n;
}
// здесь start и end индексы первого и последнего элемента максимальной пилообразной подпоследовательности
... << RSDN@Home 1.1 alpha 1 >>
Здравствуйте, Рома Мик, Вы писали:
Чего-то я ошибся зачем-то
РМ>РМ>int start = 0, end = 0;
РМ>for(int n = 1; n < count - 1; ++n)
РМ>{
РМ> int n1 = n;
РМ> while(((a[n - 1] > a[n]) == (a[n] < a[n + 1])
РМ> || (a[n - 1] < a[n]) == (a[n] > a[n + 1]))
РМ> && n < count - 1)
РМ> ++n;
РМ> if(n - n1 > start - end)
РМ> {
РМ> start = n1 - 1;
РМ> end = n;
РМ> }
РМ> while((a[n - 1] > a[n]) != (a[n] < a[n + 1])
РМ> && (a[n - 1] < a[n]) != (a[n] > a[n + 1])
РМ> && n < count - 1)
РМ> ++n;
РМ>}
РМ>// здесь start и end индексы первого и последнего элемента максимальной пилообразной подпоследовательности
РМ>
... << RSDN@Home 1.1 alpha 1 >>
Здравствуйте, Nick_2003, Вы писали:
N_>Привет всем.
N_>Помогите получить алгоритм следующей задачи.
N_>Последовательность назвается пилообразной, если a1<a2>a3<a4>...>ak или a1>a2<a3>a4<...<ak.
N_>В массиве А(m) найти самую длиную пилооброзную последовательность.
N_>Буду благодарен.
N_>Николай.
Представь, что числа в массиве это значения кусочно линейной функции в точках 1 ... n. Как только ты нарисуешь примерный график решение будет очевидным. Тебе нужны локальные максимумы и минимумы этой функции, которые будут чередоваться давая, то что ты называешь пилообразной последовательностью. Естественно, максимальных последовательностей может быть несколько, но указанная 100% максимальная. Если бы это было не так, то по принципу Дирихле в один из полуинтервалов [M_i,M_{i+1}) (M_i — локальный максимум или минимум функции) попало бы две точки из массива, а функция на таком интервале монотонна => этого быть не может.
Как найти локальные максимумы и минимумы, я думаю, понятно.
