Xóa mọi người 'kth' khỏi vòng kết nối. Tìm người còn lại cuối cùng

Question

Là một phần của đơn xin việc gần đây, tôi được yêu cầu viết mã giải pháp cho vấn đề này.

Given,

• n = số người đứng trong một vòng tròn.
• k = số người để đếm lại mỗi lần

Mỗi người được đưa ra một độc đáo (incrementing) id. Bắt đầu với người đầu tiên (id thấp nhất), họ bắt đầu đếm từ 1 đến k.

Người tại k sau đó sẽ bị xóa và vòng kết nối sẽ kết thúc. Người còn lại tiếp theo (sau người bị loại) tiếp tục đếm tại 1. Quá trình này lặp lại cho đến khi chỉ còn một người, người chiến thắng.

Các giải pháp phải cung cấp:

• id của mỗi người theo thứ tự chúng được đưa ra khỏi vòng tròn
• id của người chiến thắng.

chế Hiệu suất:

• Sử dụng ít bộ nhớ càng tốt.
• Làm cho giải pháp chạy nhanh nhất có thể.

Tôi nhớ đã làm điều tương tự trong khóa học CS của mình từ nhiều năm trước nhưng không thể nhớ lại chi tiết tại thời điểm kiểm tra này. Bây giờ tôi nhận ra nó là một vấn đề cổ điển, nổi tiếng với nhiều giải pháp. (Tôi sẽ không đề cập đến nó theo tên nào được nêu ra như một số chỉ có thể 'wikipedia' một câu trả lời).

Tôi đã gửi giải pháp của mình nên tôi hoàn toàn không tìm kiếm người để trả lời nó cho tôi. Tôi sẽ cung cấp cho nó một chút sau đó một lần/nếu những người khác đã cung cấp một số câu trả lời.

Mục tiêu chính của tôi khi đặt câu hỏi này là xem cách giải pháp của tôi so sánh với những người khác đã đưa ra các yêu cầu và ràng buộc.

(Lưu ý các yêu cầu một cách cẩn thận như tôi nghĩ rằng họ có thể làm mất hiệu lực một số các giải pháp 'cổ điển'.)

Answer 1

Đây là giải pháp của tôi, được mã hóa trong C#. Điều gì có thể được cải thiện?

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 2

Bạn có thể làm điều đó bằng cách sử dụng mảng boolean.

Đây là một mã giả:

Hãy alive là một mảng boolean kích thước N. Nếu alive[i] là true thì ith người còn sống khác đã chết. Ban đầu nó là true cho mỗi 1>=i<=N
Hãy để số numAlive là số người còn sống. Vì vậy, numAlive = N khi bắt đầu.

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 

Giải pháp trên là không gian hiệu quả nhưng không hiệu quả về thời gian khi người chết đang được kiểm tra.

Để làm cho thời gian hiệu quả hơn, bạn có thể sử dụng danh sách được liên kết tròn tròn. Mỗi khi bạn giết một người bạn xóa một nút khỏi danh sách. Bạn tiếp tục cho đến khi một nút duy nhất còn lại trong danh sách.

Answer 3

Đây là câu trả lời của tôi trong C#, như đã gửi. Cảm thấy tự do để chỉ trích, cười nhạo, nhạo báng vv;)

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

Answer 4

Về cơ bản giống như câu trả lời của Ash, nhưng với một tùy chỉnh danh sách liên kết:

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 5

Vấn đề xác định 'thứ k' người là được gọi là Vấn đề Josephus. Armin Shams-Baragh từ Đại học Ferdowsi của Mashhad đã xuất bản một số công thức cho vấn đề Josephus và phiên bản mở rộng của nó. giấy này có sẵn tại địa chỉ: http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf

Answer 6

Dưới đây là một giải pháp trong 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))))))) 

Giải thích:

• bắt đầu một vòng lặp, với một bộ sưu tập của người 1..n

• nếu chỉ còn một người, họ là người chiến thắng và chúng tôi trả lại ID của họ, cũng như ID của người thua cuộc (theo thứ tự em mất)

• chúng tôi tính toán thêm thua trong mỗi vòng/tái diễn bằng cách lấy mỗi người N trong danh sách còn lại của người chiến thắng tiềm năng

• mới, danh sách ngắn những người chiến thắng tiềm năng được xác định bằng cách loại bỏ các người thua cuộc bổ sung từ những người chiến thắng tiềm năng được tính toán trước đó.

• rửa & lặp lại (sử dụng mô đun để xác định nơi trong danh sách những người còn lại để bắt đầu đếm vòng thời gian tiếp theo)

Answer 7

Manuel Gonzalez nhận thấy một cách chính xác rằng đây là hình thức chung của người nổi tiếng Josephus problem.

Nếu chúng ta chỉ quan tâm đến người sống sót f (N, K) của một vòng tròn có kích thước N và nhảy K, thì chúng ta có thể giải quyết điều này với một vòng lặp lập trình động rất đơn giản (Trong thời gian tuyến tính và bộ nhớ không đổi) .Lưu ý rằng các id bắt đầu từ 0:

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

    return r; 
} 

Nó được dựa trên mối quan hệ tái phát sau:

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

Mối quan hệ này có thể được giải thích bằng cách mô phỏng quá trình loại bỏ, và sau mỗi lần loại bỏ gán lại các id mới bắt đầu từ 0. Các chỉ số cũ là các chỉ số mới với thay đổi tròn của vị trí k. Để có giải thích chi tiết hơn về công thức này, hãy xem http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf.

Tôi biết rằng OP yêu cầu tất cả các chỉ mục của các mục bị loại bỏ theo đúng thứ tự của chúng. Tuy nhiên, tôi tin rằng thông tin chi tiết ở trên có thể được sử dụng để giải quyết vấn đề này.

Answer 8

Đây là một biến thể của Josephus problem.

Các giải pháp chung được mô tả here.

Các giải pháp trong Perl, Ruby và Python được cung cấp here. Một giải pháp đơn giản trong C bằng cách sử dụng một số circular doubly-linked list để biểu thị vòng của mọi người được cung cấp bên dưới. Tuy nhiên, không có giải pháp nào trong số này xác định được vị trí của mỗi người khi chúng bị loại bỏ.

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