从圆圈中移除每个"第k个"人.找到最后剩下的人

Question

作为最近的工作申请的一部分,我被要求为这个问题编写解决方案.

鉴于,

• n =站成一圈的人数.
• k =每次计算的人数

每个人都有一个唯一的(递增的)id.从第一个人(最低身份证)开始,他们从1到k开始计数.

然后移除k处的人并且圆圈闭合.下一个剩余的人(在被淘汰的人之后)恢复计数为1.这个过程重复,直到只剩下一个人为胜者.

解决方案必须提供:

• 每个人的ID按照他们从圈子中删除的顺序
• 胜利者的身份.

性能限制:

• 使用尽可能少的内存.
• 使解决方案尽可能快地运行.

我记得多年前在我的CS课程中做过类似的事情,但在这次测试时无法回想起细节.我现在意识到这是一个众所周知的经典问题,有多种解决方案.(我不会提到它的名字,因为有些人可能只是'维基百科'的答案).

我已经提交了我的解决方案,所以我绝对不会找人帮我回答.如果其他人提供了一些答案,我会稍后提供一次.

我提出这个问题的主要目的是看看我的解决方案在满足要求和约束条件下与其他解决方案的比较.

(请仔细注意要求,因为我认为它们可能会使某些"经典"解决方案失效.)

Answer 1

Manuel Gonzalez正确地注意到这是着名的约瑟夫斯问题的一般形式.

如果我们只对大小为N的圆的幸存者f(N,K)和大小为K的跳跃感兴趣,那么我们可以通过一个非常简单的动态编程循环(线性时间和常数存储器)来解决这个问题.请注意,ID从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以正确的顺序询问被淘汰物品的所有指数.但是,我相信上述见解也可用于解决这个问题.

Answer 2

这是我的解决方案，用 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);