一堆猴子都有编号,编号是1,2,3...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。要求:m及n要求从键盘输入,存储方式采用链表实现该问题求解。
时间: 2023-05-25 07:07:18 浏览: 115
以下是Python实现的代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
def create_linked_list(n):
head = Node(1)
curr = head
for i in range(2, n+1):
node = Node(i)
curr.next = node
curr = node
curr.next = head
return head
def josephus_circle(head, n):
prev = head
while prev.next != head:
prev = prev.next
curr = head
count = 1
while curr != curr.next:
if count == n:
count = 1
print("Monkey", curr.data, "leaves the circle.")
prev.next = curr.next
curr = prev.next
else:
count += 1
prev = curr
curr = curr.next
print("Monkey", curr.data, "is the king of the circle!")
m = int(input("Enter the total number of monkeys: "))
n = int(input("Enter the 'n' to count: "))
head = create_linked_list(m)
josephus_circle(head, n)
```
首先定义一个`Node`类表示链表中的每个节点,具有`data`和`next`两个属性,其中`data`表示猴子的编号,`next`表示下一个节点。
`create_linked_list(n)`函数用来创建一个包含`1`到`n`的循环链表,返回链表的头节点`head`。
`josephus_circle(head, n)`函数实现约瑟夫环问题的求解过程,其中`head`为循环链表的头节点,`n`表示每数到第`n`个猴子就要离开圈。在循环中,用`prev`指向当前节点的前一个节点,用`curr`指向当前节点,用`count`表示当前轮到第几只猴子。每数到第`n`只猴子,将该猴子从循环链表中删除,并输出该猴子的编号。最后剩下的猴子即为大王,输出其编号即可。
在`main`函数中,从键盘输入总猴子数和`n`,创建循环链表并调用`josephus_circle`函数求解。
阅读全文
相关推荐
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231044833.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)