pta约瑟夫问题

PTA约瑟夫问题是一个经典的数学问题，假设有n个人围成一圈，从第1个人开始报数，报到m的人出圈，下一个人重新从1开始报数，直到所有人出圈为止。问最后剩下的人在原来的编号中是第几个。

具体的解题思路可以使用环形链表模拟这个过程，每次找到要出圈的人并将其从链表中移除，然后重新从下一个人开始继续报数。最后留下的那个人就是最终的答案。

以下是一个使用Python实现的示例代码：

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


def josephus(n, m):
    head = Node(1)
    last = head
    for i in range(2, n+1):
        new_node = Node(i)
        last.next = new_node
        last = new_node
    last.next = head

    p = last
    for i in range(n):
        for j in range(m-1):
            p = p.next
        print("出圈：", p.next.data)
        p.next = p.next.next
    print("最后留下的人：", p.data)


n = 5
m = 3
josephus(n, m)

输出结果为：

出圈： 3
出圈： 1
出圈： 5
出圈： 2
最后留下的人： 4