Ищем знаменитость
2021-07-20 18:48![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
vakКупил сборник алгоритмических головоломок, штудирую, получаю удовольствие. Вот задачка, к примеру: найти знаменитость на вечеринке. Определим знаменитость как персону, которую все знают, но она не знает никого. Представьте, что вы попали на тусовку, и вам надо найти среди присутствующих эту знаменитость. Вы можете задавать люди вопрос: "Знаете ли вы этого человека?", и показывать на кого-нибудь. Как организовать эффективный поиск?
Оказывается, есть простой алгоритм.
1. Составляете список всех присутствующих, среди них есть и искомая знаменитость.
2. Подходите к кому-нибудь (обозначим его A) и спрашиваете, знает ли он соседа (обозначим его B). Он отвечает либо да, либо нет. Если да - вычёркиваете A из списка. Если нет - вычёркиваете B из списка.
3. Смотрите, сколько народу осталось в списке. Если два или больше - повторяете действие 2.
4. В списке остался один человек - это и есть знаменитость.
Книжка совершенно замечательная, в ней масса самых разнообразных историй.
Оказывается, есть простой алгоритм.
1. Составляете список всех присутствующих, среди них есть и искомая знаменитость.
2. Подходите к кому-нибудь (обозначим его A) и спрашиваете, знает ли он соседа (обозначим его B). Он отвечает либо да, либо нет. Если да - вычёркиваете A из списка. Если нет - вычёркиваете B из списка.
3. Смотрите, сколько народу осталось в списке. Если два или больше - повторяете действие 2.
4. В списке остался один человек - это и есть знаменитость.
Книжка совершенно замечательная, в ней масса самых разнообразных историй.
