| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Помогите |
| Автор: Kesh 16.9.2002, 17:12 |
| Есть такая задачка... Дается последовательность целых чисел... Из нее надо выбрать подпоследовательность с максимальной суммой и возможно меньшей длины... Алгоритм перебора всех подпоследовательностей не принимается, надо сделать, что-нить быстрое и гениальное... Я уверен, мы вместе это смогем... Так что пишите... :0) |
| Автор: podval 16.9.2002, 18:25 | ||
Эти два условия противоречат друг другу, так что сперва давай конкретизируем, что же все-таки нужно сделать. |
| Автор: FdX 16.9.2002, 23:07 |
| Да вроде смысл ясен. Если ты имел ввиду это: Имеется последовательность целых чисел. Требуется из нее выбрать последовательность определенной длины (меньшей длины исходной послед.), сумма элементов которой будет больше суммы ЛЮБОЙ другой последовательности (полученной из исходной) заданной длины (длина та же, что и у посл. с макс. суммой). Тогда все просто. Ищи n наибольших чисел и запоминай их порядковый номер в массиве. Или запоминай в массиве сами эти числа. Если напутал - извините. Колво всех возможных послед. заданной длины выражается очень большими числами. Формулу лень выводить. А таким образом ты получишь послед. с макс суммой. |
| Автор: Kesh 17.9.2002, 04:28 | ||
Ах, если бы все было так просто... :0( Играющую роль в формировании последовательности играет сумма элементов... Но при все при этом, звиняйте что сразу не сказал, подполедовательностью в данном случае называется не выборка эл-тов из последовательности, а группа следующих друг за другом элементов..., т.е. из последовательности [1,-1,0,5,6,-3,0,5,-2] нельзя выбрать подпоследовательность [-1,5,6,-3], а надо [-1,0,5,6,-3].... Думаем дальше... P.S. Я уже думал, может какое трай-дерево строить?.. |
| Автор: tserbis 19.9.2002, 00:40 |
| Ни у кого нет "Арсак. Программирование игр и головоломок"? По-моему, там я видел решение подобной задачи в один проход. Единственное, - не уверен, что было условие про минимальность длины... |
| Автор: FdX 19.9.2002, 23:26 |
| Ну тогда простым перебором последовательностей. Иначе вроде никак. Если тама по порядку, то пахать это бует довольно быстро. |
| Автор: Kesh 5.10.2002, 06:16 |
| Тут я подумал немного, и вот что пришло на ум... Можно сделать это в два пробега... Первый пробег: Наращиваем сумму по всем элементам и запоминаем тот элемент на котором она максимальна... Второй пробег(до максимума): Убираем из суммы элементы и запоминаем опять же максимум... Вот так вроде бы должно работать... Но есть ведь и однопроходный алгоритм... Мож кто знает... |
| Автор: Fantasist 9.10.2002, 12:14 |
 Я решал эту задачу два раза. Первый раз когда я был совсем маленький, тогда я вначале не понял, что надо в один проход, а когда узнал до решения не догадался. Второй раз пару лет назад - в один проход все правильно - тогда я еще удивился, что она так просто решилась. Сейчас решения не помню, но если не будет лень, придумаю снова. |
| Автор: Fantasist 9.10.2002, 12:40 |
| А ну да. Алгоритм простой. Правда, как podval заметил - условие минимальности длины странное: -1 -4 5 6 -2 -1 4 7 -3 2 и что отсюда выбрать? 5 6 -2 -1 4 7 или просто 5 6 или 4 7? А алгоритм таков: 1. Находим первое положительное число и начинаем добавлять в нашу последовательность все элементы по порядку, пока не встретиться отрицательное. 2. Нашли отрицательное запоминаем позицию где его нашли и начинаем добавлять все элементы по порядку в специальную переменну - отрицательную сумму, пока не произойдет следующее: отрицательная сумма стала больше положительной - все сбрасываем и возвращаемся к п.1 Либо, мы наткнулись на положительный элемент. В этом случае запоминаем еще один индекс и начинаем накапливать вторую положительную сумму пока не встретим отрицательный элемент. Теперь сравниваем вторую положительную сумму и отрицательную - если положительная больше включаем весь промежуток, если нет, то если первая положительная сумма больше второй - то мы нашли наш интервал, иначе вторая сумма становиться первой и начинаем искать промежуток с того индекса который мы запомнили вторым. Можно еще искать максимальный отрицателный элемент - если положительных не встретиться, то он будет искомым интервалом. |
| Автор: Alex101 10.10.2002, 06:29 |
| Вроде, это классическая задача на динамическое программирование... Посмотри алгоритм Бэлмана (поищи в сети - он должен быть) Ежели не найдешь, с делами разберусь - вышлю |
| Автор: Kesh 14.10.2002, 22:56 |
| Еще раз всем огромноое спасибо, дали пищу для размышлений... Alex 101: шли обязательно, мало ли что я сам накопаю?.. :0) |
| Автор: B0BAH 14.9.2005, 23:03 |
| Я очень долго парился,но когда узнал решение ОФИГЕЛ: sr:=0; smax:=0; for i:=0 to n do begin sr:=sr+a[i]; if sr<0 then sr:=0; if sr>smax then smax:=sr; end; writeln(smax); Приколите это ВСЕ! Работает 100% P.S Обещенного 3 года ждут!!!!!!!!!!!!!!!!!!!!!!!!!! |