Python3.猴子选王 一堆猴子都有编号，编号是1，2，3.，这群猴子（n个）按照1~n的顺序围坐一圈，从第1开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

Python3中的“猴子选王”问题，也被称为“环形链表找到中间结点”或“跳过每m个节点”，是一个常见的算法题。假设我们有一组猴子，每个猴子有一个唯一的编号，并且按照这个编号形成一个环形列表。游戏规则是从第一个猴子开始，每隔m个位置移动一次，直到只剩下一个猴子为止，这个剩下的猴子就是“大王”。

解决这个问题的一种常见思路是使用两个指针，一个每次移动一个位置（快指针），另一个每次移动m个位置（慢指针）。当快指针到达终点时，慢指针通常会停在最后一个猴子的位置，因为它是按m倍步长前进的。通过这种方法，我们可以快速确定最终的大王。

以下是Python的一个简单实现：

def findMonkey(self, n: int, m: int) -> int:
    # 如果m能整除n，说明每个猴子都会被跳过一轮，所以返回n
    if n % m == 0:
        return n

    fast = 1
    slow = 1
    while True:
        fast = (fast + m - 1) % n + 1
        slow = (slow + 1) % n + 1
        if fast == slow:
            break

    return slow

相关问题

题目1:猴子选王(学时:4) -堆猴子都有编号，编号是1，2,3….m,这群猴子(m个)按照1-m 的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求:m及n要求从键盘输入，存储方式采用数组及链表两种方式实现该问题求解。

解题思路：

该问题可以使用数组或链表两种方式求解，因为求解过程中需要频繁地从数据结构中删除元素，所以链表方式会更加方便一些。具体思路如下：

1. 读入猴子数量m、数到第n只猴子时离开圈的数值n。

2. 创建一个链表，表示初始时所有的猴子围成一圈，每个节点包含该猴子的编号和指向下一个猴子的指针。

3. 按照题目要求模拟猴子选王的过程，遍历链表删除该离开圈的猴子节点，直到链表中只剩下最后一只猴子。

4. 输出最后一只猴子的编号，即为大王的编号。

代码实现：

链表方式：

class Node:
    def __init__(self, number, next=None):
        self.number = number
        self.next = next

def monkey_king(m, n):
    # 构造循环链表
    head = Node(1)
    p = head
    for i in range(2, m+1):
        p.next = Node(i)
        p = p.next
    p.next = head

    # 模拟猴子选王的过程
    p = head
    while p.next != p:
        # 找到第n-1只猴子
        for i in range(n-1):
            p = p.next
        # 删除第n只猴子
        q = p.next
        p.next = q.next
        del q
    return p.number

m = int(input('请输入猴子数量m：'))
n = int(input('请输入数到第n只猴子时离开圈的数值n：'))
print('大王的编号是：', monkey_king(m, n))

数组方式：

def monkey_king(m, n):
    monkeys = [i+1 for i in range(m)]  # 构造初始猴子数组
    i = 0  # 当前选手的下标
    while len(monkeys) > 1:
        i = (i + n - 1) % len(monkeys)  # 找到需要删除的猴子的下标
        monkeys.pop(i)  # 删除该猴子
    return monkeys[0]

m = int(input('请输入猴子数量m：'))
n = int(input('请输入数到第n只猴子时离开圈的数值n：'))
print('大王的编号是：', monkey_king(m, n))

本关任务：一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1~m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。利用单向循环链表模拟此过程，依次输出出圈的猴子编号。

这个任务是一个典型的环形链表操作问题，可以使用动态规划或者模拟的方式来解决。首先，我们需要创建一个单向循环链表，其中每个节点包含一个猴子编号和指向下一个节点的指针。然后按照题目描述的过程：

1. 初始化一个计数器`count`为1，表示当前正在计数的猴子。
2. 遍历链表，对于每个节点：
a. 如果当前节点的编号等于`count`，那么删除这个节点，并将`count`加1。
b. 继续遍历下一个节点（即上一个节点的下一个节点），因为是循环链表，最后一个节点的下一个节点应该是第一个节点。
3. 当链表只剩下一个节点时，这个节点就是大王，它的编号即为最终结果。

每次删除节点后，都需要更新链表的结构，保证循环链表的完整性。以下是Python的一个简单示例：

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None if value == m else nodes[(value + 1) % m]  # 单向循环链接

def find_monkey_king(nodes, n, m):
    current = nodes[0]
    count = 1
    while len(nodes) > 1:
        if current.value == count:
            del nodes[count - 1]  # 删除节点
            count += 1
        current = current.next
    return current.value  # 返回大王编号

# 创建链表并初始化
nodes = [Node(i) for i in range(1, m+1)]
result = find_monkey_king(nodes, n, m)
print("大王的编号是:", result)