三种方法解决Josephus问题

不念不忘少年蓝@ 2022-05-29 12:57 212阅读 0赞

## 前景 ##

由于之前数据结构底子很薄，现在开始补咯～虽然进展缓慢，慢慢来嘛～今天遇到的是josephus问题

### 问题阐述 ###

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

### 解决 ###

# 问题描述
    # 假设有n个人围坐一圈，现在要求从第k个人开始报数，报到第m个数的人退出。然后从下一个人开始继续报数并按照同样的规则退出，直至所有人都退出。按照顺序输出各出列人的编号
    
    
    # 解法1.基于数组。使用0代表出列的人
    def josephus(n, k, m):
        lista = []
        # 一共有n个人，先编好序号
        for i in range(1, n+1):
            lista.append(i)
        # 一共要出列n个人,person 是正在报数的人的下标,最后要输出各列人的编号
        person = k-1
        for time in range(n):
            # count作为计数器，每报一个数count自增1
            count = 0
            # 游戏执行的条件，只要没报到m个数
            while count != m:
                if lista[person] != 0:
                    count += 1
                if count == m:
                    # 第m个人出列，记为0
                    lista[person] = 0
                    yield person+1
                person += 1
                person %= n
    
    
    # 基于Python的列表
    def fun(n, k, m):
        lista = list(range(1, n+1))
        i = k-1
        # 每次都要出列一个人，所有人的总数会随之减少
        for number in range(n, 0, -1):
            i = (i+m-1) % number
            person = lista.pop(i)
            yield person
    
    
    # 基于循环单链表
    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    
    class LoopList:
        def __init__(self):
            self.tail = None
    
        def add(self, data):
            if self.tail is None:
                self.tail = Node(data)
                self.tail.next = self.tail
            else:
                tmp = Node(data)
                tmp.next = self.tail.next
                self.tail.next = tmp
    
        def append(self, data):
            self.add(data)
            self.tail = self.tail.next
    
        def bianli(self):
            current = self.tail.next
            while current is not self.tail:
                print(current.data)
                current = current.next
            print(current.data)
    
        # 前端弹出
        def pop(self):
            # 如果就是一个结点的话
            tmp = self.tail.next
            if tmp is self.tail:
                self.tail = None
            else:
                self.tail.next = tmp.next
            return tmp.data
    
        # 尾端弹出
        def pop2(self):
            current = self.tail.next
            while current.next is not self.tail:
                current = current.next
            current.next = self.tail.next
            self.tail = current
    
    
    class Josephus(LoopList):
        # 尾指针作为正在报数的那个人，每一轮报数作为一次指针的移动（旋转）
        def spin(self, n):
            for i in range(n):
                self.tail = self.tail.next
    
        def __init__(self, n, k, m):
            super(Josephus, self).__init__()
            for i in range(1, n+1):
                self.append(i)
            # 初始化到第k个人进行报数
            self.spin(k-1)
            while self.tail is not None:
                # 旋转到报第m个数的人
                self.spin(m-1)
                print(self.pop())

结果测试：

a = LoopList()
    a.append(12)
    a.append(13)
    a.append(14)
    a.pop2()
    a.bianli()
    Josephus(10, 1 ,3)

> 12  
> 13  
> 3  
> 6  
> 9  
> 2  
> 7  
> 1  
> 8  
> 5  
> 10  
> 4