作为最近的一份工作申请的一部分，我被要求编写一个解决这个问题的代码。
鉴于，
每个人都有一个唯一的（递增的）id。从第一个人（最低 id）开始，他们从 1 开始数到 k。
然后，k 处的人被移除，圆圈闭合。下一个剩余的人（在被淘汰的人之后）从 1 开始重新计数。这个过程重复进行，直到只剩下一个人，即获胜者。
解决方案必须提供：
性能限制：
我记得几年前在我的 CS 课程中做过类似的事情，但在这次测试时无法回忆起细节。我现在意识到这是一个众所周知的经典问题，有多种解决方案。（我不会提到它的名字，因为有些人可能只是“维基百科”一个答案）。
我已经提交了我的解决方案，所以我绝对不会找人来为我回答。一旦/如果其他人提供了一些答案，我将稍后提供。
我提出这个问题的主要目的是看看我的解决方案与其他解决方案的要求和限制相比如何。
（请仔细注意要求，因为我认为它们可能会使某些“经典”解决方案无效。）
Manuel Gonzalez正确地注意到这是著名的约瑟夫斯问题的一般形式。
如果我们只对大小为 N 的圆的幸存者 f(N,K) 和大小为 K 的跳跃感兴趣，那么我们可以用一个非常简单的动态编程循环（在线性时间和恒定内存中）来解决这个问题。请注意，ids 从 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 开始的新 id。旧索引是具有 k 个位置循环移位的新索引。有关此公式的更详细说明，请参阅http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf。
我知道 OP 要求按正确顺序提供已消除项目的所有索引。但是，我相信上述见解也可以用来解决这个问题。
您可以使用boolean数组来完成。
这是一个伪代码：
设为 sizealive的boolean数组N。如果alive[i]是，true那么ith人是活着的，否则是死的。最初它是true为每个1>=i<=N
LetnumAlive是活着的人数。所以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
由于正在检查死者，上述解决方案节省空间但不节省时间。
为了更有效地节省时间，您可以使用循环链表。每次杀死一个人时，都会从列表中删除一个节点。您继续直到列表中留下一个节点。
确定“第 k 个”人的问题称为约瑟夫斯问题。来自马什哈德费尔多西大学的 Armin Shams-Baragh 发表了一些约瑟夫斯问题及其扩展版本的公式。该论文可在以下网址获得： http ://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf
与 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
}
}
}
}
这是约瑟夫斯问题的一个变种。
此处描述了一般解决方案。
此处提供了 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;
}
这是我的解决方案，用 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);
这是 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
如果只剩下一个人，他们是赢家，我们返回他们的 ID，以及失败者的 ID（按照他们输掉的顺序）
我们通过抓取剩余潜在赢家列表中的每 N 人来计算每个循环/重复中的额外输家
通过从先前计算的潜在赢家中删除额外的输家来确定一个新的、更短的潜在赢家名单。
冲洗并重复（使用模数来确定剩余人员列表中下一轮开始计数的位置）
这是我在 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;
}