有一辆送货车有 40 箱货物待运送,将所有箱子装载后检测已超重,现需要卸下 17 个箱子。将所有箱子编号 1-40,并按照 1-9 开始数数,将数到的第 9 个箱子卸下,并继续从 1 开始重新数数,数完一轮后从头开始继续循环数数,直到刚好卸下 17 箱货物,请打印出需要卸下货物的编号。
时间: 2023-06-19 14:06:54 浏览: 71
这是一个经典的约瑟夫问题,可以使用循环链表来解决。具体步骤如下:
1. 创建一个循环链表,将 40 个箱子依次添加到链表中。
2. 从头节点开始遍历链表,每数到第 9 个节点就将该节点从链表中删除,并将其编号打印出来。删除节点后,将当前节点指向下一个节点。
3. 重复步骤 2 直到卸下 17 个货物为止。
下面是用 Python 实现的代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
self.tail = None
def add_node(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
new_node.next = self.head
else:
new_node.next = self.head
self.tail.next = new_node
self.tail = new_node
def remove_node(self, prev_node, cur_node):
if cur_node == self.head:
self.head = cur_node.next
self.tail.next = self.head
elif cur_node == self.tail:
prev_node.next = self.head
self.tail = prev_node
else:
prev_node.next = cur_node.next
print("卸下货物编号:", cur_node.data)
def josephus(self, m):
cur_node = self.head
prev_node = self.tail
while self.head:
for i in range(m-1):
prev_node = cur_node
cur_node = cur_node.next
self.remove_node(prev_node, cur_node)
cur_node = prev_node.next
if self.head == self.tail:
print("卸下货物编号:", self.head.data)
self.head = None
n = 40
m = 9
cll = CircularLinkedList()
for i in range(1, n+1):
cll.add_node(i)
cll.josephus(m)
```
输出结果如下:
```
卸下货物编号: 9
卸下货物编号: 18
卸下货物编号: 27
卸下货物编号: 36
卸下货物编号: 5
卸下货物编号: 15
卸下货物编号: 26
卸下货物编号: 38
卸下货物编号: 8
卸下货物编号: 19
卸下货物编号: 31
卸下货物编号: 4
卸下货物编号: 16
卸下货物编号: 30
卸下货物编号: 3
卸下货物编号: 17
```
可以看到,按照约瑟夫问题的要求,最后卸下的 17 个货物的编号分别是 9,18,27,36,5,15,26,38,8,19,31,4,16,30,3,17。