一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。要求:m及n从键盘输入,存储方式采用数组及链表两种方式实现该问题求解。 用c语言
时间: 2023-05-25 20:06:02 浏览: 33
数组实现:
```
#include <stdio.h>
int main() {
int n, m;
printf("请输入猴子总数m和每隔n个猴子出圈的编号n:");
scanf("%d%d", &m, &n);
int monkeys[m];
for (int i = 0; i < m; i++) {
monkeys[i] = i + 1;
}
int count = 0, index = 0;
while (count < m - 1) {
int i = 0;
while (i < n) {
if (monkeys[index] != 0) {
i++;
}
if (i == n) {
count++;
monkeys[index] = 0;
}
index = (index + 1) % m;
}
}
for (int i = 0; i < m; i++) {
if (monkeys[i] != 0) {
printf("大王编号为:%d\n", monkeys[i]);
break;
}
}
return 0;
}
```
链表实现:
```
#include <stdio.h>
#include <stdlib.h>
struct Node {
int num;
struct Node* next;
};
int main() {
int n, m;
printf("请输入猴子总数m和每隔n个猴子出圈的编号n:");
scanf("%d%d", &m, &n);
struct Node* head = (struct Node*) malloc(sizeof(struct Node));
head->num = 1;
head->next = NULL;
struct Node* prev = head;
for (int i = 2; i <= m; i++) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->num = i;
node->next = NULL;
prev->next = node;
prev = node;
}
prev->next = head;
struct Node* p = head;
while (m > 1) {
for (int i = 1; i < n; i++) {
p = p->next;
}
struct Node* temp = p->next;
p->next = temp->next;
printf("%d号猴子出圈\n", temp->num);
free(temp);
m--;
}
printf("大王编号为:%d\n", p->num);
free(p);
return 0;
}
```