问题标签 [josephus]

我在 Josephus 游戏中遇到了一些问题。我的第一个问题是我不知道如何从每轮淘汰的人左边的人开始数（游戏顺时针方向）。它正确删除，但从被删除人右侧的人开始计数。我的第二个问题是我无法弄清楚如何在每一轮中打印被淘汰的人。大多数情况下，我已经掌握了算法，但我无法弄清楚这些小细节。任何帮助，将不胜感激！

假设 100 个人排成一圈。从第 1 个人数到第 14 个人，将人从圈子中删除。按照计数顺序，再次计数并删除第 14 个人。重复。最后一个站着的人是谁？

我已经尝试了一切来解决这个问题，但它似乎不适用于死循环。

我想用段树来解决 Joseph Flavius 问题。我几乎可以肯定，简单的模拟（即行列表）是O(n^2). 我想要实现的是在特定距离的数组上跳跃，取自段树。换句话说，段树将保留有关已删除元素数量的信息，并从树中获取一些信息将允许在 O(1) 中找到下一个要删除的元素。问题是我不知道如何在段树中存储信息以使其适用于 Joseph Flavius 问题。

每个节点中保留了某种额外的值？但是如何查询下一个元素呢？

约瑟夫斯问题（或约瑟夫斯排列）是一个与某种计数游戏相关的理论问题。

人们围成一圈等待被处决。计数从圆圈中的第一个点开始，并沿顺时针方向围绕圆圈进行。跳过指定人数后，执行下一个人。对剩余的人重复该过程，从下一个人开始，朝相同的方向前进并跳过相同数量的人，直到只剩下一个人并被释放。例如，如果 n=10，则消除顺序为 2、4、6、8、10、3、7、1、9 和 5

最初，我们得到 n，即一开始圈内的人数。牢记上述条件和约束，给出消除顺序。

简而言之，打印死亡模式而不使用任何数据结构，如数组和链表。

根据约瑟夫斯问题，我必须编写一个程序，利用循环列表给出最后一个站立的人的输出。它似乎在大多数情况下都有效，但是，当我进入系列 7（人）1（起始位置），3（杀死计数）时。它在杀戮的中途被扔掉了。（大约当列表是 2357 时）我已经按照数字查看了几次代码，但无法弄清楚为什么在这次迭代中它杀死了 3 而不是 5。

例如，我们有系列 1、2、3、4、5。我们取每 3 个元素 => 3、1、5、2、4（选择的元素不应该保留，当系列不为空时我们可以取）。通过循环双向链表的幼稚实现并不是性能的好主意。你能给我一个建议，哪些数据结构和算法更适用吗？

Advent of Code Day 19的问题具体如下：

编号为 1 到 N 的精灵围成一圈。每个精灵都会带来一份礼物。然后，从第一个精灵开始，他们轮流从左边的精灵那里偷走所有的礼物。一个没有礼物的精灵被从圈子中移除并且不轮流。因此，如果 N = 5，则：

• 精灵 1 带走了精灵 2 的礼物。
• 精灵 2 没有礼物被跳过
• 精灵 3 需要精灵 4 的礼物。
• 精灵 4 没有礼物，也被跳过了。
• 精灵 5 拿走了精灵 1 的两个礼物。
• Elf 1 和 Elf 2 都没有礼物，所以都被跳过了。
• 精灵 3 拿走了精灵 5 的三个礼物，游戏结束。

谁最终得到了 N 的一般情况下的所有礼物？

在解决了这些问题之后，我总是喜欢看别人的解决方案来学习一些新的技巧。我通读的其中一个解决方案是 Peter Norvig 的解决方案，我注意到他提到从列表中删除每个收到礼物的精灵是 O(N^2)。

从经验上讲这是有道理的，因为这基本上就是我所做的，而且我的解决方案非常缓慢，但我认为从列表中删除，假设为链表，是 O(N) （或者特别是 O(N) 迭代到删除点，和 O(1) 用于实际删除）。

我在这里显然缺乏知识，如果有人能帮助我更好地理解这是 O(N^2)，我将不胜感激。如果您要删除，然后在每次删除后，尝试再次从列表的开头搜索下一个精灵，我可以看到会是什么情况，因为在这种情况下，每次删除的成本为 N然后 N 再次搜索下一个精灵，总共 N^2。我所做的是保留我在列表中的位置的计数器，删除一个精灵，然后将计数器迭代到下一个位置。在那种情况下，我预计会产生 N 删除成本，但不会产生索引（也许这是我错的地方，索引成本）。

一个 C++ 程序，将数字从 2、5,8 和 16 转换并输入到 10。我尝试使用 switch case 解决问题，但是 16 的基数给我带来了问题。

我正在用 Python 实现约瑟夫斯圆算法。我对写 prev=Node(0) 和 head=Node(0) 时出现的错误有一点疑问。当我写 head=Node(0) prev=head 时错误被删除。为什么当我写 prev=Node(0) 和 head=Node(0) 时出现错误。

显示错误---而 currentNode.getNext()!= currentNode: AttributeError: 'NoneType' object has no attribute 'getNext'

谢谢你

我的朋友告诉我约瑟夫斯问题，你有很多41人坐在圈子里。人号1有剑，杀右边人，将剑传给下一个人。这种情况一直持续到只剩下一个人活着。我在python中提出了这个解决方案：

但它只对42人有效。我应该怎么做，或者我应该如何更改代码，以便它适用于例如100, 1000圈子中的更多人？

我查看了约瑟夫斯问题并看到了不同的解决方案，但我很好奇我的答案在经过一些小的调整后是否正确，或者我应该从头开始。