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

Ответ 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.

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

Ответ 2

Вы можете сделать это, используя массив 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

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

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

Ответ 3

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

Ответ 4

Это мое решение, закодированное на С#. Что можно улучшить?

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);

Ответ 5

По сути, это то же самое, что и для ответа Ash, но с пользовательским связанным списком:

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
            }
        }
    }
}

Ответ 6

Вот решение в 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 человек в оставшемся списке потенциальных победителей

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

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

Ответ 7

Это вариант проблемы Josephus.

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

Решения в 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;
}

Ответ 8

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

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;
}