问题标签 [josephus]

我正在尝试解决约瑟夫斯问题，并且我有工作代码。

现在我想重写它以获得如下结果：

---

我怎样才能做到这一点？

我的班级正在通过实现一个循环单链表来模拟约瑟夫斯问题。我的代码可以编译，但是当它运行时出现分段错误：构建列表后的 11 。到目前为止，我的调试使我意识到错误发生在程序进入主函数的最后一个while循环时。我认为这与我使用 first->next 的方式有关，但我不确定。任何帮助都会很棒，谢谢。如果这不明显，我正在用 C++ 编码。

我正在编写一些 Java 代码，这些代码应该使用循环链接列表来实现众所周知的约瑟夫斯问题。以下是有关约瑟夫斯问题的一些信息：http ://en.wikipedia.org/wiki/Josephus_problem

我有一个学生班和司机班，它们被分配给我来创建我的约瑟夫斯班。

这是学生课程： http: //pastebin.com/4YgSA7CM

这是驱动程序类： http: //pastebin.com/Nb08Dtqk

这两个类都不能修改。

我必须从头开始制作一个 Josephus 类，该类使用有效利用 Josephus 问题的循环链表。

这是我完成的 Josephus 类，没有编译器错误：

我的 startJosephus 方法是我认为的主要问题。虽然不完全确定。这是上面代码中的 startJosephus 方法：

这是我运行 Josephus 课程时正在运行的内容：http: //pastebin.com/5GnChgYd

这是应该产生的输出：http: //pastebin.com/Qr5dCZJp

此外，以下是用于生成此输出的两个输入文件：

StudentList1.txt：http ://pastebin.com/ysjevQ8u

StudentList2.txt：http ://pastebin.com/r2YeppNm

根据我得到的输出和我应该得​​到的输出，约瑟夫斯问题似乎没有开始并模拟杀戮狂欢。但是，我不知道我的代码有什么问题。我的代码不能有尾巴，因为它是一个循环链接列表。关于我在这里做错了什么的任何想法？抱歉所有 Pastebin 链接，这似乎是组织我在这里展示的所有代码的更好方法。希望听到你的想法。

这是我在解决无限循环问题后遇到的新运行时错误。有什么建议么？？？？所有这些空指针异常是什么

该问题的链接是UVA-1394: And There Was One。
朴素的算法是扫描整个数组并在每次迭代中标记第 k 个元素，并在最后一次停止：这需要 O(n^2) 时间。
我已经搜索了一种替代算法，并遇到了一个中文博客，该博客指出我使用惰性传播作为 O(N lgN) 时间的解决方案来分割树。
研究了段树后，我尝试为 O(N lgN) 时间形成算法，但无济于事。

---

我的问题是：
1. 可以使用分段树来获得所需的运行时间吗？
2. 如果是，请告诉我如何使用它们。
3. 段树和“zkw”段树是一回事吗？- 他在博客中提到了 zkw 段树。
更新：上述问题是约瑟夫斯问题的一个例子。

我在数据结构课程中，无法重现讲师给出的示例数据。该问题是经典的 Josephus 问题，用户提供了成员数、步长间隔和起始位置。

具体来说，我被告知有 99 人，从 23 日开始，数到 5 点，应该让 84 人成为最后一个站着的人。

我想出：65。我再次运行时认为输入可能是 99 人，从 5 开始，间隔为 23。结果：42。

我的分配解决方案涉及一个循环链表，但是这个 c 代码在所有情况下都会产生相同的输出：

再次感谢。

Please look at the following code to solve the same set of problem, I do not think that mentioning the problem would anyhow help the purpose, it's yet another iteration of the Josephus problem:

Solution 1:

This solution solves the given 10 test cases in cumulative 1.0912 seconds and consumes 4360KiB of memory.

Solution 2:

this solution solves the same 10 test cases in a total of 1.0497 seconds and 640KiB of memory.

Being a Python n00b I was wondering, while according to the online judge I earn same points for both, but what makes the solution 2 more faster than 1 and much more memory efficient? I know that the time difference can sound very less, but at the same time ranks me first on the fastest solution, even faster than c/c++/perl submissions

Can this Screenshot help?

描述： 有人围成一圈等待被处决。计数从圆圈中的某个点开始，并沿固定方向围绕圆圈进行。在每个步骤中，都会跳过一定数量的人并执行下一个人。消除围绕圆圈进行（随着被处决的人被移除，圆圈变得越来越小），直到只剩下最后一个人，他被赋予了自由。

我用谷歌搜索了这个“约瑟夫斯问题”，维基百科的热门文章给了我一个动态编程解决方案：f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1，但这只会产生最后的幸存者。我怎样才能得到执行的人的顺序？比如说，p(5, 3) = {3,1,5,2,4}。

另外，有O(nlogn)解决方案而不是解决方案O(nk)吗？

好的，我正在为 Knuth 的具体数学而苦苦挣扎，有些例子我还不明白。

J(n) = 2*J(n/2) - 1

是从第一章开始的。它专门为那些可能熟悉具体数学的人解决了约瑟夫斯问题。给出了解决方案，但绝对没有解释。我试图用迭代方法解决它。这是我到目前为止想出的

J(n) = (2^k)*J(n/(2^k)) - (2^k - 1)

我被困在这里。任何帮助或提示将不胜感激。

我已经尝试了一段时间，但我不知道如何让下面的程序以 N 作为输入并生成一个 M，以便最后一个死去的士兵是第 13 个（N>13）；

结果应该与这个相同（但我需要它在链表中，因为我不明白那个）：>。

如果您不熟悉约瑟夫斯问题：

N个士兵围成一圈站成一圈，从1开始处死，M移动，最后只有一个活着。下面的代码要求输入 N 和 M 并生成最后一个站立的玩家。

假设 N=17;M=7 输出应该是 13 上面的程序生成 2 （会发生什么？它从 M 开始计数而不是从 1 所以而不是 1,8,15 ......它消除了 7 ,14......）这是我需要你帮助的地方（因为链表对我来说仍然是一个困难的概念）。这个怎么修改？