递归实现Josephus问题的解释 [英] Explanation for recursive implementation of Josephus problem
问题描述
编辑：n是人数。 k是被淘汰的第k个人。因此，对于k = 2，每第二个人将被淘汰。
n is the number of persons. k is the kth person being eliminated. So for k=2, every 2nd person is getting eliminated.
int josephus(int n, int k)
{
if (n == 1)
return 1;
else
return (josephus(n - 1, k) + k-1) % n + 1;
}
代码非常简单。但是以某种方式我无法理解这个问题（说实话，这有点尴尬）。
The code is as simple as it could be. But somehow I am unable to understand this problem (which is a little embarassing to be honest).
我试图理解的方式是
- 约瑟夫（n ，k）给出大小为n且步长为k的总体的最终解。
- josephus（n，k）如果我们知道josephus（n-1， k）。我认为这是动态编程的最佳子结构属性。
- 我得到我们需要做一个MOD N，以便万一数超过n，它将再次从1.（即确保加法的行为就像我们在盘算一样）。但是为什么我们要添加这个 k-1呢？
主要问题是我们是否知道josephus（n- 1，k），我们如何计算josephus（n，k）的解。我们实际上已经在人口中又增加了一个人，以某种方式增加这个k-1值可以为我提供正确的解决方案（让我们暂时忽略mod）。
The main question is if we know the correct solution of josephus(n-1,k), how are we calculating the solution to josephus(n,k). We have effectively added one more person to the population and somehow adding this k-1 value is giving me the correct solution (let's ignore mod for a moment).
有人可以吗向我解释一下，问题的每个步骤如何保持最优的子结构属性？
Can anyone explain this to me that how is the optimal substructure property holding at each step in the problem?
推荐答案
导致这一问题的关键见解解决方案对我来说很有意义： josephus（n，k）的结果最好不要认为是约瑟夫斯的 number 幸存者，而是约瑟夫斯幸存者编号的 index 。例如，呼叫 josephus（5，2）会告诉您该人的指数（五环之内，该数字最终还可以幸存）。
The key insight that made this solution make sense for me is the following: the result of josephus(n, k) is best not thought of as the number that is the Josephus survivor, but rather as the index of the number that is the Josephus survivor. For example, calling josephus(5, 2) will tell you the index of the person out of a ring of five that ends up surviving.
考虑到这种直觉，让我们通过看一个具体的例子来思考约瑟夫斯问题的工作方式。假设我们想知道 josephus（n，2）。您可以想象我们有n个人这样排列：
With that intuition in mind, let's think about how the Josephus problem works by looking at a concrete example. Suppose we want to know josephus(n, 2). You can imagine we have n people lined up like this:
1 2 3 4 5 ... n
发生的第一件事是人1杀死人2，如下所示：
The first thing that happens is that person 1 kills person 2, as shown here:
1 X 3 4 5 ... n
现在，我们剩下一个以下形式的子问题：剩下n-1个人，其他每个人都将被杀死，第一个要进行刺伤的人是3个人。的话，我们留下了一群像这样的人：
Now, we're left with a subproblem of the following form: there are n-1 people remaining, every other person is going to be killed, and the first person who will be doing the stabbing is person 3. In other words, we're left with a ring of people shaped like this:
3 4 5 ... n 1
，其中k =2。现在，假设我们递归调用 josephus（n -1、2），因为我们有n-1个人。这将返回在n-1人的行中幸存者的 index 。鉴于我们拥有将要生存的人的索引，并且我们也知道起始人是谁，因此我们可以确定将剩下哪个人。
with k = 2. Now, imagine that we make a recursive call to josephus(n - 1, 2), since we have n - 1 people. This will give back the index of who survives in a line of n - 1 people. Given that we have the index of the person who will survive, and we also know who the starting person is, we can determine which person will be left. Here's how we'll do it.
此行的起始人员是紧随上次执行人员之后的人员。这将是第3个人。幸存者在四口之环中的1索引位置由 josephus（n-1，2）给出。因此，我们可以向前走 josephus（n-1，2）-1 位置，并在必要时环绕圆环以到达最终位置。换句话说，幸存者的位置是
The starting person in this line is the person who comes right after the person who was last executed. This will be person 3. The 1-indexed position of the survivor in the ring of four people is given by josephus(n - 1, 2). We can therefore walk forward josephus(n - 1, 2) - 1 positions, wrapping around the ring if necessary, to get to our final position. In other words, the survivor is given by position
(3 + josephus(n - 1, 2) - 1) % n
但是上述公式存在问题。如果我们确实在使用单索引，那么如果最后的幸存者在位置n处会发生什么？在这种情况下，我们会意外地返回位置0作为答案，但我们确实想要位置n。为了解决此问题，我们将使用一个技巧，使用mod环绕一次索引：我们将内部数量（一个索引位置）减去1以获得零索引位置。我们将数量修改为n，以获得零索引位置。最后，我们将加回一个，以获得环绕一个索引的位置。看起来像这样：
There's a problem with this above formula, though. If we are indeed using one-indexing, what happens if the final survivor is at position n? In that case, we'd accidentally get back position 0 as our answer, but we really want position n. As a fix to this, we'll use a trick for using mod to wrap around with one-indexing: we'll take the inside quantity (the one-indexed position) and subtract one to get the zero-indexed position. We'll mod that quantity by n to get the zero-indexed position wrapped around. Finally, we'll add back one to get the one-indexed position, wrapped around. That looks like this:
(3 + josephus(n - 1, 2) - 2) % n + 1
因此，这里的-2项来自两个独立的-1：第一个-1是因为 josephus（n-1，2）返回一个索引索引，因此要按正确的位置前进，我们必须采取 josephus（n-1，2 ）-1 向前移动。第二个-1来自以下事实：我们使用的是单索引而不是零索引。
The -2 term here therefore comes from two independent -1's: the first -1 is because josephus(n - 1, 2) returns a one-indexed index, so to step forward by the right number of positions we have to take josephus(n - 1, 2) - 1 steps forward. The second -1 comes from the fact that we're using one-indexing rather than zero-indexing.
让我们将其推广为适用于任意k，而不仅仅是k = 2.假设我们想知道 josephus（n，k）。在这种情况下，人1将刺伤人k，给我们留下这样的数组：
Let's generalize this to work for arbitrary k, not just k = 2. Suppose we want to know josephus(n, k). In that case, person 1 will stab person k, leaving us with an array like this:
1 2 3 ... k-1 X k+1 ... n
我们现在基本上需要解决人k处的一个子问题+1首先出现：
We now essentially need to solve a subproblem where person k+1 comes first:
k+1 k+2 ... n 1 2 ... k-1
所以我们计算 josephus（n-1，k）得到一个由n个索引组成的n-1人的幸存者，然后向前迈进许多步：
So we compute josephus(n - 1, k) to get the one-indexed survivor of a ring of n - 1 people, then shift forward by that many steps:
(k+1 + josephus(n - 1, k) - 1)
我们需要担心这种情况
(k+1 + josephus(n - 1, k) - 1) % n
但是，我们是单索引的，因此我们需要使用技巧从内部数量中减去1，然后在末尾加1：
However, we're one-indexed, so we need to use the trick of subtracting 1 from the inside quantity and then adding 1 at the end:
(k+1 + josephus(n - 1, k) - 2) % n + 1
简化为
(k-1 + josephus(n - 1, k)) % n + 1
等于
(josephus(n - 1, k) + k-1) % n + 1
与解决方案代码相同。
总而言之：k-1项来自于位置k + 1，加上 josephus（n-1，k）-1 转发适当的金额，然后减去1，最后再添加一个，以进行正确的环绕操作。
To summarize: the k-1 term comes from starting at position k+1, adding in josephus(n - 1, k) - 1 to shift forward the appropriate amount, then subtracting one and adding one back in at the end to do the correct wraparound.
希望这会有所帮助！
这篇关于递归实现Josephus问题的解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
