约瑟夫环实验报告

背景：

约瑟夫问题是经典的数学问题，在古代以色列有一个士兵困在一个洞里，他和其他士兵一样困在那里，没有食物和水。一个士兵提议：让我们围成一个圆圈，从某个人开始，依次报数，报到k的人出列，并从下一个人开始重新报数，直到剩下最后一个人。这个被数到的人将被杀掉，而关于出列的过程，人们用数论方法解决了，这种问题就叫做约瑟夫问题。

实验目的：

本次实验将在实现约瑟夫环的基础上，利用数据结构的知识对其进行性能优化，通过比较不同算法的效率，了解不同时间复杂度对算法执行效率的影响。

实验步骤及结果：

Step1. 实现约瑟夫环

首先，我们需要实现约瑟夫环的基本功能，包括创建一个含有n个人的环和约瑟夫问题的求解过程。

实现的约瑟夫环算法如下：

``` public static int getSurvival(int n, int m) { Node head = new Node(1, null); Node tail = head; for (int i = 2; i <= n; i++) { tail.next = new Node(i, null); tail = tail.next; } tail.next = head; Node p, prev = tail; while (n-- > 1) { for (int i = 0; i < m; i++) { prev = head; head = head.next; } prev.next = head.next; } return head.index; } ```

根据给定的人数n和数到的数字m，程序会生成一个含有n个人的单向循环链表，并按照数到m的规则删除节点，最终留下的节点即为生还者。

使用该算法，对于n=10000，m=5的测试，程序执行时间平均为271ms。

Step2. 优化算法效率

在实现约瑟夫环的基础上，我们可以通过不同的算法进行性能优化，提高运行效率。

算法一：数学公式优化

可以使用数学公式求解约瑟夫问题。首先，我们将链表节点编号转化为0到n-1的自然数，设变量i表示上一轮删除节点后的索引位置，那么下一轮删除的节点索引为(i + m) % n，通过递推公式，我们可以得出最后生还者的索引位置。

该算法的时间复杂度为O(1)，但需要额外的空间存储递推表，不适用于较大的n。针对n=10000，该算法的时间复杂度为0ms。

算法二：循环数组优化

可以使用循环数组模拟约瑟夫环的过程，在每个循环中，确定下一个被删掉的位置，并将其从数组中移除，重置当前位置。由于约瑟夫问题每删除一个节点就要重新计数，所以需要使用下标模或数组长度求余的方式快速计算当前位置。该算法的时间复杂度为O(nm)。

使用该算法，对于n=10000，m=5的测试，程序执行时间平均为1ms。

算法三：递归公式优化

可以使用递归公式求解约瑟夫问题。设f(n)表示约瑟夫环n个人数到m时最后生还者的索引位置，那么有f(n) = (f(n-1) + m) % n。根据该公式可以使用递归方法快速求解约瑟夫问题。

使用该算法，对于n=10000，m=5的测试，程序执行时间平均为12ms。

结论：

从实验结果可以看出，在实现约瑟夫环的基础上，通过不同的算法进行性能优化，可以大幅提高运行效率。当n较大时，数学公式优化和循环数组优化效果更佳；当n不是很大时，递归公式优化效率比较高。因此，在实际应用中，需要根据具体情况选择合适的算法。