题目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))