约瑟夫环问题用顺序线性表和链式线性表解决代码

约瑟夫环问题是一个著名的数学问题，也称为约瑟夫斯问题（Josephus problem），描述的是有n个人围成一圈，从第k个人开始报数，每次报到m的人出列，然后从下一个人开始继续报数，直到所有人都出列为止。该问题可以用顺序线性表和链式线性表来解决。

以下是使用顺序线性表和链式线性表解决约瑟夫环问题的Python代码示例：

1. 使用顺序线性表（列表List）解决约瑟夫环问题：

def josephus问题顺序线性表(n, k, m):
    # 初始化列表，存放人员编号
    people = list(range(1, n+1))
    index = k - 1  # 开始位置索引

    # 循环直到列表为空
    while len(people) > 0:
        # 报数m-1次后，当前索引位置的人出列
        index = (index + m - 1) % len(people)
        print(people.pop(index), end=' ')
    print()

# 示例
josephus问题顺序线性表(10, 3, 3)  # 10个人，从第3个人开始报数，每次报数到3

2. 使用链式线性表（链表LinkedList）解决约瑟夫环问题：

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def delete(self, value):
        current = self.head
        prev = None
        while current is not None and current.value != value:
            prev = current
            current = current.next
        if current is not None:
            if prev is None:
                self.head = current.next
            else:
                prev.next = current.next
            if current == self.tail:
                self.tail = prev
        return current

    def __str__(self):
        values = []
        current = self.head
        while current is not None:
            values.append(str(current.value))
            current = current.next
        return ' -> '.join(values)

def josephus问题链式线性表(n, k, m):
    # 初始化链表，存放人员编号
    people = LinkedList()
    for i in range(1, n+1):
        people.append(i)
    index = k - 1  # 开始位置索引

    # 循环直到链表为空
    while people.head is not None:
        # 报数m-1次后，当前索引位置的人出列
        for _ in range(m - 1):
            people.head = people.head.next
        print(people.delete(people.head.value), end=' ')
    print()

# 示例
josephus问题链式线性表(10, 3, 3)  # 10个人，从第3个人开始报数，每次报数到3