Автор | Сообщение |
|
Отправлено: 15.01.21 09:21. Заголовок: 18. Задачи на последовательность.
День добрый! Задачи на последовательность вещественных чисел. Возник вопрос: Если по условию задачи в файле только положительные числа, проблем нет - стандартный алгоритм нахождения максимальной (минимальной) суммы подпоследовательности. Если по условию задачи в файле как положительные так и отрицательные числа - обработка таких последовательностей для нахождения, например, максимальной суммы становится проблемой. Например, интересует подпоследовательность, в которой разница между соседними элементами не менее 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
[только новые]
|
|
|
Отправлено: 15.01.21 09:26. Заголовок: 4) -40 - 30 -20 -10 ..
4) -40 - 30 -20 -10 - такая же проблема как и в 3) - максимальная сумма -30, но начало последовательности даст нам другой результат - 100
|
|
|
|
| Администратор
|
Сообщение: 2316
|
|
Отправлено: 15.01.21 11:23. Заголовок: https://i.ibb.co/tsn..
|
|
|
|
Отправлено: 21.01.21 09:28. Заголовок: Последовательность, ..
Последовательность, в которой не работает: -20 -40 -10 -20 -10 -20 Результат -10, но максимальная сумма нескольких элементов (2 и более) -30 Вторая последовательность: -10 10 -10 10 -10 10 -10 Результат 10, а должен быть 0.
|
|
|
|
| Администратор
|
Сообщение: 2338
|
|
Отправлено: 21.01.21 23:51. Заголовок: alspay пишет: максим..
alspay пишет: цитата: | максимальная сумма нескольких элементов (2 и более) |
|
Нигде не написано про 2 и более.
|
|
|
|
Отправлено: 22.01.21 06:17. Заголовок: Поляков пишет: Нигд..
Поляков пишет: цитата: | Нигде не написано про 2 и более. |
| Сумма может состоять из одного элемента?
|
|
|
|
| Администратор
|
Сообщение: 2341
|
|
Отправлено: 22.01.21 09:35. Заголовок: alspay пишет: Сумма ..
alspay пишет: цитата: | Сумма может состоять из одного элемента? |
|
Да, конечно.
|
|
|
|
Отправлено: 21.01.21 09:39. Заголовок: Константин Юрьевич, ..
Константин Юрьевич, возвращаясь к сложности заданий на последовательности. В 18 задании в Вашей подборке встречаются не только последовательности на соседние элементы, но и задания в которых надо проанализировать элементы последовательности, номера которых отличаются не более (не менее) чем на К элементов, т.е. это бывшие 27 задания. Алгоритмы на этот тип задач не вызывают особых вопросов, но ведь 27 относится к высокому уровню сложности, а 18 задание это повышенный уровень.
|
|
|
|
| Администратор
|
Сообщение: 2339
|
|
Отправлено: 21.01.21 23:52. Заголовок: alspay пишет: Алгори..
alspay пишет: цитата: | Алгоритмы на этот тип задач не вызывают особых вопросов, но ведь 27 относится к высокому уровню сложности, а 18 задание это повышенный уровень. |
|
Как говорил Суворов, "Тяжело в учении, ...".
|
|
|
|
Отправлено: 25.01.21 08:15. Заголовок: alspay пишет: цитат..
цитата: | alspay пишет: цитата: Сумма может состоять из одного элемента? Да, конечно. |
| хм... если мы ищем последовательность элементов, в которой мы проверяем сам элемент (например, интересуют четные числа), тогда мы можем сказать, что последовательность может состоять из одного элемента... но в задачи стоит условие - разница между двумя соседними элементами, т.е. минимальное количество элементов в последовательности должна состоять из 2 элементов, а значит и сумма должна состоять из минимум 2 элементов.
|
|
|
|
| Администратор
|
Сообщение: 2346
|
|
Отправлено: 25.01.21 09:24. Заголовок: alspay пишет: значит..
alspay пишет: цитата: | значит и сумма должна состоять из минимум 2 элементов. |
|
Такого нет в условии. По умолчанию всегда предполагается, что последовательность может состоять из 1+ элементов. По крайней мере, в этой задаче условие именно такое. Можно решать и какие-то другие задачи, но тогда нужно особо оговаривать, что длина последовательности не менее X. В этом случае решение будет сложнее.
|
|
|
|
Отправлено: 29.01.21 22:10. Заголовок: 3165,3194
Касательно задачи 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 это промежуточная сумма последовательности Возможно, я в корне не права в своих рассуждениях. Прошу дать объяснение , что не так . Спасибо,за то что прочитали мой опус
|
|
|
|
|
| Администратор
|
Сообщение: 2368
|
|
Отправлено: 29.01.21 23:10. Заголовок: Светлана111 пишет:во..
Светлана111 пишет: цитата: | во-первых 104,38-это промежуточная сумма в последовательности |
|
Если мы получили эту сумму и она максимальна, значит нужная нам последовательность закончилась на этой строке. цитата: | красным выделены числа, не включенные в последовательность, хотя они должны быть там |
|
Почему вы считаете, что они должны быть там?
|
|
|
|
Отправлено: 30.01.21 10:48. Заголовок: Спасибо за ответ. По..
Спасибо за ответ. По поводу максимального разобралась- не поняла ТУ к задаче. Полагала, что нужно найти максимальное из финальных сумм существующих последовательностей, оказывается все гораздо проще...те. вопрос к 3194 снимается НО вопрос по 3165 остался(почему ответ 104), все таки вот эти числа в " красном" должны быть в последовательности, тк разбег между ними меньше 20, соответственно и максимальную считает неверно, тк они не учтены.Это опять же , если использовать, предложенную Вами выше формулу.Кстати, я не совсем поняла, зачем там второе условие по И, которое как раз и дает вот такой результат.
|
|
|
|
| Администратор
|
Сообщение: 2370
|
|
Отправлено: 30.01.21 16:50. Заголовок: Светлана111 пишет: ..
Светлана111 пишет: цитата: | должны быть в последовательности, тк разбег между ними меньше 20 |
|
Мы вольны как включать, так и не включать их в последовательность. Если они увеличивают сумму, то включаем. Если не увеличивают - не включаем. цитата: | зачем там второе условие по И |
|
Как раз за этим. Чтобы найти максимальную возможную сумму.
|
|
|
|
Отправлено: 30.01.21 20:12. Заголовок: Поляков пишет: Мы в..
Поляков пишет: цитата: | Мы вольны как включать, так и не включать их в последовательность. Если они увеличивают сумму, то включаем. Если не увеличивают - не включаем. |
| Спасибо. Я просто неверно изначально поняла суть задачи. Зачем-то усложнила условия, в первую очередь сделав упор на формирование последовательностей,, удовлетворяющих условию, а не на рассмотрение сумм, такая "сама себе Буратино". Всю голову сломала, почему так..... Еще раз спасибо.!
|
|
|
Ответов - 16
, стр:
1
2
All
[только новые]
|
|