MENU

基于 Python 的 Josephus 问题解法

February 18, 2017 • Read: 1025 • 代码

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$ 的旋转。

Tags: python
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment