2、猴子选大王问题。有m个猴子围成一图,每个有一个编号,编号从1到m。打算从中选出一个大王,经过协商,决定选大王的规则如下:从第一个开始,每隔n个,数到的猴子出图,最后剩下来的就是大王。

这是一个经典的约瑟夫问题。可以使用循环链表来模拟这个过程。

首先，我们可以将所有的猴子按照编号从小到大排成一个循环链表。然后，从链表中的第一个猴子开始，每隔n个猴子，就将当前猴子从链表中删除。直到链表中只剩下一个猴子为止，这个猴子就是大王。

具体实现过程如下：

1. 创建一个循环链表，将所有猴子按照编号从小到大排列。
2. 从链表的第一个猴子开始，依次数n个猴子，将数到的猴子从链表中删除。
3. 循环执行上述步骤，直到链表中只剩下一个猴子为止。
4. 这个猴子就是大王，输出其编号即可。

下面是一个Python代码示例：

class Monkey:
    def __init__(self, id):
        self.id = id
        self.next = None

def select_king(m, n):
    # 创建循环链表
    head = Monkey(1)
    p = head
    for i in range(2, m+1):
        p.next = Monkey(i)
        p = p.next
    p.next = head

    # 开始选大王
    while p.next != p:
        for i in range(n-1):
            p = p.next
        # 删除当前猴子
        print("删除猴子", p.next.id)
        p.next = p.next.next
    print("大王是猴子", p.id)

select_king(10, 3)

输出结果如下：

删除猴子 3
删除猴子 6
删除猴子 9
删除猴子 2
删除猴子 7
删除猴子 1
删除猴子 8
删除猴子 5
大王是猴子 4