Форум » Динамическое программирование » 18. Задачи на последовательность. » Ответить

18. Задачи на последовательность.

alspay: День добрый! Задачи на последовательность вещественных чисел. Возник вопрос: Если по условию задачи в файле только положительные числа, проблем нет - стандартный алгоритм нахождения максимальной (минимальной) суммы подпоследовательности. Если по условию задачи в файле как положительные так и отрицательные числа - обработка таких последовательностей для нахождения, например, максимальной суммы становится проблемой. Например, интересует подпоследовательность, в которой разница между соседними элементами не менее 10. Найти максимальную сумму. 1) 10 20 30 40 - проблем нет, стандартный алгоритм работает, 2) -10 -20 -30 - 40 - проблем нет, стандартный алгоритм, 3) -100 -50 10 20 30 -10 -20 10 40 - 10 - 20 - в таких последовательностях возникает проблема - вначале последовательности идут отрицательные числа. Максимально возможная сумма - 80 (10 20 30 -10 -20 10 40). НО, отрицательные числа, стоящие в начале последовательности, не позволят нам получить этот результат. значит нам надо сохранять всю найденную последовательность и потом ее обрабатывать отдельно, а это уже совсем другая сложность задачи.

Ответов - 16, стр: 1 2 All

alspay: 4) -40 - 30 -20 -10 - такая же проблема как и в 3) - максимальная сумма -30, но начало последовательности даст нам другой результат - 100

Поляков:

alspay: Последовательность, в которой не работает: -20 -40 -10 -20 -10 -20 Результат -10, но максимальная сумма нескольких элементов (2 и более) -30 Вторая последовательность: -10 10 -10 10 -10 10 -10 Результат 10, а должен быть 0.


Поляков: alspay пишет: максимальная сумма нескольких элементов (2 и более) Нигде не написано про 2 и более.

alspay: Поляков пишет: Нигде не написано про 2 и более. Сумма может состоять из одного элемента?

Поляков: alspay пишет: Сумма может состоять из одного элемента? Да, конечно.

alspay: Константин Юрьевич, возвращаясь к сложности заданий на последовательности. В 18 задании в Вашей подборке встречаются не только последовательности на соседние элементы, но и задания в которых надо проанализировать элементы последовательности, номера которых отличаются не более (не менее) чем на К элементов, т.е. это бывшие 27 задания. Алгоритмы на этот тип задач не вызывают особых вопросов, но ведь 27 относится к высокому уровню сложности, а 18 задание это повышенный уровень.

Поляков: alspay пишет: Алгоритмы на этот тип задач не вызывают особых вопросов, но ведь 27 относится к высокому уровню сложности, а 18 задание это повышенный уровень. Как говорил Суворов, "Тяжело в учении, ...".

alspay: alspay пишет: цитата: Сумма может состоять из одного элемента? Да, конечно. хм... если мы ищем последовательность элементов, в которой мы проверяем сам элемент (например, интересуют четные числа), тогда мы можем сказать, что последовательность может состоять из одного элемента... но в задачи стоит условие - разница между двумя соседними элементами, т.е. минимальное количество элементов в последовательности должна состоять из 2 элементов, а значит и сумма должна состоять из минимум 2 элементов.

Поляков: alspay пишет: значит и сумма должна состоять из минимум 2 элементов. Такого нет в условии. По умолчанию всегда предполагается, что последовательность может состоять из 1+ элементов. По крайней мере, в этой задаче условие именно такое. Можно решать и какие-то другие задачи, но тогда нужно особо оговаривать, что длина последовательности не менее X. В этом случае решение будет сложнее.

Светлана111: Касательно задачи 3165 Немного не понимаю почему в ответе 3165 = 104 . Могу только предположить, что она получается как максимальное из столбца B. если пользоваться формулой , приведенной выше для столбца B =ЕСЛИ(И(ABS(A2-A1)<20;A2+B1>A2);B1+A2;A2).Как раз там и будет в ячейке B704 =104.38. Я не знаю каким способом решал автор задачи, НО даже , если пользоваться предложенной выше формулой получается казус , во-первых 104,38-это промежуточная сумма в последовательности, во-вторых - последовательности, применяя эту формулу, получается неверные(красным выделены числа, не включенные в последовательность, хотя они должны быть там). По итогу, я полагаю, ответ должен быть 91. Пользовалась формулой =ЕСЛИ(ABS(A2-A1)<20;B1+A2;A2) и максимальное искала не в столбце B, тк промежуточные суммы в последовательностях могут быть больше итоговой суммы последовательности, а отдельно делала вывод итоговой суммы каждой последовательности и там уже...,. Касательно задачи 3194 проблема та же - ответ 33 , хотя , я думаю, дб 31 - полагаю, что 33 это промежуточная сумма последовательности Возможно, я в корне не права в своих рассуждениях. Прошу дать объяснение , что не так . Спасибо,за то что прочитали мой опус

Поляков: Светлана111 пишет:во-первых 104,38-это промежуточная сумма в последовательности Если мы получили эту сумму и она максимальна, значит нужная нам последовательность закончилась на этой строке.красным выделены числа, не включенные в последовательность, хотя они должны быть там Почему вы считаете, что они должны быть там?

Светлана111: Спасибо за ответ. По поводу максимального разобралась- не поняла ТУ к задаче. Полагала, что нужно найти максимальное из финальных сумм существующих последовательностей, оказывается все гораздо проще...те. вопрос к 3194 снимается НО вопрос по 3165 остался(почему ответ 104), все таки вот эти числа в " красном" должны быть в последовательности, тк разбег между ними меньше 20, соответственно и максимальную считает неверно, тк они не учтены.Это опять же , если использовать, предложенную Вами выше формулу.Кстати, я не совсем поняла, зачем там второе условие по И, которое как раз и дает вот такой результат.

Поляков: Светлана111 пишет: должны быть в последовательности, тк разбег между ними меньше 20 Мы вольны как включать, так и не включать их в последовательность. Если они увеличивают сумму, то включаем. Если не увеличивают - не включаем. зачем там второе условие по И Как раз за этим. Чтобы найти максимальную возможную сумму.

Светлана111: Поляков пишет: Мы вольны как включать, так и не включать их в последовательность. Если они увеличивают сумму, то включаем. Если не увеличивают - не включаем. Спасибо. Я просто неверно изначально поняла суть задачи. Зачем-то усложнила условия, в первую очередь сделав упор на формирование последовательностей,, удовлетворяющих условию, а не на рассмотрение сумм, такая "сама себе Буратино". Всю голову сломала, почему так..... Еще раз спасибо.!



полная версия страницы