基于 Python 的 Josephus 问题解法

Josephus 问题：假设有 n 个人围坐一圈，现在要求从第 k 个人开始报数，报到第 m 个数的人退出。然后从下一个人开始继续报数并按同样的规则退出，直至所有人退出。要求按顺序输出各出列人的编号。

基于 Python 的 list 和固定大小的「数组」概念

把 list 当做元素个数固定的对象，只修改元素的值，不改变表的结构（不用加入或删除元素的操作）。这相当于摆了一圈 n 把椅子，人可以走但椅子在那里且位置不变。基于这种设计可以有多种实现方法。下面的方法是给每个人赋予一个编号，没有人的情况用 0 表示，各 list 的元素记录这些编号。算法梗概：

• 初始：

  • 建立一个包含 n 个人（的编号）的表；
  • 找到第 k 个人，从那里开始；

• 处理过程中采用把相应表元素修改为 0 方式表示已出列，反复做：

  • 数 m 个（尚在坐）的人，遇到表的末端就转回下标 0 继续；
  • 把表示第 m 个人的表元素修改为 0；
• n 个人出列即结束。

算法中用 i 表示数组下标，其初值取 k-1，内层循环中每次加一并通过取模 n 保持 i 的取值范围正确。大循环一次迭代出列一人，共计执行 n 次迭代。循环体里的 count 计数直至 m，计数中跳过空椅子。

def josephus_a(n, k, m):
    people = list(range(1, n+1))

    i = k - 1
    for num in range(n):
        count = 0
        while count < m:
            if people[i] > 0:
                count += 1
            if count == m:
                print(people[i], end="")
                people[i] = 0
            i = (i + 1) % n
        if num < n-1:
            print(", ", end="")
        else:
            print("")
    return

基于顺序表的解

考虑另一种算法：把保存人员编号的 list 按表的方式处理，一旦确定了应该退出的人，就将表示其编号的表元素从表中删除。这样，随着计算的不断惊醒，所用的表将变得越来越短。下面用 num 表示表的长度，每退出一人，表的长度 num 减一，至表长度为 0 时计算工作结束。采用这种想法和设计，表中的元素全是有效元素，所以下标更新可以用i = (i + m - 1) % num 来统一描述。

def josephus_l(n, k, m):
    people = list(range(1, n+1))

    num, i = n, k-1
    for num in range(n, 0, -1):
        i = (i + m-1) % num
        print(people.pop(i), end=(", " if num > 1 else "\n"))
    return

基于循环单链表的解

考虑基于循环单链表实现一个算法。

从形式上看，循环单链表可以很直观地表示围坐一圈的人，顺序数人头可以自然地反映为在循环表中沿着 next 链扫描，一个人退出可以用删除相应结点的操作模拟。在这样做完以后，又可以沿着原方向继续数人头了。

1. 建立包含指定个数（和内容）的结点的循环单链表，这件事可以通过从空表出发，在尾部逐个加入元素的方式完成；
2. 循环计数，找到并删除应该退出的结点。

现在为原循环单链表增加一个循环数数的函数，然后写一段程序建立所需的循环单链表，并完成操作。

循环单链表的类实现如下：

class LCList:
    def __init__(self):
        self._rear = None

    def is_empty(self):
        return self._rear is None

    def prepend(self, elem):
        """
        前端插入
        :param elem:
        :return:
        """
        p = LNode(elem)
        if self._rear is None:
            p.next = p
            self._rear = p
        else:
            p.next = self._rear.next
            self._rear.next = p

    def append(self, elem):
        """
        尾端插入
        :param elem:
        :return:
        """
        self.prepend(elem)
        self._rear = self._rear.next

    def pop(self):
        """
        前端弹出
        :return:
        """
        if self._rear is None:
            raise LinkedListUnderflow("in pop of LCList")
        p = self._rear.next
        if self._rear is p:
            self._rear = None
        else:
            self._rear.next = p.next
        return p.elem

    def printall(self):
        if self.is_empty():
            return
        p = self._rear.next
        while True:
            print(p.elem)
            if p is self._rear:
                break
            p = p.next

派生类 Josephus 的实现中没有增加「当前人指针」这一设置，采用了另一种考虑，把计数过程看作人圈的转动（结点环的转动）。这个类里定义了新方法 turn，将循环表对象的 rear 指针沿 next 方向移动 m 步。

class Josephus(LCList):
    def turn(self, m):
        for i in range(m):
            self._rear = self._rear.next

    def __init__(self, n, k, m):
        LCList.__init__(self)
        for i in range(n):
            self.append(i+1)
        self.turn(k-1)
        while not self.is_empty():
            self.turn(m-1)
            print(self.pop(), end=("\n" if self.is_empty() else ", "))

该算法的时间复杂度较容易考虑：建立初始表的复杂度是 O(n)，后面循环的算法复杂度是 O(m*n)，因为总共做了 $m\times n$ 的旋转。