问题标签 [josephus]

我正在尝试使用 java 中的队列来解决 Josephus 问题。输入必须是名称列表（字符串）和整数 k 或马铃薯已通过队列的次数。我需要测试 4 个不同的输入。这就是我到目前为止所拥有的，我从一些随机教程中获得了帮助，但不确定要对此进行编辑以使其正常工作。

这不起作用..有人可以提供建议吗？

这是约瑟夫斯问题的一种解决方案（人们围成一圈，其他人都被杀死，直到只剩下一个人）：

但是，如果我们不是跳过所有其他人，而是增加跳过的人数，该怎么办？也就是说，如果10个人围成一圈，则依次杀死1、3、6、10等人。我认为修改会出现在i = i + 2for 循环中，但我不确定。

我在纸上算出来了，这是消除的顺序，其中星号表示要删除的数字：

想法？

编辑：尝试了对 for 循环的这种修改：

这不起作用，因为在 j = 2 的初始传递之后，内部循环已经将列表缩小到一个候选者，因此外部循环永远不会完成。

我正在做一个班级作业：

约瑟夫问题。在古代约瑟夫斯问题中，N 人处于水深火热之中，同意以下策略来减少人口。他们将自己排成一个圆圈（从 0 到 N???1 的位置）并绕着圆圈前进，消除第 M 个人，直到只剩下一个人。传说约瑟夫斯为了避免被淘汰而想出了坐在哪里。编写一个队列客户端 Josephus.java，它从命令行获取 M 和 N，并打印出人员被淘汰的顺序（从而显示 Josephus 在圆圈中的位置）。

我的代码如下：

当我在 NetBeans 中运行它时，它给我的错误是：

队列是抽象的；无法实例化

入队：找不到符号

出队：找不到符号

StdOut：找不到符号

我认为通过导入 java.util.Queue 将使队列工作，对于 StdOut，我确实下载了一个 stdlib.jar 以添加到包含 StdOut 的项目库中，我认为这会起作用。

如果我的代码有问题或我需要做的任何其他事情，我将非常感谢您的帮助。此外，作为参考并查看我从哪里获得 stdlib.jar，这里是教科书网站的链接，该链接来自该问题的来源：http ://algs4.cs.princeton.edu/13stacks/ （约瑟夫斯问题是＃ 37 下的“创意问题部分”接近尾声。

我似乎无法弄清楚为什么我不断收到此错误！这是我第一次处理队列。我确信解决方案很简单，我可能缺少一些基本的东西。非常感谢任何指导/帮助：

这段代码的原始提示如下：约瑟夫问题。在古代约瑟夫斯问题中，N 人处于水深火热之中，同意以下策略来减少人口。他们把自己排成一个圆圈（从 0 到 N-1 的位置）并绕着圆圈前进，淘汰第 M 个人，直到只剩下一个人。传说约瑟夫斯为了避免被淘汰而想出了坐在哪里。编写一个队列客户端 Josephus，它从命令行获取 N 和 M，并打印出人员被淘汰的顺序（从而显示 Josephus 在圆圈中的位置）。

http://en.wikipedia.org/wiki/Josephus_problem 用户可以选择圈子里有多少人。用户可以选择每个人的价值。用户可以选择人员死亡的计数。前任。用户选择5人，每5人死亡。

我在想类似的东西-用户选择人数前- 50 PeopleArray 变成 PeopleArray[50]

用户在 PeopleArray[50] 中选择元素的值 他们必须为 50 个元素键入 50 个值

死亡用户选择了 3，所以每三个人都会死，我将如何从数组中删除该数字。

问题^-不确定如何使用数组执行上述操作

我正在尝试运行此代码，但该行出了点问题：

有人能帮助我吗？

太感谢了！

编辑：我似乎至少已经解决了错误，并更新了代码。但是，数学似乎仍然没有解决。有任何想法吗？

简而言之，我正在尝试用 C++ 编写一个程序，它会提示用户输入初始圆圈中的人数，然后告诉他们如果k（计算的人数在被执行之前）= 3。

我有我认为正确的想法，但是如果我将k输入为 1、2 或 5 以外的任何值，则会收到错误“调试断言失败”和“表达式：向量擦除迭代器超出范围”。

所以我正在阅读使用数据结构 Python 解决问题，作者实现了一个队列来模拟著名的 Hot Pocket/Josephus 执行问题。但是，我相信这个实现是不正确的，因为无论我尝试了多少次，程序计算的最后一个幸存者都与我的计算不匹配。例如，对于输入 ([0,1,2,3,4],2))，输出不应该是 3 而不是 1 吗？（因为它首先消除了 2，所以按照模式，顺序执行应该是 2,4,1,0,3 使 3 成为最后的幸存者。）但程序给出的输出为 1。

这是完整的实现：

那么我做错了什么？任何帮助表示赞赏。提前致谢！

我正在阅读约瑟夫斯问题的算法。

我遇到了以下算法：

我无法理解它的逻辑。假设 n=5 和 k=2。

任何人都可以通过举例来解释这一点吗？

编辑：n 是人数。k 是第 k 个被淘汰的人。所以对于 k=2，每 2 个人都会被淘汰。

代码尽可能简单。但不知何故，我无法理解这个问题（说实话有点尴尬）。

我试图理解它的方式是，

1. josephus(n,k) 给出大小为 n 且步长为 k 的种群的最终解。
2. 如果我们知道 josephus(n-1,k) 的解，就可以计算出 josephus(n,k)。在我看来，这就是动态规划的“最佳子结构属性”。
3. 我知道我们需要做一个 MOD N 以便在数字超过 n 的情况下，它将再次从 1 开始计数。（即确保加法的行为就像我们在一个圆圈中计数一样）。但是为什么我们要添加这个“k-1”呢？

主要问题是如果我们知道 josephus(n-1,k) 的正确解，我们如何计算 josephus(n,k) 的解。我们已经有效地向人口中增加了一个人，并且以某种方式添加这个 k-1 值给了我正确的解决方案（让我们暂时忽略 mod）。

谁能向我解释一下，在问题的每一步中，最优子结构属性如何保持？