Рубрики

Проблема знаменитости

Матрицы, Стек

В группе из N человек всем известен только один человек. Такой человек может присутствовать на вечеринке, если да, то он не знает никого на вечеринке. Мы можем только задавать вопросы типа « А знает ли Б? «. Найдите незнакомца (знаменитость) в минимальном количестве вопросов.

Мы можем описать ввод проблемы как массив чисел / символов, представляющих людей в группе. У нас также есть гипотетическая функция HaveAcquaintance (A, B), которая возвращает true, если A знает B, иначе false . Как мы можем решить эту проблему.

Мы измеряем сложность с точки зрения обращений к HaveAcquaintance ().

Метод 1 (график)

Мы можем смоделировать решение, используя графики. Инициализируйте степень и степень каждой вершины как 0. Если A знает B, нарисуйте направленное ребро из A в B, увеличьте степень B и степень A на 1. Постройте все возможные ребра графа для каждой возможной пары [i, j ]. У нас есть N C 2 пары. Если на вечеринке присутствует знаменитость, у нас будет один приемный узел на графике с нулевой степенью и степенью N-1. Мы можем найти узел приемника за (N) времени, но общая сложность составляет O (N 2 ), так как нам нужно сначала построить граф.

Метод 2 (рекурсия)

Мы можем разложить проблему на комбинацию меньших экземпляров. Скажем, если мы знаем знаменитостей из N-1, можем ли мы распространить решение на N? У нас есть две возможности: Знаменитость (N-1) может знать N, или N уже знала Знаменитость (N-1). В первом случае N будет знаменитостью, если N никого не знает. В последнем случае нам нужно проверить, что Знаменитость (N-1) не знает N.

Решите проблему меньшего экземпляра во время шага деления. На обратном пути мы находим знаменитость (если есть) из меньшего экземпляра. На этапе объединения проверьте, известна ли всем возвращенная знаменитость, и он никого не знает. Рецидив рекурсивного разложения

Т (Н) = Т (Н-1) + О (Н)

T (N) = O (N 2 ). Вы можете попробовать написать псевдокод, чтобы проверить свои навыки рекурсии.

Метод 3 (Использование стека)
Построение графа занимает O (N 2 ) времени, оно похоже на поиск методом перебора. В случае рекурсии мы уменьшаем экземпляр проблемы не более чем на один, а также комбинированный шаг, позволяющий проверить M-1 человек (M — размер экземпляра).

У нас есть следующие наблюдения, основанные на технике исключения (см. Книгу Поли «Как решить» ).

  • Если А знает В, то А не может быть знаменитостью. Откажитесь от А, и Б может быть знаменитостью .
  • Если A не знает B, то B не может быть знаменитостью. Откажитесь от Б, и А может быть знаменитостью .
  • Повторите выше два шага, пока мы не ушли только с одним человеком.
  • Убедитесь, что оставшийся человек знаменитость. (Зачем нам этот шаг?)

Мы можем использовать стек для настоящей знаменитости.

  1. Сложите всех знаменитостей в стек.
  2. Вытащите двух верхних игроков из стека, откажитесь от одного человека на основе статуса возврата HaveAcquaintance (A, B) .
  3. Поместите оставшегося человека в стек.
  4. Повторите шаги 2 и 3, пока в стеке не останется только один человек.
  5. Проверьте, что оставшийся человек в стеке не знаком с кем-либо еще.

Мы отбросим N элементов максимально (Почему?). Если знаменитость присутствует на вечеринке, мы будем вызывать HaveAcquaintance () 3 (N-1) раза. Вот код, использующий стек.

C ++

// C ++ программа для поиска знаменитостей
#include <bits/stdc++.h>
#include <list>

using namespace std;

  
// Максимальное количество человек в партии
#define N 8

  
// Человек с 2 - знаменитость

bool MATRIX[N][N] = {{0, 0, 1, 0},

                    {0, 0, 1, 0},

                    {0, 0, 0, 0},

                    {0, 0, 1, 0}};

  

bool knows(int a, int b)

{

    return MATRIX[a][b];

}

  
// Возвращает -1 если знаменитость
// нет. Если представить,
// возвращает идентификатор (значение от 0 до n-1).

int findCelebrity(int n)

{

    // Обработка тривиального

    // case of size = 2

  

    stack<int> s;

  

    int C; // Знаменитости

  

    // толкаем всех в стек

    for (int i = 0; i < n; i++)

        s.push(i);

  

    // Извлечь топ 2

    int A = s.top();

    s.pop();

    int B = s.top();

    s.pop();

  

    // Найти потенциальную достоверность

    while (s.size() > 1)

    {

        if (knows(A, B))

        {

            A = s.top();

            s.pop();

        }

        else

        {

            B = s.top();

            s.pop();

        }

    }

  

    // Потенциальный кандидат?

    C = s.top();

    s.pop();

  

    // Последний кандидат не был

    // осмотрено, приводит

    // избыточное сравнение (оптимизация)

    if (knows(C, B))

        C = B;

  

    if (knows(C, A))

        C = A;

  

    // Проверить, действительно ли C

    // знаменитость или нет

    for (int i = 0; i < n; i++)

    {

        // Если кто-то не

        // знаю, что «а» или «а» не

        // узнать любого человека, вернуть -1

        if ( (i != C) &&

                (knows(C, i) || 

                 !knows(i, C)) )

            return -1;

    }

  

    return C;

}

  
// Код драйвера

int main()

{

    int n = 4;

    int id = findCelebrity(n);

    id == -1 ? cout << "No celebrity" :

               cout << "Celebrity ID " << id;

    return 0;

}

Джава

// Java-программа для поиска знаменитостей с помощью
// структура данных стека

  

import java.util.Stack;

  

class GFG 

{

    // Человек с 2 - знаменитость

    static int MATRIX[][] = { { 0, 0, 1, 0 },

                            { 0, 0, 1, 0 },

                            { 0, 0, 0, 0 }, 

                            { 0, 0, 1, 0 } };

  

    // Возвращает true, если знает

    // b, ложь в противном случае

    static boolean knows(int a, int b) 

    {

        boolean res = (MATRIX[a][b] == 1) ? 

                                     true : 

                                     false;

        return res;

    }

  

    // Возвращает -1 если знаменитость

    // нет. Если представить,

    // возвращает идентификатор (значение от 0 до n-1).

    static int findCelebrity(int n) 

    {

        Stack<Integer> st = new Stack<>();

        int c;

  

        // Шаг 1: подтолкнуть всех

        // в стек

        for (int i = 0; i < n; i++) 

        {

            st.push(i);

        }

  

        while (st.size() > 1) 

        {

            // Шаг 2: выскочить сверху

            // два человека из

            // укладываем, отбрасываем

            // человек, основанный на возврате

            // статус знает (A, B).

            int a = st.pop();

            int b = st.pop();

  

            // Шаг 3: Нажмите

            // оставшийся человек в стеке.

            if (knows(a, b)) 

            {

                st.push(b);

            }

  

            else

                st.push(a);

        }

  

        c = st.pop();

  

        // Шаг 5: Проверьте, последний ли

        // человек знаменитость или нет

        for (int i = 0; i < n; i++) 

        {

            // Если кто-то не

            // знаю, что «с» или «а» не

            // узнать любого человека, вернуть -1

            if (i != c && (knows(c, i) || 

                          !knows(i, c)))

                return -1;

        }

        return c;

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        int n = 4;

        int result = findCelebrity(n);

        if (result == -1) 

        {

            System.out.println("No Celebrity");

        } 

        else

            System.out.println("Celebrity ID " + 

                                        result);

    }

}

  
// Этот код добавлен
// Ришабх Марси


Выход :

Celebrity ID 2

Сложность O (N). Всего сравнений 3 (N-1). Попробуйте приведенный выше код для успешного выполнения MATRIX {{0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}}.

Примечание: вы можете подумать, зачем нам нужен новый график, поскольку у нас уже есть доступ к матрице ввода. Обратите внимание, что матрица MATRIX использовалась для помощи гипотетической функции HaveAcquaintance (A, B), но никогда не получала доступ через обычную запись MATRIX [i, j]. У нас есть доступ к входу только через функцию HaveAcquiantance (A, B) . Матрица — это просто способ кодирования решения. Мы можем принять стоимость гипотетической функции как O (1).

Если все еще не ясно, предположим, что функция HaveAcquiantance осуществляет доступ к информации, хранящейся в наборе связанных списков, расположенных по уровням. Узел списка будет иметь указатели next и nextLevel . Каждый уровень будет иметь N узлов, то есть список N элементов, следующие точки указывают на следующий узел в списке текущего уровня, а указатель nextLevel в последнем узле каждого списка будет указывать на заголовок списка следующего уровня. Например, представление связанного списка вышеупомянутой матрицы выглядит так:

L0 0->0->1->0
             |
L1           0->0->1->0
                       |
L2                     0->0->1->0
                                 |
L3                               0->0->1->0

Функция HaveAcquanintance (i, j) будет искать в списке j-й узел на i-м уровне. Наша цель — минимизировать вызовы функции HaveAcquanintance .

Метод 4 (с использованием двух указателей)

Идея состоит в том, чтобы использовать два указателя, один с начала и один с конца. Предположим, что начальный человек — А, а конечный — Б. Если А знает В, то А не должен быть знаменитостью. Иначе, Б не должно быть знаменитостью. Мы найдем кандидата в знаменитости в конце цикла. Пройдите через каждого человека снова и проверьте, является ли это знаменитостью. Ниже приведена реализация C ++.

C ++

// C ++ программа для поиска
// знаменитость в O (n) время
// и O (1) лишний пробел
#include <bits/stdc++.h>

using namespace std;

  
// Максимальное количество человек в партии
#define N 8

  
// Человек с 2 - знаменитость

bool MATRIX[N][N] = {{0, 0, 1, 0},

                     {0, 0, 1, 0},

                     {0, 0, 0, 0},

                     {0, 0, 1, 0}

};

  

bool knows(int a, int b)

{

    return MATRIX[a][b];

}

  
// Возвращает идентификатор знаменитости

int findCelebrity(int n)

{

    // Инициализируем два указателя

    // как два угла

    int a = 0;

    int b = n - 1;

  

    // Продолжайте двигаться, пока

    // два указателя

    // не становиться таким же.

    while (a < b)

    {

        if (knows(a, b))

            a++;

        else

            b--;

    }

  

    // Проверить, действительно ли a

    // знаменитость или нет

    for (int i = 0; i < n; i++)

    {

        // Если кто-то не

        // знаю, что «а» или «а» не

        // узнать любого человека, вернуть -1

        if ( (i != a) &&

                (knows(a, i) || 

                !knows(i, a)) )

            return -1;

    }

  

    return a;

}

  
// Код драйвера

int main()

{

    int n = 4;

    int id = findCelebrity(n);

    id == -1 ? cout << "No celebrity" :

               cout << "Celebrity ID " 

                    << id;

    return 0;

}

Джава

// Java-программа для поиска
// знаменитость использует два
// указатели

  

class GFG 

{

    // Человек с 2 - знаменитость

    static int MATRIX[][] = { { 0, 0, 1, 0 },

                               { 0, 0, 1, 0 }, 

                              { 0, 0, 0, 0 },

                              { 0, 0, 1, 0 } };

  

    // Возвращает true, если знает

    // b, ложь в противном случае

    static boolean knows(int a, int b) 

    {

        boolean res = (MATRIX[a][b] == 1) ? 

                                     true : 

                                     false;

        return res;

    }

  

    // Возвращает -1 если знаменитость

    // нет. Если представить,

    // возвращает идентификатор (значение от 0 до n-1).

    static int findCelebrity(int n) 

    {

        // Инициализируем два указателя

        // как два угла

        int a = 0;

        int b = n - 1;

          

        // Продолжайте двигаться, пока

        // два указателя

        // не становиться таким же.

        while (a < b) 

        {

            if (knows(a, b))

                a++;

            else

                b--;

        }

  

        // Проверить, действительно ли a

        // знаменитость или нет

        for (int i = 0; i < n; i++) 

        {

            // Если кто-то не

            // знаю, что «а» или «а» не

            // узнать любого человека, вернуть -1

            if (i != a && (knows(a, i) || 

                           !knows(i, a)))

                return -1;

        }

        return a;

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        int n = 4;

        int result = findCelebrity(n);

        if (result == -1) 

        {

            System.out.println("No Celebrity");

        } 

        else

            System.out.println("Celebrity ID " + 

                                        result);

    }

}

  
// Этот код предоставлен Rishabh Mahrsee

C #

// C # программа для поиска
// знаменитость использует два
// указатели

using System;

  

class GFG 

{

    // Человек с 2 - знаменитость

    static int [,]MATRIX = {{ 0, 0, 1, 0 },

                            { 0, 0, 1, 0 }, 

                            { 0, 0, 0, 0 },

                            { 0, 0, 1, 0 }};

  

    // Возвращает true, если знает

    // b, ложь в противном случае

    static bool knows(int a, int b) 

    {

        bool res = (MATRIX[a, b] == 1) ? 

                                  true : 

                                  false;

        return res;

    }

  

    // Возвращает -1 если знаменитость

    // нет. Если представить,

    // возвращает идентификатор (значение от 0 до n-1).

    static int findCelebrity(int n) 

    {

        // Инициализируем два указателя

        // как два угла

        int a = 0;

        int b = n - 1;

          

        // Продолжайте двигаться, пока

        // два указателя

        // не становиться таким же.

        while (a < b) 

        {

            if (knows(a, b))

                a++;

            else

                b--;

        }

  

        // Проверить, действительно ли a

        // знаменитость или нет

        for (int i = 0; i < n; i++) 

        {

            // Если кто-то не

            // знаю, что «а» или «а» не

            // узнать любого человека, вернуть -1

            if (i != a && (knows(a, i) || 

                          !knows(i, a)))

                return -1;

        }

        return a;

    }

  

    // Код драйвера

    public static void Main() 

    {

        int n = 4;

        int result = findCelebrity(n);

        if (result == -1) 

        {

            Console.WriteLine("No Celebrity");

        } 

        else

            Console.WriteLine("Celebrity ID " + 

                                       result);

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для поиска
// знаменитость в O (n) время
// и O (1) лишний пробел

  

  
// Максимальное количество человек
// в партии $ N = 8;

  
// Человек с 2 - знаменитость

$MATRIX = array(array(0, 0, 1, 0),

                array(0, 0, 1, 0),

                array(0, 0, 0, 0),

                array(0, 0, 1, 0));

  

function knows( $a, $b)

{

    global $MATRIX;

    return $MATRIX[$a][$b];

}

  
// Возвращает идентификатор знаменитости

function findCelebrity( $n)

{

    // Инициализируем два

    // указатели как два угла

    $a = 0;

    $b = $n - 1;

  

    // Продолжайте двигаться, пока

    // два указателя

    // не становиться таким же.

    while ($a < $b)

    {

        if (knows($a, $b))

            $a++;

        else

            $b--;

    }

  

    // Проверить, действительно ли a

    // знаменитость или нет

    for ( $i = 0; $i < $n; $i++)

    {

        // Если кто-то не

        // знаю, что «а» или «а» не

        // узнать любого человека, вернуть -1

        if ( ($i != $a) and

                (knows($a, $i) || 

                !knows($i, $a)) )

            return -1;

    }

  

    return $a;

}

  
// Код драйвера

$n = 4;

$id = findCelebrity($n);

if($id == -1)

echo "No celebrity" ;

else

echo "Celebrity ID " , $id;

  
// Этот код предоставлен anuj_67.
?>


Выход :

Celebrity ID 2

Спасибо Сисси Пенг за предложение этого метода.

Связанная статья:
Количество узлов стока в графе

Упражнения:
1. Напишите код, чтобы найти знаменитость. Не используйте какие-либо структуры данных, такие как графики, стек и т. Д., У вас есть доступ только к N и HaveAcquaintance (int, int) .

2. Реализуйте алгоритм, используя Очереди. Каково ваше наблюдение? Сравните ваше решение с поиском максимума и минимума в массиве и турнирным деревом . Какое минимальное количество сравнений нам нужно (оптимальное количество обращений к HaveAcquaintance () )?

— Венки . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проблема знаменитости

0.00 (0%) 0 votes