language-agnostic - 从一个圈子中删除每个 'kth' 人。找到最后剩下的人

Question

作为最近的一份工作申请的一部分，我被要求编写一个解决这个问题的代码。

鉴于，

n = 围成一圈的人数。

k = 每次计数的人数

每个人都有一个唯一的(递增的)id。从第一个人(最低 id)开始，他们从 1 开始数到 k。

然后移除 k 处的人，圈子关闭。下一个剩下的人(在被淘汰的人之后)从 1 开始重新计数。这个过程重复进行，直到只剩下一个人，即获胜者。

解决方案必须提供:

每个人的 id，按照他们从圈子中删除的顺序排列

获胜者的 id。

性能限制:

使用尽可能少的内存。

使解决方案尽可能快地运行。

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

我已经提交了我的解决方案，所以我绝对不会找人来为我回答。一旦/如果其他人提供了一些答案，我将稍后提供。

我提出这个问题的主要目的是看看我的解决方案与其他解决方案的要求和限制相比如何。

(请仔细注意要求，因为我认为它们可能会使某些“经典”解决方案无效。)

Answer 1

曼努埃尔·冈萨雷斯 正确地注意到这是著名的 Josephus problem 的一般形式.

如果我们只对大小为 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 要求按正确顺序提供已消除项目的所有索引。但是，我相信上述见解也可以用来解决这个问题。