约瑟夫环问题python代码
时间: 2023-09-08 21:15:00 浏览: 51
以下是使用Python的解决方案:
```python
def josephus(n, k):
if n == 1:
return 1
else:
return (josephus(n - 1, k) + k-1) % n + 1
# 测试
n = 7
k = 3
print("最后一个剩下的人的编号是 ", josephus(n, k))
```
输出为:最后一个剩下的人的编号是 4
解释:
假设n = 7,k = 3,那么就有7个人围成一圈,从第1个人开始报数,报到3的人出圈,然后从下一个人重新开始报数,直到最后只剩下一个人。
第一轮:1 2 3(出圈) 4 5 6 7
第二轮:1 2(出圈) 4 5 6 7
第三轮:1(出圈) 4 5 6 7
第四轮:4 5(出圈) 6 7
第五轮:4 5(出圈) 7
最后剩下的人是4。
相关问题
Python约瑟夫环问题代码
以下是Python实现约瑟夫环问题的代码[^1]:
```python
def Joseph(n,m):
a =[i for i in range(1,n+1)]
print(a)
m = m
while len(a) >= 1:
if len(a) >= m:
print(a[m-1])
# del a[m-1]
a = a[m:] + a[:m-1]
print(a)
else:
if (m%len(a)-1) != -1:
print(a[m%len(a)-1])
a = a[m%len(a):] + a[:m%len(a)-1]
print(a)
else:
print(a[m%len(a)-1])
a = a[:m%len(a)-1]
print(a)
if __name__ == '__main__':
n,m = input('Please enter n and m:').split()
Joseph(int(n),int(m))
```
该代码实现了输入n个人和间隔m个人,从第一个人开始报数,报到m的人出圈,下一个人重新从1开始报数,直到所有人都出圈为止。
约瑟夫环问题python
好的,约瑟夫环问题是一个经典的问题,它的描述如下:有n个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,直到剩下最后一个人。现在请问,最后剩下的人的编号是多少?
这个问题可以用循环链表来解决,具体实现可以参考以下代码:
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
def josephus(n, m):
# 构建循环链表
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 i in range(m-1):
cur = cur.next
cur.next = cur.next.next
return cur.value
print(josephus(5, 3)) # 输出3
```