Python实现约瑟夫问题：顺序表和链表解法详解

下面是使用顺序表和链表两种方式解决约瑟夫问题的 Python 代码：

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

class Josephus:
    @staticmethod
    def solve_sequential(n, m):
        seq = list(range(1, n+1))
        index = 0
        while len(seq) > 1:
            index = (index + m - 1) % len(seq)
            seq.pop(index)
        return seq[0]

    @staticmethod
    def solve_linked(n, m):
        head = Node(1)
        curr = head
        for i in range(2, n+1):
            curr.next = Node(i)
            curr = curr.next
        curr.next = head

        while curr.next != curr:
            for _ in range(m-1):
                curr = curr.next
            curr.next = curr.next.next

        return curr.data

def main():
    n = int(input('请输入总人数: '))
    m = int(input('请输入报数间隔: '))

    result1 = Josephus.solve_sequential(n, m)
    print('顺序表解法结果: ', result1)

    result2 = Josephus.solve_linked(n, m)
    print('链表解法结果: ', result2)

if __name__ == '__main__':
    main()

这段代码实现了一个约瑟夫问题的解决方案。约瑟夫问题是一个经典的数学问题，描述了如何选择一个固定间隔的人，使得最后剩下的人为最后一个。

代码中定义了一个Node类表示链表节点，包含一个数据域和一个指向下一个节点的指针。然后定义了一个Josephus类，其中包含两个静态方法solve_sequential和solve_linked，分别使用顺序表和链表两种方式解决约瑟夫问题。

在solve_sequential方法中，首先创建一个顺序表seq，包含了从1到n的整数。然后使用一个循环，每次移除报数为m的人，直到只剩下最后一个人。

在solve_linked方法中，首先创建一个循环链表，每个节点代表一个人。然后使用一个循环，每次移除报数为m的人，直到只剩下最后一个人。

在main函数中，用户输入总人数和报数间隔，然后分别调用顺序表和链表解法，并打印结果。

运行程序时，用户需要输入总人数和报数间隔，然后程序会输出顺序表解法和链表解法的结果。