Первый из быстрых алгоритмов достаточно сложен, поэтому если вы запутаетесь в деталях, можете перейти сразу к следующему разделу, вы не слишком много потеряете при этом. Итак, алгоритм основан на следующем правиле:
Если нужно решить задачу размера п, следует рекурсивно решить две подзадачи размера приблизительно п/2, а затем объединить их решения в одно целое.
В данном случае мы имеем дело с массивом размера п, поэтому наиболее естественным способом разделения задачи на две подзадачи будет создание двух массивов приблизительно одинакового размера. Один из них мы назовем а, а другой — Ь.
Затем мы рекурсивно найдем подпоследовательности с максимальной суммой элементов в массивах а и Ь; одну из них назовем та, а другую — ть.
m.i mb
Соблазнительная мысль о том, что мы решили задачу, потому что подпоследовательность всего массива с максимальной суммой должна равняться либо та, либо mh> оказывается неправильной, потому что эта искомая подпоследовательность может и пересекать границу между а и Ь. Такую подпоследовательность мы назовем тс, поскольку она пересекает границу.
Итак, наш алгоритм «разделяй и властвуй» должен рекурсивно находить та и mh, после чего каким-то другим способом находить mL и сравнивать их между собой.
Этого описания почти достаточно для написания программы. Осталось лишь определить способ работы с массивами малого размера и способ вычисления тс. Первое сделать несложно: подпоследовательность с максимальной суммой для массива из одного элемента равна этому элементу, если он положителен, или нулю, если элемент отрицателен, а максимальная подпоследовательность пустого массива равна нулю. Для вычисления тс отметим, что его левая часть представляет собой максимальную подпоследовательность элементов, заканчивающуюся на границе а и b и простирающуюся в а, а правая часть — такую же подпоследовательность, лежащую в Ь. Собрав все это вместе, получим алгоритм 3 (листинг 8.4).
Опубликовал vovan666
April 17 2013 00:00:32 ·
0 Комментариев ·
5702 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
