问题标签 [josephus]

我正在尝试用数组列表解决约瑟夫斯问题。我注意到即使我在它被杀死后删除并索引它仍然出现在我的输出中。

为什么应该删除的 2 又出现了？

以下是我当前的输出：

我正在尝试使用 ArrayList 和 for 循环来解决 Josephus 问题。我在我的 circle.size for 循环中创建了一个无限 for 循环，但我无法推断出我的代码的哪一部分导致它发生。

我正在尝试编写一个代码来模拟一个circle拥有一把剑的固定大小的人。最接近当前的“活人”index将被淘汰，剑将传给下一个活人（在被杀死的人之后），依此类推。

我希望它在没有链表的情况下编写。

示例： 一组 3 人： arr[0] = 1, arr[1] = 1, arr[2] = 1

第一回合：

• arr[0] KILLS arr[1] and the sword gets PASSED to arr[2]

第一回合后的元素值：

arr[0] = 1, arr[1] = 0, arr[2] = 1

第二回合：

• arr[2] KILLS arr[0] and stays the last player

第二回合后的元素值：

arr[0] = 0, arr[1] = 0, arr[2] = 1

• arr[2]'s index gets returned by the main function.

我想到的是：

• 大批
• 将所有元素的值设置为1
• 每次循环检查if (1 == arr[i])
• 设置一个标志来确定是杀死还是只是将剑传给这个家伙。
• 返回当前索引，指示这是最后一个活着的玩家的索引。

例如，假设我们组中有 5 个人： [1] [1] [1] [1] [1]

第一轮：

give_sword = 0

i = 0不进入第一个if是因为give_sword不是1。它进入 second if，并使用该函数找到最近的活人findClosestLivingPerson并获取他的索引并将他的值设置为0（==杀死最近的活人）。它设置give_sword为1。

减少players_counter并检查是否只剩下一名玩家。如果不是，则继续循环。

这是我的代码：

编译器说：

在函数'main'中：last_man.c:23:43：警告：没有效果的语句[-Wunused-value] 23 | 对于 (i = 0; i < group_size; (i+1) % group_size)

last_man.c：在函数“findClosestLivingPerson”中：last_man.c:49:42：警告：声明无效 [-Wunused-value] 49 | for (; index < group_size; (index+1) % group_size)

(index+1) % group_size是为了在这个数组中循环。

我有一个问题是约瑟夫斯问题变体。描述如下：

有 m 张卡片，编号从 1 到 m，每张卡片都有一个唯一的编号。卡片分发给围成一圈的 n 个人。请注意m >= n。

然后我们选择坐在位置“p”的人“A”离开圆圈，就像约瑟夫斯问题一样。下一步，我们跳过 p 右边的“k”个人，而 k 是“A”个人拿到的牌的编号，我们做同样的事情，直到圈子里只剩下一个人。

问题给定n个人和m张卡片，我们是否可以选择n张卡片分配给第n个人，使得无论从哪个位置开始（不包括第一个位置），最后生存的人总是第一个圆圈。

例如，m = n = 5，唯一的解是 (4, 1, 5, 3, 2)。

我认为这个问题是一个 np-complete 问题，但我无法证明。任何人都有一个好主意来找到多项式时间解决方案或证明它是 np-hard 吗？

--- 示例解决方案 ---

--- 可能对数学解决方案有帮助 --- 我注意到从长度 9 开始，每个长度的至少一个解决方案都有一个较长的整数序列，该序列减 1。

CSES 问题 Josephus 问题 I 要求我们打印 n 人和 k = 2 时如何选择人的顺序。我在这里找到了一个优雅的解决方案。基本上，代码与此类似：

有人可以解释它为什么起作用吗？

我目前正在使用 java 开发 Josephus 解决方案。不幸的是，我只被允许使用数组（没有 arrayLists 也没有递归）

我在从最后一个位置开始（7 名玩家，从第 2 轮第 7 位开始）以及将循环计数器的增量放在哪里时遇到问题。

你们能帮帮我吗？

我打算使用链表解决 C 中的约瑟夫斯问题，但它不起作用。我已经尝试了多种方法来做到这一点，所以我很困惑。

我有点理解 struct 函数和 typedef，所以我想我在那里没有任何问题（？）。我猜我在主函数中犯了一个错误。

我想为一般约瑟夫斯问题找到最简单的算法，即任何方向的计数。
以组合的“递归列表”算法为基础（Python）。
它适用于积极的转变，并以消极的方式开始，但随后出现问题。

添加几个“if”语句可能会有所帮助，但我不想这样做。

我正在使用循环双向链表创建约瑟夫斯问题。我收到一个属性错误，我认为这是因为我的 current_node（第一个节点）还没有 .prev。

我知道我的第一个节点的 prev 应该指向我的最后一个节点的下一个以创建循环双向链表。

有人可以指导我是否正确识别错误？如果是，我该如何纠正？

如果不是，那么我可以纠正错误的其他方法是什么？

错误

经典的约瑟夫斯问题（n 个人围成一个圆圈，从第 p 个人开始，然后删除每个第 k 个人，找到最后剩下的人的索引）但在这个版本中，每个人还被分配了一个整数（从键盘读取）旁边他们的位置在圈子里。我必须输出分配给最后一个活着的人的整数。

我已经完成了基本算法，但它似乎给了我奇怪的输出，比如当我只输入 2 位数字时，5 位数字。

n=一开始圈子里的人数

p=我们开始计数的人的索引

k=第k个人被移除

我试图通过创建一个向量 v[i] 来解决它，该向量保存分配给每个人的整数。

当 (n>1) 时，对于 i=p，我将 v[i] 之后的所有内容向左移动 1 个空格并减少 n，然后将 k 添加到 i。如果我们通过 n，那么 i 变为 i+kn。