[已解决]约瑟夫生死游戏

stumblemodel

有n个人按顺序围成一个圈，从第一个开始1-3循环报数，报到3的人被淘汰，直到只剩最后一个
编程实现：
      输入n，输出最后一个人原来的编号

最佳答案

月排行榜 / 总排行榜

FishC

2023-12-25 21:42:37

可以使用循环链表来模拟这个约瑟夫生死游戏的过程。

首先，我们定义一个节点类来表示每个人，其中包含一个编号和一个指向下一个节点的指针：

1. class Node:
2.     def __init__(self, data):
3.         self.data = data
4.         self.next = None

复制代码

然后，我们可以编写一个函数来创建一个包含n个人的循环链表：

1. def create_circle(n):
2.     head = Node(1)
3.     current = head
4.     for i in range(2, n + 1):
5.         node = Node(i)
6.         current.next = node
7.         current = node
8.     current.next = head
9.     return head

复制代码

接下来，我们编写一个函数来模拟游戏的过程，直到只剩下最后一个人：

1. def josephus_game(n):
2.     circle = create_circle(n)
3.     current = circle
4.     while current.next != current:
5.         for _ in range(2):
6.             current = current.next
7.         current.next = current.next.next
8.     return current.data

复制代码

最后，我们可以通过输入一个n来测试这个函数，输出最后一个人原来的编号：

1. n = int(input("请输入人数："))
2. last_person = josephus_game(n)
3. print("最后一个人原来的编号是：", last_person)

复制代码

希望我的解答对你有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

可以使用循环链表来模拟这个约瑟夫生死游戏的过程。

首先，我们定义一个节点类来表示每个人，其中包含一个编号和一个指向下一个节点的指针：

1. class Node:
2.     def __init__(self, data):
3.         self.data = data
4.         self.next = None

复制代码

然后，我们可以编写一个函数来创建一个包含n个人的循环链表：

1. def create_circle(n):
2.     head = Node(1)
3.     current = head
4.     for i in range(2, n + 1):
5.         node = Node(i)
6.         current.next = node
7.         current = node
8.     current.next = head
9.     return head

复制代码

接下来，我们编写一个函数来模拟游戏的过程，直到只剩下最后一个人：

1. def josephus_game(n):
2.     circle = create_circle(n)
3.     current = circle
4.     while current.next != current:
5.         for _ in range(2):
6.             current = current.next
7.         current.next = current.next.next
8.     return current.data

复制代码

最后，我们可以通过输入一个n来测试这个函数，输出最后一个人原来的编号：

1. n = int(input("请输入人数："))
2. last_person = josephus_game(n)
3. print("最后一个人原来的编号是：", last_person)

复制代码

希望我的解答对你有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。