进行1-m的报数,删除第n只猴子,剩下的猴子否为1,输出猴子大王的序列c语言编写
时间: 2024-01-24 21:17:40 浏览: 29
以下是一个简单的实现,其中使用了循环链表来表示猴子的环:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct monkey {
int num;
struct monkey *next;
} Monkey;
int main() {
int m, n, i;
printf("请输入猴子的总数m:");
scanf("%d", &m);
printf("请输入要删除的猴子的位置n:");
scanf("%d", &n);
// 创建猴子环
Monkey *head = (Monkey*)malloc(sizeof(Monkey));
head->num = 1;
Monkey *tail = head;
for (i = 2; i <= m; i++) {
Monkey *new_monkey = (Monkey*)malloc(sizeof(Monkey));
new_monkey->num = i;
tail->next = new_monkey;
tail = new_monkey;
}
tail->next = head; // 猴子环形成
// 开始报数并删除猴子
Monkey *p = head, *prev = tail;
while (p->next != p) {
for (i = 1; i < n; i++) {
prev = p;
p = p->next;
}
prev->next = p->next;
printf("第%d只猴子被删除\n", p->num);
free(p);
p = prev->next;
}
// 输出最后剩下的猴子
printf("猴子大王的序号是:%d\n", p->num);
return 0;
}
```
需要注意的是,这个算法的时间复杂度为$O(mn)$,当$m$和$n$非常大时,效率会非常低下。实际上,有更快的算法可以在$O(m)$的时间复杂度内解决这个问题,但需要使用数学方法,这里就不再赘述了。