VPF::мажорирующий элемент - Форум программистов

_ky

Дата 29.11.2006, 23:06 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 29.11.2006

Репутация: нет
Всего: нет

Вот задачка почти решена тока с сортировкой осталось разобраться..

Мажорирующим элементом в массиве A[1..N] будем называть элемент, встречающийся в массиве более N/2 раз. Легко заметить, что в массиве может быть не более одного мажорирующего элемента. Например, мас-сив 3, 3. 4, 2, 4, 4, 2, 4, 4 имеет мажорирующий элемент 4, тогда как в массиве 3, 3, 4, 2, 4, 4, 2, 4 мажорирующего элемента нет. Необходимо определить, есть ли в массиве мажорирующий элемент, и если есть, то какой.

Код


int array[N];

помогите ПОЖАЛУЙСТА мне здесь с сортировкой далее всё вроде правильнл..

int count =0, i =0;
int maz_el;

//
while( i < N-1 ){
maz_el = array[i];
if( array[i] == array [i+1] )
count++;
else
if( count>N/2 ){
//есть маж. эл. maz_el;
else
count = 0;
}
i++;
}

Void

Дата 29.11.2006, 23:26 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173

Эта задача решается в константной памяти за линейное время безо всякой сортировки.
(Алголист)
Но если требуется (читай «требует преподаватель») всё-таки использовать сортировку, то на том же Алголисте алгоритмов завались, всяких и разных.

Добавлено @ 23:28
Прошу прощения, упустил из виду, что мажорирующий элемент может и не присутствовать. Тогда несколько сложнее.
Ну вот они, сортировки.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

_ky

Дата 30.11.2006, 16:11 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 29.11.2006

Репутация: нет
Всего: нет

Void Пасиба за полезную инфу!

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »