мажорирующий элемент

Тема в разделе "Общие вопросы по С и С++", создана пользователем kyCa4ka, 15 ноя 2006.

Статус темы:
Закрыта.
  1. kyCa4ka

    kyCa4ka Гость

    привет всем. помогите пожалуйста кто может с задачкой. буду рад любой помощи..

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

    зы. в ответ предлагаю помощь по веб-дизайну.
     
  2. LAW

    LAW Гость

    Ты алгоритм-то сего действа представляешь?
     
  3. Dmirys

    Dmirys Гость

    Ну а, например, так:
    1. Отсортировать массив
    2. Выполнить примерно следующую схему:

    Код (Text):
    int arr[] = {1, 1, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 7, 8, 9, 9};

    for (int i = 0, count = 1; i < sizeof(arr) - 1; i++) {
    if (arr[i] == arr[i + 1]) {
    if (++count > sizeof(arr) / (2 * sizeof(int))) {
    // Здесь вывод сообщения, что элемент найден и равен arr[i]
    break;
    }

    continue;
    } else {
    count = 1;
    }

    }
    Поиск мажорирующего элемента имеет смысл для массива минимум из трех элементов.
     
  4. Kmet

    Kmet Well-Known Member

    Регистрация:
    25 май 2006
    Сообщения:
    1.017
    Симпатии:
    1
    Для: Dmirys
    От задачек такого родa обычно требуется сложность О(N)

    мне почему то казалось что sizeof возвращает размер в байтах
     
  5. kyCa4ka

    kyCa4ka Гость

    <!--QuoteBegin-Kmet+17:11:2006, 10:49 -->
    <span class="vbquote">(Kmet @ 17:11:2006, 10:49 )</span><!--QuoteEBegin-->От задачек такого родa обычно требуется сложность О(N)
    [snapback]48080" rel="nofollow" target="_blank[/snapback]​
    [/quote]
    если так всё просто то помогите а млин осталось только эта последняя задачка вот у мя есть исходник на паскале:

    for i:=1 to N-1 do
    for j:=2 to N do
    if A>A[j]
    then
    begin
    tmp:=A;
    A:=A[j];
    A[j]:=tmp
    end;
    Count:=1; { Количество одинаковых элементов }
    for i:=2 to N do
    if A<>A[i-1]
    then if Count > N div 2
    then
    begin
    writeln('Mажорирующий элемент ',A[i-1]); { Распечатать } Halt { Стоп }
    end;
    else Count:=0 { Начать подсчет для следующего элемента}
    else Count:=Count+1; { Увеличить счетчик для текущего элемента }
     
  6. Kmet

    Kmet Well-Known Member

    Регистрация:
    25 май 2006
    Сообщения:
    1.017
    Симпатии:
    1
    Кто сказал что просто? В общем случае все как раз наоборот. Все зависит от диапазона элемнентов которые могут встретиться в массиве. И для общего случае скореее всего потребуется написание каго-нибудь хитрого хеш словаря с поддержкой колизий.=)

    Если диапон ограничен тогда действительно не сложно=)
    Создаем массив который будет хранить сколько раз элемент встречался,и индексируем его(этот массив) самим же элементом. Таким образом можно обойтись без сортироки
     
  7. ZZmiy

    ZZmiy Гость

    можно, наример, std::map<int,int> - чем плох? :unsure:
     
  8. European

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    Судя по примеру на Паскале, на сложность O(N) можно забить
     
  9. Kmet

    Kmet Well-Known Member

    Регистрация:
    25 май 2006
    Сообщения:
    1.017
    Симпатии:
    1
    Я говорил о хитром хеш словаре с подержкой коллизий
    std::map и не хитрый и не хеш и коллизии тоже естестно не обробатывает. Хотя конечно на числовом ряду проку от хештрование не будет, это так для общности.

    Из stl можно взять std::multimap или hash_map, но этот контейнер еще не вошел в стандарт
     
  10. kyCa4ka

    kyCa4ka Гость

    так может кто исходником помочь или нет? :huh: или хотяб частично
     
  11. zugr

    zugr Гость

    Вот примерный алгоритм (JavaScript):
    Код (Text):
    function Major(arr)
    {
    var ss=new Object();
    var n=arr.length;
    for(var i in arr) {
    var v=arr[i];
    if (ss[v]==null) {
    ss[v]=Math.round(n/2);
    } else if ( i <= ss[v] ) {
    if (n==++ss[v])
    return v;
    }
    }
    return null;
    }

    arr=new Array(1,2,3,4,9,1,1,1,1,5);
    var rez=Major(arr);
    if (null==rez)
    print("Array not have major");
    else
    print("Major element is "+rez);
    здесь ss - и есть map счётчиков, только мажорный элемент может довести его до N.
    Почему считаем до N:
    1. Это позволит закончить поиск мажорного элемента до завершения просмотра всего массива;
    2. Это позволяет игнорировать элементы, которые уже не станут мажорными даже если все оставшиеся непросмотренные будут такимиже.

    Сложность алгоритма в худшем случае O(N*log(N))

    Думаю на Си перевести можно :)
     
  12. kyCa4ka

    kyCa4ka Гость

    а если JavaScript незнаю :)
     
  13. zugr

    zugr Гость

    Это плохо, но и не страшно :)
    Начинай переводить на Си с того что понимаешь, пиши если что не выходит, помогут ;)
     
  14. kyCa4ka

    kyCa4ka Гость

    Код (Text):
    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++;
    }
     
  15. kyCa4ka

    kyCa4ka Гость

    помогите пожалуйста кто нибудь дописать алгоритм :)
     
  16. zugr

    zugr Гость

    :D Всё просто:
    Код (Text):
    #include <iostream>
    #include <vecotr>
    #include <map>

    typedef int el;
    typedef std::vector<el> Array;
    typedef std::map<el,int> Object;

    //function Major(arr)
    el* Major(Array& arr)
    //{
    {
    //var ss=new Object();
    Object ss;
    //var n=arr.length;
    int n=arr.size();
    //for(var i in arr) {
    for(int i=0; i!=arr.size(); i++) {
    //var v=arr[i];
    el v=arr[i];
    //if (ss[v]==null) {
    if ( ss.find(v) == ss.end() ) {
    // ss[v]=Math.round(n/2);
    ss.insert(Object::value_type(v,int(n/2)));
    //} else if ( i <= ss[v] ) {
    } else if ( i <= ss.find(v).second ) {
    //if (n==++ss[v])
    if (n == ++(ss.find(v).second) )
    //return v;
    return arr+i; // не v, т.к. функция возвращает указатель на элемент масива
    //}
    }
    //}
    }
    //return null;
    return null;
    //}
    }


    void main(void)
    {
    // arr=new Array(1,2,3,4,9,1,1,1,1,5);
    el _arr[]={1,2,3,4,9,1,1,1,1,5}
    Array arr(_arr,_arr+sizeof(_arr)/sizeof(el));
    // var rez=Major(arr);
    el* rez = Major(arr);
    //if (null==rez)
    if (null == rez)
    //print("Array not have major");
    std::cout << "Array not have major" << std::endl;
    //else
    else
    //print("Major element is "+rez);
    std::cout << "Major element is " << *rez << std::endl;
    }
    Но я не отлаживал, так что баги шукай, наверняка есть. :(
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей