Есть ряд чисел: 0,0,3,3,5,4,5,7,6,0,2,0...
Максимальная разница между числами в одном подряде = 5
Нужно разбить ряд так что бы получить как можно длинее подряды:
[0,0,3,3],[5,4,5,7,6],[0,2,0] - вариант не очень
[0,0,],[3,3,5,4,5,7,6],[0,2,0] - так получше
Как это сделать эффективно за один проход? Буду рад ссылкам и обьяснениям.

на сколько я понимаю очень важен факт является ли последовательность конечной или бесконечной..

Последовательность конечна.
Алгоритм должен быть с минимум проходов. Спросил у гугла, ничего... может просто не понял или спросил не правильно...

Интересно что сам(мозгами) могу разбить ряд, но описать точно что я делаю до алгоритма не могу

Начни с того, что сначала ищешь подряд максимальной длины.

Sardar

Цитата

Есть ряд чисел: 0,0,3,3,5,4,5,7,6,0,2,0...

Дык [0,0],[3,3,5,4,5,7,6,0,2,0]... еще лучше?
Попробуй пояснить смысл задачи - может есть обходные пути? ибо однопроходно это не делается (запоминать неопределенное количество членов ряда не лучше второго прохода)

В: разница должна быть меньше 5 у минимального и максимального элемента в ряде. Нет условий что у последующего предыдущего разница должна быть минимальной?(у.1 , у.2)
В голову приходят несколько простых вариантов.
1) Выполняет у.1,у.2. Пусть у тебя все числа ограничены сверху (занимают 1 байт, допустим).Тогда ты спокойно можешь создать таблицу 256 символов -- частот появления определенного числа,
тогда ряды строятся елементарно(допустим ряд с номером к -- обозначение k(0)-- значение к стоит на 0 месте в подряде
(k(0),,,k(freq[k]), ..... ,k+5,,,,,k+5(freq[k]+freq[k+1]+..freq[k+5])). Естесственно значения с 0 частотами пропускаются. Вариант дурацкий -- на байт еще памяти хватит на dword уже придется напрягаться.(Хотя если кодируешь текст такой способ вполне оправдан и даже носит имя кого-то, кто не поленился ему это имя дать)
2) Тоже тривиальный вариант -- более медленный естественно(уж не знаю как это слово пишется). Алгоритм трепологически такой: (у.2 не выполняется)
Общая инфа:
есть 2 связный(для удобства) список, каждый элемент которого тоже 2 связный список

1 -ое слово:
в ставляем в начало списка
2-ое слово если расстояние от первого меньше 5 -- в тот же узел, если нет в следующий.
Узлу приписывается 2 числа минимальное, маскимальное значение -- если новое слово принадлежит (входит в диапазон +- 5)сразу 2 узлам(придется по ни пробегать ) -- слово всатвляется, диапазон пересчитывается, узлы объединяются, если принадлежит только 1 -- втавляется в него, если ни 1 объявляется новый узел.

Вот так.

динамическое программирование:
1. делаем табличку, по горизонтали заданная последовательность, по вертикали - номер подряда
2. решение задачи - каждому элементу последовательности сопоставить номер подряда

постепенно по предыдущим данным заполняются все клеточки таблицы

А для первого примера
[0,0,0,0,2],[3,3,4,5,7]
не лучше?
Просто задача нечетко сформулирована, пытаюсь понять, что является решением.

Это сообщение отредактировал(а) Alex101 - 6.9.2004, 16:55

Цитата(Akina @ 6.9.2004, 08:37)

Дык [0,0],[3,3,5,4,5,7,6,0,2,0]... еще лучше?

Нет, в ряду числа разница которых больше 5: 0-7 - что не допустимо

Цитата(podval @ 6.9.2004, 07:33)

Начни с того, что сначала ищешь подряд максимальной длины.

Пока ищу как это сделать.
Sined, Alex101 перемещать элементы в ряду нельзя, нужно просто порезать ряд на подряды с минимальной разницей в элементах(не более n=5)
По этой причине первый способ не подходит.
Во втором способе не разобрался... Число не должно входить в какой-то определённый диапазон. Нужно что бы разница между соседними числами в одном ряду была не более n и при этом найти самые длинные подряды.

Цитата(maxim1000 @ 6.9.2004, 12:34)

решение задачи - каждому элементу последовательности сопоставить номер подряда

А на примере можно это показать? С первого раза не разобрался....

Вот ! Наконец - то начинает приоткрываться завеса тайны над постановой задачи.
Примечание: Для того, чтобы решить задачу точно/строго надо придумывать что-то типа целевой функции(т.е. чем мы в конкретной ситуации можем чуть-чуть жертвовать длинной ряда или минимальностьб расстояния -- если ты четко поставишь задачу и представкишь такую функцию в аналитическом виде -- буду знать к кому отсылать людей за автографами. )

Тогда (опять таки трепологически) можно заформализовать то, что ты написал в первом примере.(в данном случае длинна ряда важнее минимальности)
к-й шаг:
Мы не можем переставлять числа => можем работать только с текущим подрядом или начинать следующий. Пусть пришло число(А) разница с предыдущим у которого >= _dopustimiiDiapazon/n (n выбираем сами). Тогда это число может быть либо продолжением текущего либо началом нового ряда. Если за этим числом пришло число(равные пропускаем) не входящие в диапазон , но имеющее меньшую разницу с А, чем конец предыдущего ряда -- тогда это новый ряд
( у.1) начинающийся с А), если число входит в диапазон, и разница у следующего за А числа(В) с числом перед А(А_1) меньше разницы(А,А_1) то тогда А является числом текущего подряда(у.2) -- на В проводим ту же процедуру , если разница(A_1,B) больше разница(А_1,А) то складируем и А и В в буффер(т.н. непонятные значения) пока не выполнится у.1 | у.2 --тогда либо весь буффер новый ряд либо весь буффер старый ряд.
Кузяво, конечно, но видимо хоть как-то поможет.

Цитата(Sardar @ 5.9.2004, 08:05)

[0,0,],[3,3,5,4,5,7,6],[0,2,0] - так получше

А такой вариант:
[0,0,3,3,5,4,5],[7,6],[0,2,0]
Чем хуже?
Как определить "лучшесть", если возможно несколько одинаковых (примерно) вариантов?

Есть какая-то идея...
Допустим, делим пополам:
[0,0,3,3,5,4] [5,7,6,0,2,0]
Первая половина удовлетворяет условию, вторая половина - нет, тогда разбиваем ее пополам:
[5,7,6] [0,2,0]
Обе половины удовлетворяют условиям,
Смотрим, можно ли что-то улучшить (добавить элемент в одну из частей)
Нет
Получаем:
[0,0,3,3,5,4] [5,7,6] [0,2,0]
Снова смотрим, можно ли что-то улучшить - Да
[0,0,3,3,5,4,5] [7,6] [0,2,0]
Получается "спуск" и "подъем"
На "спуске" пытаемся сделать "правильные" ряды,
на "подъеме" - их "улучшаем".

Но возможно несколько вариантов "улучшений", надо выбирать лучший.
Не знаю пока, правильно это, или нет...
Если такой ряд [0,0,3,7,3,5,4,5,6,0,2,0] , то
[0,0,3,7,3,5] [4,5,6,0,2,0]
Разбили, обе половины не удовлетворяют условию
[0,0,3] [7,3,5] [4,5,6] [0,2,0]
Снова разбили (два раза)
[0,0] [3,7,3,5] [4,5,6] [0,2,0]
Улучшили
[0,0] [3,7,3,5,4,5,6] [0,2,0]
Еще раз улучшили

P.S.
К чему надо стремиться - к созданию максимального ряда, даже если окажется, что какие-то ряды будут состоять из одного числа?
Задача все равно все еще плохо поставлена - непонятно, что является результатом...

Это сообщение отредактировал(а) Alex101 - 7.9.2004, 11:13

Цитата(Alex101 @ 7.9.2004, 09:43)

А такой вариант: [0,0,3,3,5,4,5],[7,6],[0,2,0] Чем хуже?

Тем что 5-0+1 = 6

Цитата(Alex101 @ 7.9.2004, 10:02)

Задача все равно все еще плохо поставлена - непонятно, что является результатом...

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

Часть дороги со стаканчиками разделленной границами будем называть подрядом. У подряда есть ключевое свойство: разница между самым наполненным стаканчиком и самым не наполненным не должна превышать N.

Основная цель: найти самые длинные ряды. Xороший результат: несколько длинных рядов и куча очень маленьких(2-3 стаканчика)

Графически это выглядит так:

Цитата

***|*********|*|**|***********|...

Мне кажется это должно встречатся графике(области с схожим цветом).

Как то не получается описать задачу формально

Цитата(Sined @ 7.9.2004, 07:14)

пока не выполнится у.1 | у.2 --тогда либо весь буффер новый ряд либо весь буффер старый ряд.

Вот здесь остановился, как y.1|y.2 должно выполнится? Пока результат алгоритма: [0,0,3,3,5,4,5,7,6,0,2,0] -> [0,0,`3,3],[5,4,`5,7,6,0],[2,0] - апострофы там где сохраненно смещение как возможного ряда. Где я ошибся?

Цитата(Alex101 @ 7.9.2004, 10:02)

Первая половина удовлетворяет условию, вторая половина - нет

Да я запарюсь проверять, проще пробежатся по ряду и разбить на подряды по принципу: число лежит в диапазоне :минимальное число(меняется по ходу просмотра) + максимальная разница:, тогда в этот ряд, иначе открываем следующий. Затем пробежатся по второму разу и сдвинуть границы.
Есть варианты умнее?

Пробуем
Шаги
1) 0 -- новый ряд
2) 0 -- вставляем в предыдущий
3) 3 -- хз. толи новый толи предыдущий --- в буффер
4) 3 -- аналогично
5) -- 7) все в буффере
8) число 7 -- определяем что выгоднее вставить буффер в предыдущий ряд 0,0 или начать новый. Выгода может быть определена посредством сравнения 7) -- т.е. число 5 и 8)(7) и 3) и 2)
определяем, что выгоднее строить новый ряд 7-5 < 3-0 => повезло и получаем картинку как ты и описал ранее
9) 0 -- новый ряд
10) 2 -- хз
11) 0 -- завершение произошло числом входящим в "диапазон" предыдущего ряда => все в предыдуший ряд. Подогнали и получили

Цитата(Sardar @ 5.9.2004, 11:05)

[0,0,],[3,3,5,4,5,7,6],[0,2,0] - так получше

З.Ы. Что я не написал
1) Если буффер не пуст и не выполнены у1(у1 надо изменить как : наибольшая разница у вновь пришедшего числа чисел в буффере и предыдущем ряду недопустимо большая)
(у2 -- бред больного человека, но что-то типа него нужно) любое число заталкивается в буффер. Критерий начала новго ряда и запихивание всего буффера в старый такой:
Если разница между последним подтвержденным числом старого ряда и первым символом буферв меньше разницы последнего числа в буффере и вновь пришедшего символа -- новый символ -- начало нового ряда, весь буффер предыдущий ряд, если нет, то наоборот).