Алгоритм должен быть с минимум проходов. Спросил у гугла, ничего... может просто не понял или спросил не правильно...
Интересно что сам(мозгами) могу разбить ряд, но описать точно что я делаю до алгоритма не могу
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Разбить ряд чисел на подряды |
| Автор: Sardar 5.9.2004, 11:05 |
| Есть ряд чисел: 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] - так получше Как это сделать эффективно за один проход? Буду рад ссылкам и обьяснениям. |
| Автор: Fearless 5.9.2004, 21:17 |
| на сколько я понимаю очень важен факт является ли последовательность конечной или бесконечной.. |
| Автор: Sardar 5.9.2004, 23:54 |
| Последовательность конечна. Алгоритм должен быть с минимум проходов. Спросил у гугла, ничего... может просто не понял или спросил не правильно... Интересно что сам(мозгами) могу разбить ряд, но описать точно что я делаю до алгоритма не могу |
| Автор: podval 6.9.2004, 08:33 |
| Начни с того, что сначала ищешь подряд максимальной длины. |
| Автор: Akina 6.9.2004, 09:37 | ||
Sardar
Дык [0,0],[3,3,5,4,5,7,6,0,2,0]... еще лучше? Попробуй пояснить смысл задачи - может есть обходные пути? ибо однопроходно это не делается (запоминать неопределенное количество членов ряда не лучше второго прохода) |
| Автор: Sined 6.9.2004, 12:04 |
| В: разница должна быть меньше 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 объявляется новый узел. Вот так. |
| Автор: maxim1000 6.9.2004, 13:34 |
| динамическое программирование: 1. делаем табличку, по горизонтали заданная последовательность, по вертикали - номер подряда 2. решение задачи - каждому элементу последовательности сопоставить номер подряда постепенно по предыдущим данным заполняются все клеточки таблицы |
| Автор: Alex101 6.9.2004, 16:55 |
| А для первого примера [0,0,0,0,2],[3,3,4,5,7] не лучше? Просто задача нечетко сформулирована, пытаюсь понять, что является решением. |
| Автор: Sardar 7.9.2004, 00:21 | ||||||
Нет, в ряду числа разница которых больше 5: 0-7 - что не допустимо
Пока ищу как это сделать. Sined, Alex101 перемещать элементы в ряду нельзя, нужно просто порезать ряд на подряды с минимальной разницей в элементах(не более n=5) По этой причине первый способ не подходит. Во втором способе не разобрался... Число не должно входить в какой-то определённый диапазон. Нужно что бы разница между соседними числами в одном ряду была не более n и при этом найти самые длинные подряды.
А на примере можно это показать? С первого раза не разобрался.... |
| Автор: Sined 7.9.2004, 08:14 |
| Вот ! Наконец - то начинает приоткрываться завеса тайны над постановой задачи. Примечание: Для того, чтобы решить задачу точно/строго надо придумывать что-то типа целевой функции(т.е. чем мы в конкретной ситуации можем чуть-чуть жертвовать длинной ряда или минимальностьб расстояния -- если ты четко поставишь задачу и представкишь такую функцию в аналитическом виде -- буду знать к кому отсылать людей за автографами. ) Тогда (опять таки трепологически) можно заформализовать то, что ты написал в первом примере.(в данном случае длинна ряда важнее минимальности) к-й шаг: Мы не можем переставлять числа => можем работать только с текущим подрядом или начинать следующий. Пусть пришло число(А) разница с предыдущим у которого >= _dopustimiiDiapazon/n (n выбираем сами). Тогда это число может быть либо продолжением текущего либо началом нового ряда. Если за этим числом пришло число(равные пропускаем) не входящие в диапазон , но имеющее меньшую разницу с А, чем конец предыдущего ряда -- тогда это новый ряд ( у.1) начинающийся с А), если число входит в диапазон, и разница у следующего за А числа(В) с числом перед А(А_1) меньше разницы(А,А_1) то тогда А является числом текущего подряда(у.2) -- на В проводим ту же процедуру , если разница(A_1,B) больше разница(А_1,А) то складируем и А и В в буффер(т.н. непонятные значения) пока не выполнится у.1 | у.2 --тогда либо весь буффер новый ряд либо весь буффер старый ряд. Кузяво, конечно, но видимо хоть как-то поможет. |
| Автор: Alex101 7.9.2004, 10:43 | ||
А такой вариант: [0,0,3,3,5,4,5],[7,6],[0,2,0] Чем хуже? Как определить "лучшесть", если возможно несколько одинаковых (примерно) вариантов? |
| Автор: Alex101 7.9.2004, 11:02 |
| Есть какая-то идея... Допустим, делим пополам: [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. К чему надо стремиться - к созданию максимального ряда, даже если окажется, что какие-то ряды будут состоять из одного числа? Задача все равно все еще плохо поставлена - непонятно, что является результатом... |
| Автор: Sardar 8.9.2004, 01:22 | ||||||||||
Тем что 5-0+1 = 6
Есть дорога, на ней стоят стаканчики. На каждом стаканчике есть отметки по которым замеряем наполненость стаканчика. Стаканчики рандомно заполненны. Количество стаканчиков конечно, но их очень много(представте сколько для вас лично "много"  ).Нужно пройтись по дороге и выставить разделяющие границы. В процессе работы со стаканчиками можно делать что угодно, но в конце они должны стоять на своих местах и иметь то количество жидкости, которое было в них изначально. Часть дороги со стаканчиками разделленной границами будем называть подрядом. У подряда есть ключевое свойство: разница между самым наполненным стаканчиком и самым не наполненным не должна превышать N. Основная цель: найти самые длинные ряды. Xороший результат: несколько длинных рядов и куча очень маленьких(2-3 стаканчика) Графически это выглядит так:
Мне кажется это должно встречатся графике(области с схожим цветом). Как то не получается описать задачу формально
Вот здесь остановился, как 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] - апострофы там где сохраненно смещение как возможного ряда. Где я ошибся?
Да я запарюсь проверять, проще пробежатся по ряду и разбить на подряды по принципу: число лежит в диапазоне :минимальное число(меняется по ходу просмотра) + максимальная разница:, тогда в этот ряд, иначе открываем следующий. Затем пробежатся по второму разу и сдвинуть границы. Есть варианты умнее? |
| Автор: Sined 8.9.2004, 08:17 | ||
| Пробуем Шаги 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 -- завершение произошло числом входящим в "диапазон" предыдущего ряда => все в предыдуший ряд. Подогнали и получили
З.Ы. Что я не написал 1) Если буффер не пуст и не выполнены у1(у1 надо изменить как : наибольшая разница у вновь пришедшего числа чисел в буффере и предыдущем ряду недопустимо большая) (у2 -- бред больного человека, но что-то типа него нужно) любое число заталкивается в буффер. Критерий начала новго ряда и запихивание всего буффера в старый такой: Если разница между последним подтвержденным числом старого ряда и первым символом буферв меньше разницы последнего числа в буффере и вновь пришедшего символа -- новый символ -- начало нового ряда, весь буффер предыдущий ряд, если нет, то наоборот). |