6.编写程序,使用单链表作数据结构，解决Josephus问题。 Josephus问题描述如下:设有

Question

6.编写程序,使用单链表作数据结构，解决Josephus问题。 Josephus问题描述如下:设有n个人围坐一圈，现从第1个人开始报数,顺时针方向数到m的人出列，然后从出列的下一个人重新开始报数，数到m的人出列.....如此反复，直至最后剩下一个人便是胜利者。Josephus问题是:对于任意给定的n和m(m

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

代码实现：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
def josephus(n, m):
    if n <= 0 or m <= 0:
        return -1
    # 构建循环链表
    head = Node(1)
    cur = head
    for i in range(2, n + 1):
        cur.next = Node(i)
        cur = cur.next
    cur.next = head
    
    # 从头节点开始报数
    cur = head
    while cur.next != cur:
        # 找到要出列的节点的前一个节点
        for _ in range(m - 2):
            cur = cur.next
        # 将要出列的节点移除链表
        cur.next = cur.next.next
        cur = cur.next
    
    return cur.data
n = int(input("请输入人数："))
m = int(input("请输入报数的个数："))
winner = josephus(n, m)
print("最后胜利者的编号是 %d" % winner)

案例： 输入：

请输入人数：7
请输入报数的个数：3

输出：

最后胜利者的编号是 4

解释：有7个人围坐一圈，从1开始报数，数到3的人出列，然后从出列的下一个人重新开始报数，如此反复，最后剩下的人的编号是4。