问题标签 [josephus]

所以，我试着看看我是否可以编写代码来解决 Python 中的约瑟夫斯问题，供 n 人（在圆圈中）使用。

我是业余爱好者，请多多包涵。

这是我想出的代码，但它有一些问题。

首先，它给出了一个 TypeError 并说在 'int' 和 'str' 的实例之间不支持 '<'。

其次，如果我更换

和

然后它给出 TypeError: 'int' object is not callable。

此外，考虑到我使用了一个奇怪的 for 循环并且它会为每个值返回解决方案，我似乎无法理解如何让程序返回 n = 100（即 73）的真正解决方案2^i 一直小于 n 直到 2^10

输出与我预期的不同。例如，当n=5 时，答案是 3，但我得到 11 的输出。

在进行代码大战训练时，我遇到了关于约瑟夫排列的挑战，我尝试先在纸上解决它，然后再将其转换为代码。

问题如下：“创建一个返回 Josephus 排列的函数，将要排列的初始数组/项目列表作为参数，就好像它们在一个圆圈中一样，并计算每 k 个位置，直到没有剩余。”

我的主要想法是：

• 有一个辅助数组来保持响应

• 使用两个迭代器：

  • i：跟踪给定数组中的当前索引
  • k：跟踪排列的步骤

• 将 i 初始化为 0，将 k 初始化为 1

• 当原始数组只剩下一个元素时：
  • 将元素推送到输出数组
• 每当 i 不是数组的最后一个索引时：
  • 如果 k = 步长：
    • 从原数组中取出元素，推入输出数组，最后替换k = 1
  • 如果 k != 步：
    • 增加 i 和 k
• 当 i 是原始数组的最后一个索引时（并且该数组有多个元素）：
  • 如果 k = 步长：
    • 从原数组中取出元素，压入输出数组，替换k = 1，设置i = 0
  • 如果 k != 步：
    • 设置 i = 0 并增加 k

这可行，但效率不高，当我在运行示例测试中运行它时，我得到 5 个示例测试已通过，但它还包括一个 STDERR：执行超时（12000 毫秒）。

样本测试如下：

我的问题是，我怎样才能提高效率？

是我使用的算法错误还是实现？

一条评论提到了两件事：

• push() 非常慢，这是我的可能性之一（错误的数据结构）

• 建议查看递归（这更让我怀疑算法）。不过，我并没有真正看到如何进行递归。

在此先感谢您的帮助！

我正在尝试为约瑟夫斯问题编写一些代码，但我不断收到一个奇怪的错误。我的代码如下所示：

当我尝试运行它时，它给了我这个错误：

ValueError Traceback（最近一次调用最后一次）

在 （）

---> 14 variabletest = type(math.log(newnumber,power))

ValueError：数学域错误

有任何想法吗？我不知道如何解决这个问题。

该函数的问题在于，在调用它 1 次后，它不能正常工作。例如，对于 k = 4，并且树的大小 n = 7，调用时它应该首先返回值为 4 的节点，然后返回 5，而实际上它返回值为 4 和 NULL 指针的节点。找不到解决方案。

我已经为这个函数苦苦挣扎了很长一段时间，它将 node_t *root 作为我们树的根，将 k 作为第 k 个元素。我们的结构看起来像它。

我们的函数还应该在从根节点到指定节点的每个节点上减少 t 并将 isVisited 更改为 true，因此我们不会再次访问它。

示例我们的 BCT 是如何从linked_list 创建的：

Josephus 可以用以下算法求解：

不过，我也想知道游戏中第i个被杀的人是谁。例如，n=10，k=2，第一个被杀的人就是第二个。我怎样才能得到这个答案？无论如何我可以使用上面的算法找到它吗？

有没有办法在O(n.logn)中打印出约瑟夫斯问题中的删除顺序？

例子

与人数是n = 7和跳过的人数k = 3。淘汰顺序为：

输入：

输出：

如果你不知道这个问题 问题描述：有n个人围成一圈（顺时针从1到n编号）等待被处决。计数从圆圈中的点 1 开始，并沿固定方向（顺时针）围绕圆圈进行。在每个步骤中，都会跳过一定数量的人并执行下一个人。消除围绕圆圈进行（随着被处决的人被移除，圆圈变得越来越小），直到只剩下最后一个人，他被赋予了自由。给定总人数 n 和数字 k，表示跳过 k-1 人，循环杀死第 k 人。任务是选择初始圈子中的位置，以便您是最后一个并生存下来。考虑如果 n = 5 且 k = 2，则安全位置为 3。首先，位置2的人被杀，然后位置4的人被杀，然后位置1的人被杀。最后，位置 5 的人被杀死。所以位置 3 的人活了下来。

我正在尝试使用循环链表来解决约瑟夫斯问题。但是在创建函数中，我得到了一个关于指向链表节点的 NULL 指针的分段错误。谁能解释为什么会出现分段错误？谢谢你！

在约瑟夫斯问题中，我们有 n 个人，从 1 到 n 编号。每回合你跳过k个人并杀死下一个。通常你打印最后一个幸存者，我对受害者的顺序感兴趣。我尝试根据网上找到的建议使用循环链表来做到这一点。当输入像 n=123456 这样大时，我的算法仍然不够快；k=1000000000。我的时间目标是不到一秒。我认为时间复杂度是 O(nk)，因为所有链表操作都是 O(1)，并且对于每个人，我必须打印它们的值并可能移动 k 步。我是否应该找到一些不同的策略我是否缺少一些明显的优化技术？