问题标签 [josephus]

作为最近的一份工作申请的一部分，我被要求编写一个解决这个问题的代码。

鉴于，

• n = 围成一圈的人数。
• k = 每次计数的人数

每个人都有一个唯一的（递增的）id。从第一个人（最低 id）开始，他们从 1 开始数到 k。

然后，k 处的人被移除，圆圈闭合。下一个剩余的人（在被淘汰的人之后）从 1 开始重新计数。这个过程重复进行，直到只剩下一个人，即获胜者。

解决方案必须提供：

• 每个人的 ID，按照他们从圈子中移除的顺序排列
• 获胜者的 id。

性能限制：

• 使用尽可能少的内存。
• 使解决方案尽可能快地运行。

我记得几年前在我的 CS 课程中做过类似的事情，但在这次测试时无法回忆起细节。我现在意识到这是一个众所周知的经典问题，有多种解决方案。（我不会提到它的名字，因为有些人可能只是“维基百科”一个答案）。

我已经提交了我的解决方案，所以我绝对不会找人来为我回答。一旦/如果其他人提供了一些答案，我将稍后提供。

我提出这个问题的主要目的是看看我的解决方案与其他解决方案的要求和限制相比如何。

（请仔细注意要求，因为我认为它们可能会使某些“经典”解决方案无效。）

所以这是维基上的约瑟夫斯问题。我遇到的问题是它的线性变化，但为了清楚起见，我将重申整个问题。

（数字=自然数）

有一个过程以下列方式消除数字：

你也会得到一个号码K，你必须确认这个号码K是否能在淘汰赛中幸存下来。

例如（假设索引从 0 开始）

正如我们所看到的，2、4、6safe在此步骤之后，因为该过程将选择越来越高的值进行消除。

所以再一次，给定一个K你如何确定 if Kwill be safe？

Robert Sedwick 的算法，有人提到链表可以使用数组来表示，在下面的链接

http://flylib.com/books/en/3.55.1.34/1/

图 3.8，如果从我的理解中删除了 5，则在删除 val 5 时，下一个 4 应该更改为索引 6，因为我们将在第 4 项的数字被删除，下一个 val 3 被更改。我没有遵循该图的逻辑。任何人都可以帮助我。

谢谢！

上周我参加了 Facebook Hacker Cup 的第 1b 轮比赛。

问题之一基本上是约瑟夫斯问题

我之前研究过约瑟夫斯问题作为一个离散数学问题，所以我基本上了解如何获得递归：

但这在 Facebook 黑客杯中不起作用，因为 n 的最大值是 10^12。k 的 mak 值为 10^4。

Wikipedia 提到了一种当 k 很小而 n 很大时的方法。基本上从一轮中删除人员，然后重新编号。但它的描述并不多，我不明白为什么重新编号有效。

我查看了解决方案的示例工作源代码，但我仍然不明白最后一部分。

我真的不明白的部分是从res-=n%k（以及之后的行）开始。您如何得出这是调整结果的方法？

有人可以说明这是如何得出的背后的原因吗？还是派生它的链接？（我在 UVA 或 topcoder 论坛上没有找到任何信息）

有5名成员围坐在一张桌子旁。关键值是围坐在桌子旁的成员数量。所以现在关键值是 5。一个恐怖分子告诉成员，因为你是 5 个成员，我将从第一个成员开始数，被数为 5 的人将被枪杀。他数数，第五个人死了。他再一次数到五，第一个人就死了。他又数了一遍，第三个人死了，现在剩下了2和4。他数了数他们之间的不，最后4算5，他被枪杀了。最后剩下的人是2。

同样，如果尝试 7 人，答案将是 8。对于 8 人，答案将是 4。

如何为此设置公式，以便计算机可以正确拍摄人。

我猜它可能通过给成员一个令牌值而在一个循环链表中。但我无法得出一个等式。因此，通过给出关键值，将确定将要活下去的人。

我偶然发现了 Haskell 和 FP，并被这些可能性惊呆了。我内心的老数学书呆子为实际有用的目的编写幼稚的代码没有问题。然而，尽管阅读了所有内容，我仍然很难理解如何不遇到一些令人惊讶的性能瓶颈。

因此，我用幼稚的实现编写了非常短的代码，然后尝试进行一些小的更改以查看性能如何响应。这是一个我真的无法理解的例子......我写了这个函数来找到约瑟夫斯问题的解决方案，故意用一个简单的列表实现。

后者的运行时间为 190 毫秒，根据 RTS，生产率为 63%。

然后我想尝试的第一件事是删除（长度士兵-1）并将其替换为递减整数。

运行时间跃升至 900 毫秒，生产力下降至 16%，并且使用的内存是上面更简单的代码的 47 倍！所以我添加了严格的评估，强制使用 Int 类型，尝试删除全局变量等，但效果不大。我只是无法理解这种放缓。

我已经筛选了与性能相关的文章和帖子，但我似乎对此一无所知。仍然是一个 Haskell 菜鸟，我一定错过了一些重要的东西......这个添加的参数（预先咀嚼的计算......）如何降低速度这么多？

PS：我知道，如果约瑟夫斯真的和 3000 名士兵在一起，他们就不需要自杀了……

我使用计数器作为人的标签，或者换句话说，消除开始的位置。

我对消除方法有疑问，我希望它必须不断调用，直到列表为空，

我对 VC++ 很陌生。昨天我的 VC++ 讲师给了我们这段代码，并要求我们将其制作为 exe。我不知道从哪里开始和结束。如何将这个单个文件变成exe。在 Visual Studio 中如何以及在何处粘贴此工作代码。如果我的问题听起来太愚蠢，对不起。但是我。请帮助我从这个单个文件中制作一个 exe。顺便说一下，这是约瑟夫斯圆算法

约瑟夫斯问题可以通过以下递归来解决：

这种递归关系是如何得出的？

我想知道是否可以在 python 中使用 list 来解决 Josepheus 问题。

简单来说，约瑟夫斯问题就是在循环排列中找到一个位置，如果使用预先知道的跳过参数处理执行，这将是安全的。

例如：给定一个圆形排列，例如[1,2,3,4,5,6,7]跳过参数为 3，人员将按顺序执行，3,6,2,7,5,1并且位置4将是安全的。

一段时间以来，我一直在尝试使用 list 来解决这个问题，但是索引位置对我来说变得难以处理。

用代码片段更新了问题，但我认为我的逻辑不正确。