约瑟夫环数据结构实验报告（实验：约瑟夫问题——从数据结构的角度分析问题）

●耍cool●+ 论文 2023-10-04 22:51:16 627 次浏览评论已关闭

实验：约瑟夫问题——从数据结构的角度分析问题

约瑟夫问题是经典的计算机科学问题之一，它源于古希腊历史学家JosephusFlavius的故事，迄今为止已经产生了很多有趣的解法。这个问题的具体描述是：有$n$个人（编号从1到$n$）围坐成一个圆环形状，从1开始每数$m$个人，从圆盘中删除第$m$个人，然后剩下的人重新坐成一个圆圈并重复这个过程，直到只剩下一个人。那么最后剩下的人是谁？

算法分析

约瑟夫问题有很多种解法，其中比较常用的有两种：递推法和循环链表法。

递推法

递推法的核心思想是：通过状态转移方程直接计算出第$i$轮剩余人数。我们设$f(i)$为第$i$轮剩余人数，则可以得到这样一组递推式：

$$f(1)=n, f(i)=f(i-1)-(m-1)\\quad(2\\le i \\le n)$$

这个式子的解法很简单，只需要从1到$n$枚举每一轮的剩余人数就可以了。但是问题在于：这个式子没有考虑到转换周期。因为当已经删掉了第$m$个人后，我们重新从剩余的人中开始数数。所以我们需要对$i$进行一个小变化：令$g(i)=$第$i$个出局的人原来的编号。显然，$g(i)$并不等于$f(i)$。

对于这个问题，我们可以发现一个规律：每隔$m$个人，就会出现一次转换周期。因此，我们需要对$k$进行一个小变化：令$p=k\\mod f(i-1)$。这样，每次剩余的人数变化的过程，就会自动地刻画出转换周期。递推公式变为：

$$ \\begin{aligned} g(1)&=\\,m\\mod n\\\\ g(i)&=\\,[g(i-1)+(m-1)]\\mod f(i-1),\\quad (2\\le i \\le n) \\end{aligned} $$

这个公式比较好理解，即每次报数的起点就是上次被幸存者的后面，加上规律$m-1$。可以证明，这个公式能够正确地解决约瑟夫问题。

循环链表法

另一种常见的解法是使用循环链表。我们可以将$n$个人用循环链表的方式表示出来，并对每个结点进行编号。在每一轮过程中，我们只需要遍历链表一遍，并找到第$m$个结点，然后删除它就行了。具体的实现细节可以参考下面的代码：

```python class Node: def __init__(self, data=0, next=None): self.data = data self.next = next class Josephus: def __init__(self, n, m): self.head = Node(1) x = self.head for i in range(2, n+1): x.next = Node(i) x = x.next x.next = self.head # 将尾指针指向头结点 self.n, self.m = n, m def solve(self): x = self.head for i in range(self.n-1): for j in range(self.m-2): x = x.next x.next = x.next.next x = x.next return x.data ```

这种方法的主要优点在于代码比较简单易懂，也容易调试。不过这种方法的时间复杂度比递推法要高，为$O(nm)$，其中$n$为总人数，$m$为规则数。

性能分析

我们对比一下这两种算法的时间复杂度。递推法用的空间很少，只需要存储两个数组，而且计算速度很快，时间复杂度为$O(n)$；循环链表法则需要用到单向循环链表，空间占用较多，时间复杂度为$O(nm)$。当$n$和$m$非常大的时候，循环链表法的时间复杂度会越来越高，而递推法的时间复杂度基本不变。

此外，还需要注意到，使用递推法的策略可能会影响实际运行效果。如果我们使用递推法来计算约瑟夫问题，那么在最后一次递推之后，$f(n)=1$，即只剩下最后一个人。但是如果我们将递推式写成$f(i)=(2f(i-1)-m)\\mod i$的形式，则需要枚举从1到$n$的所有人，但最终结果是一样的。这对优化实际运行效果非常有帮助。