Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.58/12: Рейтинг темы: голосов - 12, средняя оценка - 4.58
SrgKord
47 / 29 / 2
Регистрация: 14.02.2013
Сообщений: 634
1

Поиск максимального элемента в массиве методом "разделяй и властвуй"

19.02.2014, 00:02. Просмотров 2265. Ответов 4
Метки нет (Все метки)

Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его элементов на предмет превышения значения одной переменной над значением другой, с последующей записью этого значения в последнюю переменную.
А задача стоит описать этот алгоритм с применением метода "разделяй и властвуй". Вот я и думаю, а что тут делить? Итак код в двух строчках.
На какие две "еще более простые задачи" можно разделить эту задачу?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.02.2014, 00:02
Ответы с готовыми решениями:

Методом "разделяй и властвуй" построить башни
Всем привет, последняя задачу которую нужно решить) Есть бесконечное...

Методом "разделяй и властвуй" посчитать задания
Тема больше не актуальна Всем привет, снова мучаюсь с задачей вот уже...

В каких случаях лучше использовать алгоритм "разделяй и властвуй"?
Подскажите, в каких случаях лучше использовать алгоритм разделяй и властвуй?...

Разделяй и властвуй: сумма произведений попарных элементов массивов
Всем привет. Есть задача. Дан массив А из 150 чисел, который начинается с 2 и...

Поиск максимального паросочетания в задаче "Испорченный паркет"
Привет всем! Прошу помощи. Есть задача "Испорченный паркет". Условие задачи...

4
Eldies
90 / 82 / 40
Регистрация: 06.02.2014
Сообщений: 122
19.02.2014, 00:27 2
Лучший ответ Сообщение было отмечено SrgKord как решение

Решение

Как вариант - разделить задачу на две задачи:
1) поиск максимума в первой половине массива
2) поиск максимума во второй половине массива
и сравнить найденное.
Метод применён)

Еще можно применить sqrt-декомпозицию, когда массив из N элементов разделяется на http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N} частей, максимум каждой части просчитывается заранее и где-нибудь хранится. При изменении какого-нибудь элемента массива, перерассчитывается максимум соответствующей части массива, а максимум во всем массиве можно теперь искать всего за http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N} операций.
1
SrgKord
47 / 29 / 2
Регистрация: 14.02.2013
Сообщений: 634
19.02.2014, 00:37  [ТС] 3
А ведь этот вариант у меня в голове неоднократно возникал, но я его отвергал, как слишком... плоский, что ли. Но тут, пожалуй, ни чего лучше и не сделаешь =)
0
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
20.02.2014, 13:45 4
Цитата Сообщение от SrgKord Посмотреть сообщение
Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его элементов на предмет превышения значения одной переменной над значением другой, с последующей записью этого значения в последнюю переменную.
А задача стоит описать этот алгоритм с применением метода "разделяй и властвуй". Вот я и думаю, а что тут делить? Итак код в двух строчках.
На какие две "еще более простые задачи" можно разделить эту задачу?
А этот массив случайно не обладает никакими свойствами ? Например, числа сначала возрастают, потом убывают, или еще какие свойства.
А то если это "обычный" массив с неизвестным поведением, то я не вижу как можно применить "разделяй и властвуй" с большим выигрышем.
Цитата Сообщение от Eldies Посмотреть сообщение
Еще можно применить sqrt-декомпозицию, когда массив из N элементов разделяется на http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N} частей, максимум каждой части просчитывается заранее и где-нибудь хранится. При изменении какого-нибудь элемента массива, перерассчитывается максимум соответствующей части массива, а максимум во всем массиве можно теперь искать всего за http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{N} операций.
Я тут почеркал на листочке и посмотрел разные описания. Я вижу, что sqrt (и аналогичные) декомпозиции хороши при долговременной работе с массивом при операциях для однотипных результатов (сумма/максимум/минимум), но я не могу увидеть реальный выигрыш при использовании такого метода разово.

Вот, например, возьмем массив размера 81 и разобьем его на sqrt(81) = 9 частей
в каждой части мы для поиска локального максимума мы сделаем 8 сравнений и от 1 до 8 присваиваний
аналогичный цифры для поиска глобального максимума
Итого получаем 8*9+8 = 80 сравнений и от 10 до 80 присваиваний. Аналогичные цифры при прямом поиске.

Направь мой взор дабы узрел я истину.
0
Eldies
90 / 82 / 40
Регистрация: 06.02.2014
Сообщений: 122
20.02.2014, 17:03 5
Цитата Сообщение от wingblack Посмотреть сообщение
Я тут почеркал на листочке и посмотрел разные описания. Я вижу, что sqrt (и аналогичные) декомпозиции хороши при долговременной работе с массивом при операциях для однотипных результатов (сумма/максимум/минимум), но я не могу увидеть реальный выигрыш при использовании такого метода разово.
При разовом поиске максимума никакого выигрыша действительно нет.
Не зная, какая конкретно задача у ТС, предложил sqrt-декомпозицию, как метод, который
1) является реализацией "разделяй и властвуй"
2) приводит к выигрышу на немаленьком классе задач
0
20.02.2014, 17:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.02.2014, 17:03

Поиск максимального элемента в двумерном массиве
Здравствуйте! Собственно вопрос - оптимальный алгоритм. Есть ли тут вообще...

Поиск и вывод строки по заданному шаблону (с использованием симоволов "?", "*", "+")
Добрый день Имею такое задание: необходимо написать программу, которая...

"Задача на поиск чего-либо в массиве"
Представим ситуацию, что надо, например, проверить массив на наличие в нем,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru