Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
yol
10 / 10 / 0
Регистрация: 13.10.2012
Сообщений: 155
1

Массив с большинством

20.05.2013, 19:08. Просмотров 376. Ответов 4
Метки нет (Все метки)

Получил задания сравнить рандомизированный и линейный алгоритмы на массиве с большинством.
(Массив с большинством - это такой массив, где больше половины элементов имеют равные значения, т.е.: 3 2 5 3 3 9 1 3 2 3 3 3, здесь большинство элементов равны "3" ).

В инете усердно порылся, но никакой информации по "массиву с большинством" и алгоритмы обработки его - не нашел. (На руках есть книга, где описывается сложность рандомизированного алгоритма на основе данного массива, но про сложность линейного - нет никакой инфы).
Кто-что знает, поскидывайте всякой инфы по данному вопросу, мне будет полезно почитать.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.05.2013, 19:08
Ответы с готовыми решениями:

Вывести на печать массив X, массив Z, массив Y, произведение элементов массива X, упорядоченный массив Y
Вывести на печать массив X, массив Z, массив Y, произведение элементов массива X, упорядоченный...

Сформировать массив, который будет состоять из чисел, входящих как в массив A, так и в массив B
Задание: На основе исходных массивов A и B (n и m – рабочие размеры массивов) сформировать массив...

Массив: Преобразовать массив, прибавив к четным числам, входящим в массив, значение первого элемента.
Есть задача С клавиатуры вводятся элементы целочисленного массива размера N. Преобразовать его,...

Дан массив целых чисел а(12). Переписать в массив х четные, а в массив у нечетные элементы массива а
Помогите пожалуйста решить эту задачу. Массив a выводит на печать. Я пишу a mod 2 = 0 , а он мне 41...

Дан одномерный массив A из N элементов. Переписать положительные элементы массива в массив B, а отрицательные в массив C
Дан одномерный массив A из N элементов. Переписать положительные элементы массива в массив B, а...

4
Igor3D
1229 / 596 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
21.05.2013, 09:51 2
С большинством понятно, а что от Вас хотят - нет Определить что в массиве больше половины троек? Или каких чисел больше половины?
0
yol
10 / 10 / 0
Регистрация: 13.10.2012
Сообщений: 155
21.05.2013, 10:14  [ТС] 3
Цитата Сообщение от Igor3D Посмотреть сообщение
С большинством понятно, а что от Вас хотят - нет Определить что в массиве больше половины троек? Или каких чисел больше половины?
Я имел ввиду, что мне надо оценить/сравнить сложность двух алгоритмов обработки массива с большинством. Алгоритмы обработки:
1) Рандомизированный алгоритм (я уже нашел его сложность - это t<2(n-1));
2) Линейный алгоритм (по данному алгоритму, я к сожалению, ни какой информации не нашел).

Добавлено через 2 минуты
Вот небольшая информацию по рандомизированному алгоритму:
Кликните здесь для просмотра всего текста
Массив x1, x2, ..., xn назовем массивом, содержащим большинство, если больше половины его элементов имеют равные значения. Пусть над элементами массивов разрешена операция проверки равенства двух элементов, будем называть эту операцию сравнением. Пусть для данного массива, содержащего большинство, требуется найти i, 1<=i<=n, такое, что значение xi принадлежит большинству значений элементов x1, x2, ..., xn. Один из возможных рандомизированных алгоритмов решения этой задачи состоит в том, что i выбирается случайно (распределение вероятностей равномерного), а затем проверяется, удовлетворяет ли xi поставленному условию, - сравнений на эту проверку уйдет не более n-1. Если xi не подходит, то все повторяется. Сложность в среднем по числу сравнений этого алгоритма не превосходит 2(n-1). В самом деле, пространство всех сценариев разлагается на два события: первая попытка найти нужное i оказывается удачной, и соответственно, эта попытка оказывается неудачной. По формуле полного математического ожидания имеем для искомого среднего a: a<=p(n-1)+(1-p)(a+n-1).
Отсюда a<=1/p(n-1)<2(n-1).
0
Igor3D
1229 / 596 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
21.05.2013, 17:38 4
Ну "линейный" алгоритм наверное выглядит так: заводим массив счетчиков (изначально c нулевыми значениями). Идем по массииву, от каждого элемента "бежим назад" сравнивая его с предыдущим. Если равны - устаналтваем счетчик в предыдущее + 1, иначе просто в 1. Напр

1, 3, 2, 3, 1, 3, 3, 3 // исходный массив
0, 0. 0. 0, 0, 0, 0, 0 // начальные счетчики
1, 0. 0. 0, 0, 0, 0, 0 // счетчики на шаге 1
1, 1. 0. 0, 0, 0, 0, 0 // счетчики на шаге 2
1, 1. 1. 0, 0, 0, 0, 0 // счетчики на шаге 3
1, 1. 1. 2, 0, 0, 0, 0 // счетчики на шаге 4
1, 1. 1. 2, 2, 0, 0, 0 // счетчики на шаге 5
1, 1. 1. 2, 2, 3, 0, 0 // счетчики на шаге 6
и.т.д.

Как только счетчик превысит 4 (половина) - найдено. Как оценить затратность - не знаю

А вообще конечно - от жизни далековато. Это делается ассоциативным контейнером (напр std::map) в неск строк
0
yol
10 / 10 / 0
Регистрация: 13.10.2012
Сообщений: 155
27.05.2013, 19:02  [ТС] 5
Цитата Сообщение от Igor3D Посмотреть сообщение
Ну "линейный" алгоритм наверное выглядит так: заводим массив счетчиков (изначально c нулевыми значениями). Идем по массииву, от каждого элемента "бежим назад" сравнивая его с предыдущим. Если равны - устаналтваем счетчик в предыдущее + 1, иначе просто в 1. Напр

1, 3, 2, 3, 1, 3, 3, 3 // исходный массив
0, 0. 0. 0, 0, 0, 0, 0 // начальные счетчики
1, 0. 0. 0, 0, 0, 0, 0 // счетчики на шаге 1
1, 1. 0. 0, 0, 0, 0, 0 // счетчики на шаге 2
1, 1. 1. 0, 0, 0, 0, 0 // счетчики на шаге 3
1, 1. 1. 2, 0, 0, 0, 0 // счетчики на шаге 4
1, 1. 1. 2, 2, 0, 0, 0 // счетчики на шаге 5
1, 1. 1. 2, 2, 3, 0, 0 // счетчики на шаге 6
и.т.д.

Как только счетчик превысит 4 (половина) - найдено. Как оценить затратность - не знаю

А вообще конечно - от жизни далековато. Это делается ассоциативным контейнером (напр std::map) в неск строк
Да уж... Вообщем, под "линейностью" подразумевалось его сложность, т.е. линейная сложность данного алгоритма. У меня есть предположение, что сложность в среднем этого линейного алгоритма можно определить через метод "Отсечения и поиска".
0
27.05.2013, 19:02
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.05.2013, 19:02

Сформировать массив C, который будет состоять из чисел, которые одновременно входят как в массив A, так и в массив B
Есть задание :На основе исходных массивов A и B (n и m – рабочие размеры массивов) сформировать...

Массив: Отсортировать полученный массив 3 способами: по строкам, по столбцам( возр.), 3) и весь массив
Помогите, пожалуйста ,решить задачу. Очень нужно. Задан массив (4*6). Элементы задаются по...

Массив: Получить новый массив P, состоящую из чисел в интервале (a,b), которые не входят в массив H...
Помогите с заданием, пожалуйста :Написать программу, которая формирует новую последовательность P,...


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

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

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