Знаменитостью (celebrity) на вечеринке называется человек, которого знают все остальные присутствующие, а сам он не знает никого. (Нужно отметить, что если Петя знает Васю, то не факт, что Вася знает Петю).
Вы пришли на вечеринку, на которой присутствуют n человек, чтобы выяснить, есть ли на ней знаменитость. Вы можете подходить к очередному гостю и задавать вопрос вида "Простите, Вы знаете человека X?" и получать ответ да/нет.
Как выяснить, есть ли на вечеринке знаменитость, и если есть, то кто именно, задав минимальное число вопросов?
Есть более формальная версия задачи. Рассмотрим ориентированный граф G(V,E). Вершину v назовём стоком графа, если для любой вершины u отличной от v существует дуга (u, v) и не существует дуги (v, u). Требуется либо найти такую вершину в графе, либо указать, что её нет.
Решение
Составим список из всех кандидатов в знаменитости. Изначально в нём будут все присутствующие гости.
Подойдём к первому попавшемуся гостю (назовём его A) и спросим, знает ли он произвольного гостя B.
а) Если A знает B, то A точно не может быть celebrity (знаменитость по определению не знает никого). Вычеркнем его из списка.
б) Если A не знает B, то из списка кандидатов можно вычеркнуть B (celebrity должны знать все).
Таким образом, при любом ответе A наш список уменьшится на одного человека.
Задав n-1 вопрос, мы вычеркнем из списка всех гостей кроме одного - последнего из кандидатов в знаменитости. Теперь нужно проверить, является ли этот последний знаменитостью.
Для этого мы зададим ему n-1 вопрос о каждом из гостей. Если окажется, что он не знает никого, то каждому из гостей мы зададим вопрос об этом кандидате. Если все скажут, что знают его, то он и есть знаменитость. Если же окажется, что он кого-то знает, или же кто-то не знает его, то знаменитости на вечеринке нет.
Всего мы зададим 3*(n-1) вопросов.
В англоязычном интернете задача известна как Celebrity Problem, первая же ссылка в Гугле выдаёт неплохой разбор задачи.
Вы пришли на вечеринку, на которой присутствуют n человек, чтобы выяснить, есть ли на ней знаменитость. Вы можете подходить к очередному гостю и задавать вопрос вида "Простите, Вы знаете человека X?" и получать ответ да/нет.
Как выяснить, есть ли на вечеринке знаменитость, и если есть, то кто именно, задав минимальное число вопросов?
Есть более формальная версия задачи. Рассмотрим ориентированный граф G(V,E). Вершину v назовём стоком графа, если для любой вершины u отличной от v существует дуга (u, v) и не существует дуги (v, u). Требуется либо найти такую вершину в графе, либо указать, что её нет.
Решение
Составим список из всех кандидатов в знаменитости. Изначально в нём будут все присутствующие гости.
Подойдём к первому попавшемуся гостю (назовём его A) и спросим, знает ли он произвольного гостя B.
а) Если A знает B, то A точно не может быть celebrity (знаменитость по определению не знает никого). Вычеркнем его из списка.
б) Если A не знает B, то из списка кандидатов можно вычеркнуть B (celebrity должны знать все).
Таким образом, при любом ответе A наш список уменьшится на одного человека.
Задав n-1 вопрос, мы вычеркнем из списка всех гостей кроме одного - последнего из кандидатов в знаменитости. Теперь нужно проверить, является ли этот последний знаменитостью.
Для этого мы зададим ему n-1 вопрос о каждом из гостей. Если окажется, что он не знает никого, то каждому из гостей мы зададим вопрос об этом кандидате. Если все скажут, что знают его, то он и есть знаменитость. Если же окажется, что он кого-то знает, или же кто-то не знает его, то знаменитости на вечеринке нет.
Всего мы зададим 3*(n-1) вопросов.
В англоязычном интернете задача известна как Celebrity Problem, первая же ссылка в Гугле выдаёт неплохой разбор задачи.
Комментариев нет:
Отправить комментарий