约瑟夫问题的求解。 1、分别用带附加头结点和不带附加头结点的单链表实现,写出实现的代码,可以使用单链表的基本操作函数。 2、在1基础上,计算报数间隔多大时,排1的人能留到最后。
时间: 2024-05-14 07:16:36 浏览: 8
1. 不带附加头结点的单链表实现:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Josephus:
def __init__(self, n, m):
self.head = None
self.tail = None
self.n = n
self.m = m
self.count = 0
def create_list(self):
for i in range(1, self.n+1):
new_node = Node(i)
if not self.head:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.tail.next = self.head
def delete_node(self, prev, curr):
prev.next = curr.next
curr = curr.next
def find_survivor(self):
curr = self.tail.next
while self.n > 1:
self.count += 1
if self.count == self.m:
self.delete_node(prev, curr)
self.count = 0
self.n -= 1
else:
prev = curr
curr = curr.next
return curr.data
```
2. 计算报数间隔多大时,排1的人能留到最后:
设报数间隔为$m$,则第一轮删除的是第$m$个数,即$m-1$个数在第一轮之后还剩下,设$n_1$表示第一轮之后剩下的人数。
第二轮开始时,从第$m+1$个数开始报数,由于第一轮删除了第$m$个数,所以实际上是从第$m+1$个数开始报数。所以第二轮删除的是第$2m$个数,即第$m$个数(原来的第$2m$个数)在第二轮之后还剩下,设$n_2$表示第二轮之后剩下的人数。
依次类推,可以得到:
$$n_{i+1} = (n_i - 1)\ mod\ i + 1$$
当$n_i=1$时,即只剩下1个人时,此时的$m$即为所求的答案。
完整代码如下:
```python
class Josephus:
def __init__(self, n):
self.n = n
def find_m(self):
m = 2
while True:
count = 1
for i in range(2, self.n+1):
count = (count + m - 1) % i + 1
if count == 1:
break
if i == self.n:
return m
m += 1
```