问题标签 [josephus]

我最近偶然发现了一个论坛，声称约瑟夫斯问题可以用数据结构在 O(n) 中解决。这里明确的选择是循环链表，但我声称它只能在 O(kn) 或 O(n^2) 中完成，除非你按照维基百科的数学递归/迭代约瑟夫斯算法。首先，循环链表具有以下属性：搜索 O(n)、删除 O(1)、追加 O(1)。这假设 delete 是给定的节点并且 append 正在替换头部或尾部。

如果我们有一个循环的节点列表，我们可以从起点找到要删除的节点，如下所示：

n = 6 个节点

k = 删除每第三个节点

起点：节点 #0

节点：0、1、2、3、4、5

我们可以通过 (k + StartingPoint - 1) % n 计算要删除的节点。对于 startpoint = 0，我们有 (3 + 0 - 1) % 6 = 2。现在，3 将是我们的起点。(3 + 3 - 1) % 5 = 0，当移位时是我们原来的 5 节点（即，由于原来的 2 已经消失，数字现在将是 0,1,2,3,4）。这基本上就是数学版本的工作原理。对于链表，我们可以类似地推导出哪个节点需要删除。问题是我们必须前往这个节点。链表有 O(n) 搜索，这是一个问题。所以我们遍历这个节点，删除它，现在我们有n = n-1。我们找到下一个索引，进行 O(n) 搜索，得到 n = n_original - 2。这变为 n + (n-1) + (n-2) + ... = O(n^2)。

如果我们有一个双向循环列表，那么如果节点离我们后面更近，我们就不必一路走来走去。尽管如此，如果 k 小于 n，这仍然是 O(k) 搜索，如果 k 大于 n，则搜索 O(n)你只需要把 k 移开，你就不会到达你开始的地方）。

无论如何，我的观点是我看不出你如何通过 O(n) 中的数据结构来做到这一点。维基百科上的解决方案是 O(n) 中非常优雅的数学方法，它显示了递归的力量（纯粹通过调用堆栈来跟踪旧起点等），但是当删除实际对象时似乎不可能得到 O( n)。我想展示我试图解决这个问题的尝试，而不仅仅是公然问，那么有没有人知道在 O(n) 中使用一些数据结构来做到这一点的方法？谢谢！

所以这是给出的问题。

你在一个有 100 把椅子的房间里。椅子按从 1 到 100 的顺序编号。

在某个时间点，1 号椅子上的人将被要求离开。2 号椅子上的人将被跳过，3 号椅子上的人将被要求离开。这种跳过一个人并要求下一个人离开的模式将继续围绕圆圈进行，直到剩下一个人，即幸存者。

这就是我想出的答案。我相信这是正确的答案，我在纸上也做了大约 10 次，每次都得出 74 个。这是一个技巧问题还是什么？因为我不知道从这里做什么。

这是 jsfiddle http://jsfiddle.net/cQUaH/

我想在给定的位置和人数之后找到下一个幸存者。

我只需要用幸存位置的确切数字替换最后一位。该程序将运行直到找到幸存者，我只是不知道如何给出这个位置作为答案，因为现在一切都是真假。谢谢！

我正在尝试解决约瑟夫斯问题，但我不允许使用其他人的代码片段。考虑到这一点，我的代码中有 27 个错误，但不知道如何修复它。你能不能向我解释为什么它不能编译。我想看看我的逻辑是否有缺陷，但我无法测试它，因为它不会编译。任何其他提示都非常受欢迎！这是我的代码：

约瑟夫斯问题的这种实现在哪里不足？对于那些不熟悉约瑟夫斯问题的人，我们的目标是从循环链表中删除每 3 个条目，直到只剩下一个。在此示例中，我将删除每个“mth”值。

我总是以列表的最后一个数字作为答案。我知道这是不对的。

我一直在处理约瑟夫斯问题（作业的另一部分），我们应该做的是给两个变量m和n. m代表它开始的玩家，n代表玩家的数量。我在弄清楚将m变量放在哪里时遇到问题，以便程序在正确的播放器上启动并跳过适当数量的空格。

因此，如果m是 2 并且有 6 个玩家，它将从玩家 2 开始，传给玩家 3，消除玩家 3 并转到玩家 4，传给玩家 5 并消除他们，依此类推，直到剩下一名玩家。这是我希望得到的输出：

相反，使用我拥有的代码，我得到

int i = 1; i <= n; i++我有用 , 替换的想法，int i = m; i <= n; i++从i正确的数字开始，但这给了我：

我也知道为什么它只增加了 5 名玩家，但我不确定m可以去哪里添加正确数量的玩家。任何想法/提示将不胜感激。

我知道模数给出了余数，而这段代码将给出约瑟夫斯问题的幸存者。我注意到一种模式，当 n mod k = 0 时，起始计数点从圆圈的最开始开始，而当 n mod k = 1 时，紧接在圆圈开始之前的人在该循环中幸存下来.

我只是不明白这个递归如何使用模数来找到最后一个站着的人，以及 josephus(n-1,k) 实际指的是什么。它是指最后一个被处决的人还是特定回合的最后一个幸存者？

以下代码中使用了哪个 ADT，您如何得出这个结论？我有一种预感，它是一个循环链表，但不知道为什么。

我在检查括号字符串是否平衡的算法时遇到了一些问题。我必须从文本文件中获取输入并在另一个文本文件中显示输出。我遇到了这个算法的问题。请帮我找出问题

我创建了一个 CircularLinkedList 类，而不是使用 util LinkedList 类。该问题基于约瑟夫斯问题，指出对于 20 人的圈子，每 12 人将被杀死，直到确定幸存者将站在哪个位置（使用迭代器）。我对如何使用 Iterator 来解决这个问题感到困惑，因为我使用的是我自己的类而不是 LinkedList，它已经有一个 iterator() 方法，因此我可以像这样声明一个 Iterator：

我不知道如何编写自己的 Iterator 方法，而且我觉得我必须过度思考这个问题。任何帮助表示赞赏！如果可以清除我忘记提及的任何内容，我可以发布我的代码

我仍然坚持这一点，所以我想我会发布我的代码，看看是否有人可以提供帮助。很多，所以我很抱歉。

Itr 类（迭代器）

约瑟夫级

CircularLinkedList 类

我从在线 Itr 类中的 next() 方法中得到 NullPointerException

我在 CircularLinkedList 类中做错了什么，因为它实际上不是循环的，还是我的驱动程序/Itr 类有问题？在这一点上，我有点迷路了。任何帮助表示赞赏。