blocks|key|3799523|text|对我来说，让这个解决方案有意义的关键洞察力是：josephus(n,+k)的结果最好不要被认为是约瑟夫斯幸存者的数字，而是作为约瑟夫斯幸存者的数字的索引。例如，打电话给josephus(5,+2)会告诉你五个人中的一个人的索引，这个人最终幸存了下来。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|3799524|考虑到这种直觉，让我们看看约瑟夫斯问题是如何工作的，通过一个具体的例子。假设我们想知道josephus(n,+2)。你可以想象我们有像这样排队的人：|3799525|1+2+3+4+5+...+n|code-block|syntax|javascript|3799526|发生的第一件事是，person+1杀死2个人，如下所示：|3799527|1+X+3+4+5+...+n|3799528|现在，我们有一个子问题，形式如下:还有n个人还活着，每个其他人都会被杀，第一个被刺伤的人是3个人。换句话说，我们剩下一个像这样形状的人环：|3799529|3+4+5+...+n+1|3799530|现在，假设我们对josephus(n+-+1,+2)进行递归调用，因为我们有n-1人。这将返回谁在n-1人中幸存的指数。考虑到我们有生存的人的指数，而且我们也知道谁是开始的人，我们可以决定谁会被留下。这就是我们要做的。|3799531|这一行中的起跑者是在最后一次被处决的人之后出现的人。这将是人3。幸存者在四人圈的1索引的位置是由josephus(n+-+1,+2)给出的。因此，我们可以向前走josephus(n+-+1,+2)+-+1的位置，如果有必要的话，绕着圆环走到最后的位置。换句话说，幸存者是按位置分配的。|3799532|+(3+%2B+josephus(n+-+1,+2)+-+1)+%25+n|3799533|不过，上面的公式有个问题。如果我们确实使用了一个索引，那么如果最后的幸存者位于n位置会发生什么呢？在这种情况下，我们会意外地返回位置0作为我们的答案，但我们真的想要位置n。作为一个修正，我们将使用一个技巧使用mod来用一个索引来环绕:我们将取里面的数量(一个索引的位置)，然后减去一个得到零索引的位置。我们将这个数量乘以n，以得到零索引的位置。最后，我们将添加一个，以得到一个索引的位置，包装。看起来是这样的：|3799534|(3+%2B+josephus(n+-+1,+2)+-+2)+%25+n+%2B+1|3799535|因此，这里的-2项来自两个独立的-1+:第一个-1是因为josephus(n+-+1,+2)返回一个索引索引，所以要按正确的位置前进，我们必须采取josephus(n+-+1,+2)+-+1前进的步骤。第二个-1是因为我们使用的是一个索引而不是零索引。|3799536|让我们把它推广到任意k上，而不仅仅是k=+2，假设我们想知道josephus(n,+k)。在这种情况下，person+1会刺伤person+k，留给我们这样一个数组：|3799537|1+2+3+...+k-1+X+k%2B1+...+n|3799538|我们现在基本上需要解决一个子问题，即person+k%2B1优先：|3799539|k%2B1+k%2B2+...+n+1+2+...+k-1|3799540|因此，我们计算josephus(n+-+1,+k)，得到一个n-1人环的单索引幸存者，然后通过许多步骤向前移动：|3799541|(k%2B1+%2B+josephus(n+-+1,+k)+-+1)|3799542|我们需要担心这样的情况，所以我们需要用n来表示：|3799543|(k%2B1+%2B+josephus(n+-+1,+k)+-+1)+%25+n|3799544|然而，我们只有一个索引，所以我们需要使用从内部数量减去1，然后在末尾添加1的技巧：|3799545|(k%2B1+%2B+josephus(n+-+1,+k)+-+2)+%25+n+%2B+1|3799546|它简化为|3799547|(k-1+%2B+josephus(n+-+1,+k))+%25+n+%2B+1|3799548|这相当于|3799549|(josephus(n+-+1,+k)+%2B+k-1)+%25+n+%2B+1|3799550|就像解决方案代码一样。|3799551|概括地说:+k-1项来自于从k%2B1位置开始，加上josephus(n+-+1,+k)+-+1以向前移动适当的数量，然后减去一个，在末尾再加上一个以完成正确的概括。|3799552|希望这能有所帮助！|3799553|entityMap^0|N|E|2C|E|0|17|E|0|0|0|0|0|0|8|I|0|1C|I|28|M|0|0|0|0|S|I|21|M|0|U|E|0|0|0|0|7|I|0|0|0|0|0|0|0|0|0|0|0|O|M|0|0^^$0|@$1|2|3|4|5|6|7|26|8|@$9|27|A|28|B|C]|$9|29|A|2A|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|2B|8|@$9|2C|A|2D|B|C]]|D|@]|E|$]]|$1|H|3|I|5|J|7|2E|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|2F|8|@]|D|@]|E|$]]|$1|O|3|P|5|J|7|2G|8|@]|D|@]|E|$K|L]]|$1|Q|3|R|5|6|7|2H|8|@]|D|@]|E|$]]|$1|S|3|T|5|J|7|2I|8|@]|D|@]|E|$K|L]]|$1|U|3|V|5|6|7|2J|8|@$9|2K|A|2L|B|C]]|D|@]|E|$]]|$1|W|3|X|5|6|7|2M|8|@$9|2N|A|2O|B|C]|$9|2P|A|2Q|B|C]]|D|@]|E|$]]|$1|Y|3|Z|5|J|7|2R|8|@]|D|@]|E|$K|L]]|$1|10|3|11|5|6|7|2S|8|@]|D|@]|E|$]]|$1|12|3|13|5|J|7|2T|8|@]|D|@]|E|$K|L]]|$1|14|3|15|5|6|7|2U|8|@$9|2V|A|2W|B|C]|$9|2X|A|2Y|B|C]]|D|@]|E|$]]|$1|16|3|17|5|6|7|2Z|8|@$9|30|A|31|B|C]]|D|@]|E|$]]|$1|18|3|19|5|J|7|32|8|@]|D|@]|E|$K|L]]|$1|1A|3|1B|5|6|7|33|8|@]|D|@]|E|$]]|$1|1C|3|1D|5|J|7|34|8|@]|D|@]|E|$K|L]]|$1|1E|3|1F|5|6|7|35|8|@$9|36|A|37|B|C]]|D|@]|E|$]]|$1|1G|3|1H|5|J|7|38|8|@]|D|@]|E|$K|L]]|$1|1I|3|1J|5|6|7|39|8|@]|D|@]|E|$]]|$1|1K|3|1L|5|J|7|3A|8|@]|D|@]|E|$K|L]]|$1|1M|3|1N|5|6|7|3B|8|@]|D|@]|E|$]]|$1|1O|3|1P|5|J|7|3C|8|@]|D|@]|E|$K|L]]|$1|1Q|3|1R|5|6|7|3D|8|@]|D|@]|E|$]]|$1|1S|3|1T|5|J|7|3E|8|@]|D|@]|E|$K|L]]|$1|1U|3|1V|5|6|7|3F|8|@]|D|@]|E|$]]|$1|1W|3|1X|5|J|7|3G|8|@]|D|@]|E|$K|L]]|$1|1Y|3|1Z|5|6|7|3H|8|@]|D|@]|E|$]]|$1|20|3|21|5|6|7|3I|8|@$9|3J|A|3K|B|C]]|D|@]|E|$]]|$1|22|3|23|5|6|7|3L|8|@]|D|@]|E|$]]|$1|24|3|-4|5|6|7|3M|8|@]|D|@]|E|$]]]|25|$]]

The key insight that made this solution make sense for me is the following: the result of <code>josephus(n, k)</code> 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 <code>josephus(5, 2)</code> will tell you the index of the person out of a ring of five that ends up surviving.

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 <code>josephus(n, 2)</code>. You can imagine we have n people lined up like this:

<pre><code>1 2 3 4 5 ... n
</code></pre>

The first thing that happens is that person 1 kills person 2, as shown here:

<pre><code>1 X 3 4 5 ... n
</code></pre>

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:

<pre><code>3 4 5 ... n 1
</code></pre>

with k = 2. Now, imagine that we make a recursive call to <code>josephus(n - 1, 2)</code>, 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.

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 <code>josephus(n - 1, 2)</code>. We can therefore walk forward <code>josephus(n - 1, 2) - 1</code> positions, wrapping around the ring if necessary, to get to our final position. In other words, the survivor is given by position

<pre><code> (3 + josephus(n - 1, 2) - 1) % n
</code></pre>

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:

<pre><code>(3 + josephus(n - 1, 2) - 2) % n + 1
</code></pre>

The -2 term here therefore comes from two independent -1's: the first -1 is because <code>josephus(n - 1, 2)</code> returns a one-indexed index, so to step forward by the right number of positions we have to take <code>josephus(n - 1, 2) - 1</code> steps forward. The second -1 comes from the fact that we're using one-indexing rather than zero-indexing.

Let's generalize this to work for arbitrary k, not just k = 2. Suppose we want to know <code>josephus(n, k)</code>. In that case, person 1 will stab person k, leaving us with an array like this:

<pre><code>1 2 3 ... k-1 X k+1 ... n
</code></pre>

We now essentially need to solve a subproblem where person k+1 comes first:

<pre><code>k+1 k+2 ... n 1 2 ... k-1
</code></pre>

So we compute <code>josephus(n - 1, k)</code> to get the one-indexed survivor of a ring of n - 1 people, then shift forward by that many steps:

<pre><code>(k+1 + josephus(n - 1, k) - 1)
</code></pre>

We need to worry about the case where we wrap around, so we need to mod by n:

<pre><code>(k+1 + josephus(n - 1, k) - 1) % n
</code></pre>

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:

<pre><code>(k+1 + josephus(n - 1, k) - 2) % n + 1
</code></pre>

which simplifies to

<pre><code>(k-1 + josephus(n - 1, k)) % n + 1
</code></pre>

which is equivalent to

<pre><code>(josephus(n - 1, k) + k-1) % n + 1
</code></pre>

as in the solution code.

To summarize: the k-1 term comes from starting at position k+1, adding in <code>josephus(n - 1, k) - 1</code> to shift forward the appropriate amount, then subtracting one and adding one back in at the end to do the correct wraparound.

Hope this helps!

blocks|key|3799584|text|我们需要调整k-1的位置，因为在kth被移除后，开始位置已经被k移动(第一个k-1被旋转到末端)。也就是说，初始位置pos变成pos。如果k=+3，(n-1，k)返回pos+=+2，则原始位置应为pos+%2Bk=+5。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3799585|我们在公式中用k-1代替k，因为我们必须用mod(n)：k=+(k-1)+%25n%2B1。|3799586|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

We need to adjust the position by k-1 simply because the starting position has been shift by k after the kth is removed (and the first k-1 are rotated to the end). That is, initial position pos becomes pos-k. If k = 3, (n-1,k) returned pos = 2, the original position should be pos + k = 5.
We replace k with k-1 in the formula because we have to mod(n): k = (k-1) % n + 1

EDIT: n is the number of persons. k is the kth person being eliminated. So for k=2, every 2nd person is getting eliminated.

<pre><code>int josephus(int n, int k)
{
 if (n == 1)
 return 1;
else
 return (josephus(n - 1, k) + k-1) % n + 1;
}
</code></pre>

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). 

The way I am trying to understand it is, 

<ol>
<li>josephus(n,k) gives the final solution for a population of size n and step size k.</li>
<li>josephus(n,k) can be calculated if we know the solution for josephus(n-1,k). That is in my opinion "optimal substructure property" of dynamic programming.</li>
<li>I get that we need to do a MOD N so that in case number goes past n, it will again start counting from 1. (i.e. ensure that addition behaves like we are counting in a circle). But why did we add this "k-1"?</li>
</ol>

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?

Explanation for recursive implementation of Josephus problem

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

编辑:n是人数。K是被淘汰的kth人员。因此，对于k=2，每2个人就会被淘汰。int josephus(int n, int k){ if (n == 1)  return 1;else   return (josephus(n - 1, k) + k-1) % n + 1;}代码尽可能简单。但不知何故，我无法理解这个...

问约瑟夫斯问题递归实现的解释
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问约瑟夫斯问题递归实现的解释EN