Xpoint
   [напомнить пароль]

Зигзагообразная последовательность

Метки: [без меток]
2009-04-09 18:48:48 [обр] nikov[досье]

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

Скачок — это разность между соседними элементами.

Если точное наименьшее количество выбрасываемых элементов вычислить трудно, то допустимо приближенное решение.

спустя 17 минут [обр] nikov[досье]
Появилась такая идея: находим минимальный и максимальный элемент. У нас будут 4 точки на горизонтальном отрезке: начало, два экстремума и конец. Они разбивают его на 3 части. Если на каждой из частей скачок больше, чем M, то все 3 части опять рекурсивно пытаемся разбивать. Иначе весь отрезок целиком войдет в результирующий зигзаг.
спустя 8 минут [обр] nikov[досье]
Нет, так не получится. Пожалуйста, подскажите идею.
спустя 41 минуту [обр] nikov[досье]
Прошу прощения, в формулировке неточность. На самом деле мне надо максимизировать не количество оставшихся скачков, а сумму их модулей.
спустя 10 часов [обр] Алексей Полушин(0/231)[досье]
Берем четыре идущих подряд числа x1,x2,x3,x3. Если abs(x2-x3)<=M и abs(x2-x3)<=abs(x1-x2) и abs(x2-x3)<=abs(x3-x4), то выкидываем x2,x3 и повторяем операцию с того же места, иначе сдвигаемся на единичку и повторяем операцию.
Powered by POEM™ Engine Copyright © 2002-2005