一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。要求:m及n从键盘输入,存储方式采用数组及链表两种方式实现该问题求解。
时间: 2023-05-25 20:05:52 浏览: 64
解题思路:
在数组方式中,可以采用模拟整个环的操作,将离开环的猴子的值设置为“-1”,直到只剩下一个猴子为止。
在链表方式中,则可以采用循环链表结构表示环,然后每次遍历链表找到要离开的猴子,并将其从链表中删除,直到只剩下最后一个猴子为止。
以下为两种方式的具体实现:
1. 数组方式
```python
m = int(input("请输入猴子数量m:"))
n = int(input("请输入每数到第几只猴子n:"))
# 初始化猴子编号列表
monkey = [i+1 for i in range(m)]
print("猴子围成的圈为:", monkey)
# 开始游戏,直到只剩下一只猴子
while len(monkey) > 1:
for i in range(n-1):
monkey.append(monkey.pop(0))
monkey.pop(0)
print("胜出的猴子编号为:", monkey[0])
```
2. 链表方式
```python
# 定义链表节点类
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
m = int(input("请输入猴子数量m:"))
n = int(input("请输入每数到第几只猴子n:"))
# 初始化循环链表
head = ListNode(1)
pre = head
for i in range(2, m+1):
node = ListNode(i)
pre.next = node
pre = node
pre.next = head # 最后一个节点指向头节点,形成循环链表
# 开始游戏,直到只剩下一只猴子
cur = pre = head
while cur.next != cur:
count = 1
while count != n:
pre, cur = cur, cur.next
count += 1
pre.next = cur.next # 将cur节点从链表中删除
cur = pre.next
print("胜出的猴子编号为:", cur.val)
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)