从圈子中删除每个"kth"人.找到最后剩下的人 [英] Removal of every 'kth' person from a circle. Find the last remaining person
问题描述
作为最近求职申请的一部分，我被要求编写解决此问题的方法.
As part of a recent job application I was asked to code a solution to this problem.
给出
- n =围成一圈的人数.
- k =每次计算的人数
每个人都有一个唯一的(递增)ID.从第一个人(最低ID)开始，他们从1到k开始计数.
Each person is given a unique (incrementing) id. Starting with the first person (the lowest id), they begin counting from 1 to k.
然后将位于k处的人删除，并关闭圆圈.下一个剩余的人(跟随被淘汰的人)恢复计数为1.重复此过程，直到只剩下一个人(获胜者)为止.
The person at k is then removed and the circle closes up. The next remaining person (following the eliminated person) resumes counting at 1. This process repeats until only one person is left, the winner.
该解决方案必须提供:
- 每个人的身份(从圈子中删除的顺序)
- 获胜者的ID.
性能约束:
- 使用尽可能少的内存.
- 使解决方案尽快运行.
我记得几年前在CS课程中做过类似的事情，但是在这次测试时却不记得详细信息.我现在意识到这是一个众所周知的经典问题，有多种解决方案. (由于某些人可能只是维基百科"的答案，所以我不会提及它的名字).
I remembered doing something similar in my CS course from years ago but could not recall the details at the time of this test. I now realize it is a well known, classic problem with multiple solutions. (I will not mention it by name yet as some may just 'wikipedia' an answer).
我已经提交了我的解决方案，因此我绝对不希望别人为我解答.我会稍后再提供(如果其他人提供了一些答案).
I've already submitted my solution so I'm absolutely not looking for people to answer it for me. I will provide it a bit later once/if others have provided some answers.
我提出这个问题的主要目的是，看看在给定要求和约束的情况下，我的解决方案与其他解决方案的比较.
My main goal for asking this question is to see how my solution compares to others given the requirements and constraints.
(请仔细注意要求，因为我认为它们可能会使某些经典"解决方案无效.)
(Note the requirements carefully as I think they may invalidate some of the 'classic' solutions.)
推荐答案
Manuel Gonzalez noticed correctly that this is the general form of the famous Josephus problem.
如果我们只对大小为N的圆的幸存者f(N，K)感兴趣，并且对大小为K的跳跃感兴趣，那么我们可以使用非常简单的动态编程循环(在线性时间和恒定内存中)解决此问题.请注意，id从0开始:
If we are only interested in the survivor f(N,K) of a circle of size N and jumps of size K, then we can solve this with a very simple dynamic programming loop (In linear time and constant memory). Note that the ids start from 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
f(N,K) = (f(N-1,K) + K) mod N
可以通过模拟消除过程来解释此关系，并在每次消除后重新分配从0开始的新id.旧索引是具有k个位置的循环移位的新索引.有关此公式的更详细说明，请参见 http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf .
This relation can be explained by simulating the process of elimination, and after each elimination re-assigning new ids starting from 0. The old indices are the new ones with a circular shift of k positions. For a more detailed explanation of this formula, see http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf.
我知道OP会以正确的顺序要求被淘汰项目的 all 个索引.但是，我相信上述见解也可以用于解决此问题.
I know that the OP asks for all the indices of the eliminated items in their correct order. However, I believe that the above insight can be used for solving this as well.
这篇关于从圈子中删除每个"kth"人.找到最后剩下的人的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
