用三种存储结构（顺序表，链表，静态链表）求解josuphu问题；设有n个人围坐在一圈，现从指定的第个人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，如此重复，直到所

该问题涉及到约瑟夫问题，即$n$个人围成一圈，从指定的第一个人开始报数，在报到第$m$个人出列后，再从下一个人开始重新报数，直到所有人全部出列为止。 解决该问题有多种存储结构（顺序表，链表，静态链表）和算法（递归，迭代，数学公式）。

相关问题

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

以下是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`函数求解。

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

链表方式实现该问题求解，可以按照以下步骤实现：

1. 定义猴子节点结构体，包含编号和指向下一个节点的指针：

struct monkey {
    int id;
    struct monkey *next;
};

2. 根据输入的m和n，创建m个猴子节点并构成一个循环链表：

struct monkey *create_monkeys(int m) {
    struct monkey *head = NULL, *p = NULL, *last = NULL;
    int i;
    // 创建m个猴子节点，并构成循环链表
    for (i = 1; i <= m; i++) {
        p = (struct monkey *) malloc(sizeof(struct monkey));
        p->id = i;
        if (head == NULL) {
            head = p;
        } else {
            last->next = p;
        }
        last = p;
    }
    // 循环链表
    last->next = head;
    return head;
}

3. 按照每次数到第n个猴子离开的规则，依次移除猴子节点，直到只剩一个节点为止：

int remove_monkey(struct monkey **head, int n) {
    struct monkey *p = *head, *q = NULL;
    int i;
    // 找到第n-1个猴子节点
    for (i = 1; i < n; i++) {
        q = p;
        p = p->next;
    }
    // 移除第n个猴子节点
    if (q == NULL) {
        *head = p->next;
    } else {
        q->next = p->next;
    }
    int id = p->id;
    free(p);
    return id;
}

int find_king(int m, int n) {
    // 创建m个猴子节点并构成循环链表
    struct monkey *head = create_monkeys(m);
    // 按照规则依次移除猴子节点，直到只剩一个节点
    while (head->next != head) {
        int id = remove_monkey(&head, n);
    }
    int king_id = head->id;
    free(head);
    return king_id;
}

完整代码如下：