Ищем знаменитость

[vak]

Купил сборник алгоритмических головоломок, штудирую, получаю удовольствие. Вот задачка, к примеру: найти знаменитость на вечеринке. Определим знаменитость как персону, которую все знают, но она не знает никого. Представьте, что вы попали на тусовку, и вам надо найти среди присутствующих эту знаменитость. Вы можете задавать люди вопрос: "Знаете ли вы этого человека?", и показывать на кого-нибудь. Как организовать эффективный поиск?

Оказывается, есть простой алгоритм.

1. Составляете список всех присутствующих, среди них есть и искомая знаменитость.

2. Подходите к кому-нибудь (обозначим его A) и спрашиваете, знает ли он соседа (обозначим его B). Он отвечает либо да, либо нет. Если да - вычёркиваете A из списка. Если нет - вычёркиваете B из списка.

3. Смотрите, сколько народу осталось в списке. Если два или больше - повторяете действие 2.

4. В списке остался один человек - это и есть знаменитость.

Книжка совершенно замечательная, в ней масса самых разнообразных историй.

Comments

[juan_gandhi]

Любопытно.

[vak]

Имена авторов русские, что интересно. Ананий Левитин - профессор Computer Science в университете Villanova.

[johnconst.livejournal.com]

Левитин нерусская фамилия, а еврейская

[vak]

Еврейская пока молодой, а прославится - станет великим русским учёным.

[ivanrubilo]

Много лет назад коллега посоветовал его The Design & Analysis of Algorithms как менее унылую альтернативу Кормену и т.д. И в целом мне зашло. Надо и эту прикупить.

[vlkamov]

Напоминате алгоритм Евклида

[spyle]

Исходя из задания: если А не знает В, то он и есть занменитость! Зачем идти дальше?

[vak]

Ну, может быть A знает C или D.