Удаление каждого «kth» человека из круга. Найти последнего оставшегося человека

Question

В рамках недавнего заявления о приеме на работу меня попросили написать решение этой проблемы.

Учитывая,

• n = количество людей, стоящих в кругу.
• k = количество людей, на которое нужно рассчитывать каждый раз

Каждому человеку присваивается уникальный (инкрементный) идентификатор. Начиная с первого человека (самый низкий идентификатор), они начинают считать от 1 до k.

Человек в k тогда удален, и круг закрывается. Следующий оставшийся человек (после выбывшего) возобновляет счет с 1. Этот процесс повторяется до тех пор, пока не останется только один человек, победитель.

Решение должно предоставить:

• идентификатор каждого человека в порядке их удаления из круга
• идентификатор победителя.

Ограничения производительности:

• Используйте как можно меньше памяти.
• Сделайте так, чтобы решение работало как можно быстрее.

Я вспомнил, как делал что-то похожее в моем курсе CS несколько лет назад, но не мог вспомнить подробности во время этого теста. Теперь я понимаю, что это хорошо известная классическая проблема с несколькими решениями. (Я пока не буду упоминать это по имени, так как некоторые могут просто ответить «википедией»).

Я уже отправил свое решение, поэтому я абсолютно не ищу людей, которые бы ответили за него. Я предоставлю это чуть позже один раз / если другие предоставят некоторые ответы.

Моя главная цель задать этот вопрос - увидеть, как мое решение сравнивается с другими, учитывая требования и ограничения.

(Обратите внимание на требования, поскольку я думаю, что они могут сделать недействительными некоторые «классические» решения.)

Answer 1

Мануэль Гонсалес правильно заметил, что это общая форма знаменитой проблемы Иосифа .

Если нас интересует только оставшийся в живых f (N, K) круга размера N и скачков размера K, то мы можем решить это с помощью очень простого цикла динамического программирования (с линейным временем и постоянной памятью). Обратите внимание, что идентификаторы начинаются с 0:

int remaining(int n, int k) {
    int r = 0;
    for (int i = 2; i <= n; i++)
        r = (r + k) % i;

    return r;
}

Он основан на следующем рекуррентном отношении:

f (N, K) = (f (N-1, K) + K) mod N

Это отношение может быть объяснено путем моделирования процесса исключения и после каждого исключения повторного назначения новых идентификаторов, начиная с 0. Старые индексы являются новыми с круговым сдвигом k позиций. Для более подробного объяснения этой формулы см. http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf.

Я знаю, что ОП запрашивает все индексы исключенных предметов в правильном порядке. Тем не менее, я полагаю, что вышеупомянутое понимание может быть использовано и для решения этой проблемы.

Answer 2

Проблема определения «kth» человека называется проблемой Иосифа. Армин Шамс-Барах из Мешхедского университета имени Фердоуси опубликовал некоторые формулы для проблемы Иосифа и ее расширенную версию Документ доступен по адресу: http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf

Answer 3

Вы можете сделать это, используя массив boolean.

Вот псевдокод:

Пусть alive будет boolean массивом размера N. Если alive[i] равно true, тогда ith человек жив, а мертв. Первоначально это true для каждого 1>=i<=N
Пусть numAlive будет числом живых людей. Итак numAlive = N в начале.

i = 1 # Counting starts from 1st person.
count = 0;

# keep looping till we've more than 1 persons.
while numAlive > 1 do

 if alive[i]
  count++
 end-if

 # time to kill ?
 if count == K
   print Person i killed
   numAlive --
   alive[i] = false
   count = 0
 end-if

 i = (i%N)+1 # Counting starts from next person.

end-while

# Find the only alive person who is the winner.
while alive[i] != true do
 i = (i%N)+1
end-while
print Person i is the winner

Приведенное выше решение экономит место, но не экономит время, так как мертвые люди проверяются.

Для повышения эффективности использования времени вы можете использовать круговой связанный список . Каждый раз, когда вы убиваете человека, вы удаляете узел из списка. Вы продолжаете, пока в списке не останется один узел.

Answer 4

Это вариант проблемы Иосифа .

Общие решения описаны здесь .

Решения на Perl, Ruby и Python предоставляются здесь . Ниже приведено простое решение на языке C, использующее круговой двусвязный список для представления кольца людей. Однако ни одно из этих решений не определяет положение каждого человека по мере его удаления.

#include <stdio.h>
#include <stdlib.h>

/* remove every k-th soldier from a circle of n */
#define n 40
#define k 3

struct man {
    int pos;
    struct man *next;
    struct man *prev;
};

int main(int argc, char *argv[])
{
    /* initialize the circle of n soldiers */
    struct man *head = (struct man *) malloc(sizeof(struct man));
    struct man *curr;
    int i;
    curr = head;
    for (i = 1; i < n; ++i) {
        curr->pos = i;
        curr->next = (struct man *) malloc(sizeof(struct man));
        curr->next->prev = curr;
        curr = curr->next;
    }
    curr->pos = n;
    curr->next = head;
    curr->next->prev = curr;

    /* remove every k-th */
    while (curr->next != curr) {
        for (i = 0; i < k; ++i) {
            curr = curr->next;
        }
        curr->prev->next = curr->next;
        curr->next->prev = curr->prev;
    }

    /* announce last person standing */
    printf("Last person standing: #%d.\n", curr->pos);
    return 0;
}

Answer 5

Вот решение в Clojure:

(ns kthperson.core
  (:use clojure.set))


(defn get-winner-and-losers [number-of-people hops]
  (loop [people (range 1 (inc number-of-people))
         losers []
         last-scan-start-index (dec hops)]
    (if (= 1 (count people))
      {:winner (first people) :losers losers}
      (let [people-to-filter (subvec (vec people) last-scan-start-index)
            additional-losers (take-nth hops people-to-filter)
            remaining-people (difference (set people)
                                         (set additional-losers))
            new-losers (concat losers additional-losers)
            index-of-last-removed-person (* hops (count additional-losers))]
        (recur remaining-people
               new-losers
               (mod last-scan-start-index (count people-to-filter)))))))

Объяснение:

• начать цикл с набором людей 1..n

• если остался только один человек, он становится победителем, и мы возвращаем их удостоверение личности, а также идентификаторы проигравших (в порядке их проигрыша)

• мы рассчитываем дополнительных проигравших в каждом цикле / повторении, отбирая каждого N человек из оставшегося списка потенциальных победителей

• новый, более короткий список потенциальных победителейопределяется путем удаления дополнительных проигравших из ранее рассчитанных потенциальных победителей.

• промыть и повторить (используя модуль, чтобы определить, где в списке оставшихся людей начать подсчет в следующий раз)

Answer 6

По существу такой же, как и ответ Эша, но с настраиваемым связанным списком:

using System;
using System.Linq;

namespace Circle
{
    class Program
    {
        static void Main(string[] args)
        {
            Circle(20, 3);
        }

        static void Circle(int k, int n)
        {
            // circle is a linked list representing the circle.
            // Each element contains the index of the next member
            // of the circle.
            int[] circle = Enumerable.Range(1, k).ToArray();
            circle[k - 1] = 0;  // Member 0 follows member k-1

            int prev = -1;  // Used for tracking the previous member so we can delete a member from the list
            int curr = 0;  // The member we're currently inspecting
            for (int i = 0; i < k; i++)  // There are k members to remove from the circle
            {
                // Skip over n members
                for (int j = 0; j < n; j++)
                {
                    prev = curr;
                    curr = circle[curr];
                }

                Console.WriteLine(curr);
                circle[prev] = circle[curr];  // Delete the nth member
                curr = prev;  // Start counting again from the previous member
            }
        }
    }
}

Answer 7

Это моё решение, написанное на C #. Что можно улучшить?

public class Person
{
    public Person(int n)
    {
        Number = n;
    }

    public int Number { get; private set; }
}


static void Main(string[] args)
{
    int n = 10; int k = 4;
    var circle = new List<Person>();

    for (int i = 1; i <= n; i++)
    {
        circle.Add(new Person(i));
    }

    var index = 0;
    while (circle.Count > 1)
    {
        index = (index + k - 1) % circle.Count;
        var person = circle[index];
        circle.RemoveAt(index);
        Console.WriteLine("Removed {0}", person.Number);
    }
    Console.ReadLine();
}
        Console.WriteLine("Winner is {0}", circle[0].Number);

Answer 8

Вот мой ответ в C #, как представлено.Не стесняйтесь критиковать, смеяться, высмеивать и т.д .;)

public static IEnumerable<int> Move(int n, int k)
{
    // Use an Iterator block to 'yield return' one item at a time.  

    int children = n;
    int childrenToSkip = k - 1;

    LinkedList<int> linkedList = new LinkedList<int>();

    // Set up the linked list with children IDs
    for (int i = 0; i < children; i++)
    {
        linkedList.AddLast(i);
    }

    LinkedListNode<int> currentNode = linkedList.First;

    while (true)
    {
        // Skip over children by traversing forward 
        for (int skipped = 0; skipped < childrenToSkip; skipped++)
        {
            currentNode = currentNode.Next;
            if (currentNode == null) currentNode = linkedList.First;
        }

        // Store the next node of the node to be removed.
        LinkedListNode<int> nextNode = currentNode.Next;

        // Return ID of the removed child to caller 
        yield return currentNode.Value;

        linkedList.Remove(currentNode);

        // Start again from the next node
        currentNode = nextNode;
        if (currentNode== null) currentNode = linkedList.First;

        // Only one node left, the winner
        if (linkedList.Count == 1) break;  
    }

    // Finally return the ID of the winner
    yield return currentNode.Value;
}