约瑟夫问题 -- python实现

问题描述

N个人围成一个圈, 从第一个人开始报数, 报到M的人出圈, 剩下的人继续从1开始报数, 报到M的人出圈;如此往复, 直到所有人出圈.

列表解决

def solution_list(n, m):
    """
    初始化一个长度为n的列表, 默认值为True. 当某个元素出圈时, 将其置为False.
    循环迭代这个列表, 遇到值为False的元素则跳过, 当列表中全为False时表示所有人
    都已出圈.
    """
    # 初始化列表
    people = []
    for _ in range(n):
        people.append(True)

    result = []
    num = 1
    while any(people):
        for index, p in enumerate(people):
            if p:
                if num == m:                  # 出圈操作
                    people[index] = False
                    result.append(index + 1)
                    num = 1
                else:
                    num += 1
    print('-' * 25)
    print(f'\n总人数为{n}, 报数为{m}')
    print(f'约瑟夫序列为:\n {result}\n')
    print('-' * 25)

def solution_list2(n, m):
    """
    这是上面这种思路的另一种解法, 将圈内和圈外表示成0和1.
    这里实现循环迭代的方式我第一次遇到, 记录一下
    """
    people = [0 for _ in range(n)]

    alive = n                           # 剩余人数
    index = 0
    num = 0                             # 计数器, 当index == m时出圈
    result = []

    while alive > 0:
        num += 1 - people[index]        # 每轮到一个人报数, 不论0或1都进行计数
        if num == m:
            result.append(index + 1)    # 出圈
            people[index] = 1           # 将出圈人置为 1
            alive -= 1                  # 剩余人数 - 1
            num = 0                     # 重置计数器

        # 与总人数 n 取余, 可以实现index在 0 ~ count -1之间一直循环, 达到循环迭代的目的
        index = (index + 1) % n

    print('-' * 25)
    print(f'\n总人数为{n}, 报数为{m}')
    print(f'约瑟夫序列为:\n {result}\n')
    print('-' * 25)

循环链表解决

class Node:
    """节点"""
    def __init__(self, value):
        self.data = value
        self.next = None

    def __repr__(self):
        return f'Node: {self.data}'


class CircularLinkedList:
    """循环链表"""
    def __init__(self):
        self.rear = None    # 尾节点

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

    def append(self, elem):
        """尾插法"""
        temp = Node(elem)
        if self.rear is None:
            temp.next = temp
            self.rear = temp
        else:
            temp.next = self.rear.next
            self.rear.next = temp
            self.rear = temp


def solution_circular_linked_list(n, m):
    """
    通过循环链表解决, 每次出圈弹出该节点
    """
    clist = CircularLinkedList()
    for i in range(n):
        clist.append(i + 1)

    result = []
    pre = clist.rear                    # 当前节点的上一个节点
    cur = clist.rear.next               # 当前节点
    num = 0                             # 计数器

    while cur.next is not cur:
        num += 1
        if num == m:                    # 出圈
            result.append(cur.data)
            pre.next = cur.next         # 弹出当前节点
            num = 0                     # 重置计数器
        else:
            pre = pre.next
        cur = cur.next
    result.append(cur.data)

    print('-' * 25)
    print(f'\n总人数为{n}, 报数为{m}')
    print(f'约瑟夫序列为:\n {result}\n')
    print('-' * 25)

参考:
经典算法--约瑟夫环问题的三种解法
百度百科