Оптимальное решение для «знаменитости» алгоритм

Question

Среди n персон, «знаменитости» определяется как кто-то , который известен всеми, но не знает никого. Задача состоит в том, чтобы идентифицировать знаменитость, если таковая существует, задав вопрос только формы: «Извините, вы знаете человека ?» (Предполагается, что все ответы верны, и даже эта знаменитость также ответит.) Цель состоит в том, чтобы свести к минимуму количество вопросов.

Есть ли решение для заказа менее очевидного O(n^2)?

Answer 1

Используя анализ проблемы знаменитости here

перебор раствор. Граф имеет не более n(n-1) ребер, и мы можем вычислить его, задав вопрос для каждого потенциального края. При этом точка, мы можем проверить, является ли вершина поглотителем, вычисляя ее в зависимости от ее усталости. Это решение грубой силы задает вопросы n(n-1) . Затем мы покажем, как сделать это не более 3(n-1) вопросы и линейное место.

Изящное решение. Наш алгоритм состоит из двух этапов: на этапе исключения мы исключаем всех, кроме одного человека, из знаменитости ; на этапе проверки мы проверяем, является ли этот оставшимся человеком действительно знаменитостью. Фаза устранения поддерживает список возможных знаменитостей. Первоначально он содержит все n человек. На каждой итерации мы удаляем одного человека из списка. We эксплуатировать следующее ключевое наблюдение: если лицо 1 знает лицо 2, then person 1 не является знаменитостью; если лицо 1 не знает person 2, тогда человек 2 не является знаменитостью. Таким образом, запросив у человека 1, если он знает человек 2, мы можем удалить любое лицо 1 или личным лицом 2 из списка возможных знаменитостей. Мы можем неоднократно использовать эту идею, чтобы устранить всех людей, кроме одного, скажем, человека p. Проверим теперь грубой силой p является ли знаменитость: для любого другого человека i, мы спрашиваем человека знает p ли он человек i, и мы просим лицам i, знают ли они человек p. Если человек p всегда отвечает нет, а остальные люди всегда ответ да, мы объявляем человека p в качестве знаменитости. В противном случае, мы пришли к выводу, что в этой группе нет знаменитостей.

Answer 2

1. Разделить все люди в парах.

2. Для каждой пары (A, B) спросите A, если он знает B.

   • если да, то A не может быть знаменитостью, отбросьте его.
   • если ответ нет, B не может быть знаменитостью, отбросьте его.

   Теперь осталось только половина людей.

3. Повторите с 1 до тех пор, пока не останется только один человек.

Стоимость O (N).

Answer 3

Здесь O (N) времени алгоритм

1. Нажмите все элементы в стек.
2. Удалить два верхних элемента (скажем, А и В), и держать А если Б знает, А и А не знает Б.
3. Удалить оба А, В оба знают друг друга или оба не знают друг друга

Answer 4

Это мое решение.

#include<iostream> 
using namespace std; 
int main(){ 
    int n; 
    //number of celebrities 
    cin>>n; 
    int a[n][n]; 
    for(int i = 0;i < n;i++){ 
     for(int j = 0;j < n;j++){ 
      cin>>a[i][j]; 
     } 
    } 
    int count = 0; 
    for(int i = 0;i < n;i++){ 
     int pos = 0; 
     for(int j = 0;j < n;j++){ 
      if(a[i][j] == 0){ 
       count = count + 1; 
      } 
      else{ 
       count = 0; 
       break; 
      } 
     } 
     if(count == n){ 
      pos = i; 
      cout<<pos; 
      break; 
     } 
    } 

    return 0; 
}