Ассоциативные алгебры

kukina_eg


Задачи и незадачи


Previous Entry Share Next Entry
Алгоритм Боера-Мура
Ассоциативные алгебры
kukina_eg
Задача сегодня алгоритмическая. Иногда ее предлагают кандидатам для поступления в Яндекс. А я ее недавно разбирала со студентами на спец.курсе.

Задача. На вход подают поток чисел. Каждое число потока можно обрабатывать ровно один раз в связи с ограниченнностью памяти (дополнительной памяти можно использовать О(1)). Про поток заранее известно, что в нем будет n элементов, а один из элементов встретится больше, чем n/2 раз. Предложите алгоритм нахождения этого популярного числа.

Решение. Решение придумала не самостоятельно. Мне вобще кажется, что это -- задача на начитанность, знаешь ты этот алгоритм или нет. Так часто бывает на собеседованиях, на экзаменах. Алгоритм называется "Алгоритмом Боера-Мура".

Алгоритм такой:
1. Поступившее первое число назначаем "претендентом". Счетчик =1.
2. Увеличиваем счетчик на один, если поступает число, совпадающее с "претендентом" и уменьшаем на 1, если не совпадает. Так делаем, пока счетчик не станет =0 или не закончится поток.
3. Если после какого-то шага счетчик стал =0, следующим шагом выполняем шаг 1.

4. То число, которое является "претендентом" в момент окончания потока, и есть искомый популярный элемент.

Алгоритм простой и ясный. Одно не понятно, почему же он дает именно то, что надо?
Докажем это.

Представьте себе пиратский корабль. Капитан разделил добычу и каждому пирату на лбу написал число, сколько ему досталось денег. (Причем, какое-то число встречается больше, чем у половины команды -- назовем это число "нормальная доля").

И вот подписанные пираты ходят по кораблю. Если встречаются 2 пирата, у которых на лбу разные надписи, им это, естественно, не нравится! Дуэль -- пираты убивают друг друга.

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

А теперь внимательно посмотрим на наш алгоритм. Пусть Капитан пиратов выдает награбленные деньги потоком. Сначала первому помощнику, потом второму, потом третьему и т.д. Сначала "претендентом" является первый помощник. А наш счетчик считает, сколько на борту живых людей с надписью на лбу как у первого помощника.
Если все люди с надписью как у первого помощника, вымерли, то следующий, получающий деньги, будет назван "претендентом".
В конце с ненулевым счетчиком останется тот, у кого на лбу написано наше "популярное число".

  • 1
И тут ещё можно заметить, что этот алгоритм на самом деле про что-то другое. Не про эту задачу.

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

Может быть ещё и поэтому до него сложно догадаться.

По-моему, есть несколько алгоритмов придуманных Боером и Муром для несколько разных задач.

В нашей задаче как раз условие, что каких-то символов больше половины.

Мне кажется, алгоритм придумать не так сложно, а вот доказать что он корректен -- уже сложнее. По самому виду алгоритма не очень понятно, почему он дает правильный ответ.

Все три человека, включая меня и вас, которых я знаю, не решили эту задачу. Однако зная алгоритм, не сложно понять, что он верный. В голове выстраиваются в точности приведённые вами рассуждениями.

Поэтому утверждение о том, что доказать корректность алгоритма в данном случае сложнее, чем придумать его мне кажется ложным.

Но попытаюсь объяснить, что я имел в виду в предыдущем комментарии. В более простых задачках на динамику, где надо по части данных что-то понимать а потом рекуррентно переходить к следующему шагу, там обычно в этой части выполняется всё то же самое, что и во всех данных. Самый простой пример - поиск максимума. Каждое промежуточное решение является именно максимумом для обработанной части данных. А тут промежуточное решение является непойми чем, что не удивительно, ведь любом начальном куске данный условие про то, что каких-то чисел больше половины не выполняется.

В этом и состоит сложность. Как эту задачу решать, я не знаю, поскольку не решил, но могу предположить, что следовало именно осознать сформулированную выше сложность на частичных условиях и в решении пытаться под неё адаптироваться. Хотя, фиг его знает. Дотумкивание до решения - процесс тёмный.

>Все три человека, включая меня и вас, которых я знаю, не решили эту задачу.

Правильно будет сказать, что я нагуглила раньше, чем решила. Студент у меня на спецкурсе решил.

Дотумкивание -- действительно, процесс очень темный.

  • 1
?

Log in