Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет Oleg Izhvanov ([info]izh) в [info]programming
@ 2007-06-24 19:27:00

Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Простая задачка (с красивым решением)
Имеется последовательность из N объектов,
про любые два из которых можно сказать только
равны они или нет. Известно, что некоторого
объекта в последовательности больше половины.
Придумать алгоритм поиска этого объекта,
который бы завершался за один проход по
последовательности и использовал фиксированный
(то есть не зависящий от N) объем памяти.

Комменты скринятся.

Пояснение:

Понятно, что количество бит, при помощи которых
можно закодировать число N зависит от N, но
конкретно этой зависимостью можно пренебречь.
Также понятно, что от размера объекта зависит
объем используемой памяти. Этой зависимостью можно
также пренебречь. Существенно, чтобы количество
используемой памяти не зависело от количества
элементов в последовательности.

Решение (выделить мышкой):

Одно из возможных решений основывается на том
интересном факте, что из последовательности
можно выкинуть 3 произвольных попарно неравных
элемента. При этом количество искомых элементов
по прежнему будет больше половины в уменьшенной
последовательности. Другое решение (более простое),
предложенное Димой Калединым, также использует 
индукцию. Понять, как именно, предоставляется 
читателю в качестве упражнения.

Для простоты в решении рассматривается массив из
целых чисел. Алгоритмы, впрочем, будут работать для
любых объектов.

Мой вариант решения:

int find_most_repeatable(int *arr, size_t size)
{
    unsigned int        i;
    int                 a, b = 0, e, answer_a, answer_b, answer;

    answer_a = arr[0];
    a = 1;
    
    for (i = 1; i < size; i ++)
    {
        e = arr[i];
    
        if (answer_a == e && a > 0)
            a ++;
        else if (answer_b == e && b > 0)
            b ++;
        else
        {
            if (a == 0)
            {
                answer_a = e;
                a = 1;
                continue;
            }
            else if (b == 0)
            {
                answer_b = e;
                b = 1;
                continue;
            }

            a --; b --;
        }
    }

    if (a >= b)
        answer = answer_a;
    else
        answer = answer_b;
    
    return answer;
}

Вариант Димы Каледина (исправленный):

int find_most_repeatable2(int *arr, size_t size)
{
    unsigned int        i;
    int                 answer, e, c;
    
    answer = arr[0];
    c = 0; 
    for (i = 1; i < size; i ++)
    {
        e = arr[i];

        if (answer == e)
        {
            c ++;
            if (c <= 0)
                c ++;
        }
        else if (c >= 0)
            c --;

        if (c < 0)
            answer = e;
    }

    return answer;
}



(Читать комментарии)

Добавить комментарий:

Как:
(комментарий будет скрыт)
(комментарий будет скрыт)
(комментарий будет скрыт)
имя пользователя:    
Вы должны предварительно войти в LiveJournal.com
 
E-mail для ответов: 
Вы сможете оставлять комментарии, даже если не введете e-mail.
Но вы не сможете получать уведомления об ответах на ваши комментарии!
Внимание: на указанный адрес будет выслано подтверждение.
(комментарий будет скрыт)
Тема:
Сообщение: