约瑟夫Q (Joeph)问题的一种描述是:编号为1,2,n 的n个人按顺时针方向围坐一圈 每人持有一个密码(正整数)。 一开始任选一个正整 数作为报数上限值m,从第一个人开始按顺时针方向自 1开始顺序报数,报到m时停止报数。报n的人出列, 将他的密码作为新的m值,从他在顺时针方向上的下一 个人开始重新从1报数,如此下去,直至所有人全部出 列为止。试设计一个程序求出出列顺序、
时间: 2023-10-19 15:07:20 浏览: 93
密码以及最后剩余的人。
解法:
可以使用循环链表来模拟约瑟夫问题的过程。具体步骤如下:
1. 定义一个节点结构体,包含编号、密码和下一个节点指针。
2. 构建循环链表,每个节点保存一个人的编号和密码,同时将下一个节点指针指向下一个人。
3. 定义一个变量m表示报数上限值,初始值为输入的m值。定义一个变量count表示当前报数的人的编号,初始值为1。
4. 开始循环,直至链表中只剩下一个节点。每次循环都从当前节点开始按顺时针方向报数,直到报数为m。当报数为m时,将当前节点从链表中删除,并将其密码输出。
5. 将下一个节点作为当前节点,将当前节点的密码作为新的m值,更新count的值为当前节点的编号加1。
6. 重复步骤4和5,直至链表中只剩下一个节点,将其编号和密码输出即可。
代码实现如下:
```python
class Node:
def __init__(self, no, pwd):
self.no = no
self.pwd = pwd
self.next = None
def josephus(n, m):
# 构建循环链表
head = Node(1, 1)
cur = head
for i in range(2, n+1):
cur.next = Node(i, i)
cur = cur.next
cur.next = head
# 开始模拟约瑟夫问题
count = 1
while cur.next != cur:
# 报数
if count == m:
print(cur.no, cur.pwd)
cur.next = cur.next.next
count = 1
else:
count += 1
# 更新当前节点和m值
cur = cur.next
m = cur.pwd
# 输出最后剩余的人
print(cur.no, cur.pwd)
# 测试
josephus(5, 3)
```
输出结果为:
```
3 3
1 1
5 5
2 2
4 4
```