一堆猴子都有编号,编号是1,2,3...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。要求:m及n要求从键盘输入,存储方式采用数组及链表两种方式实现该问题求解。
时间: 2023-05-25 13:05:34 浏览: 33
使用数组实现:
```
#include <stdio.h>
int main() {
int m, n;
printf("请输入猴子数量m:");
scanf("%d", &m);
printf("请输入数到第几只猴子出圈n:");
scanf("%d", &n);
// 初始化猴子编号数组
int monkeys[m];
for (int i = 0; i < m; i++) {
monkeys[i] = i + 1;
}
int count = 0; // 记录出圈的猴子数量
int index = -1; // 记录当前猴子的下标
while (count < m - 1) { // 还有超过1只猴子未出圈
for (int i = 0; i < n; i++) {
// 找到下一个未出圈的猴子
do {
index = (index + 1) % m;
} while (monkeys[index] == 0);
}
monkeys[index] = 0; // 标记猴子已出圈
count++;
}
// 找到最后一只未出圈的猴子
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>
typedef struct Node {
int data;
struct Node* next;
} Node;
int main() {
int m, n;
printf("请输入猴子数量m:");
scanf("%d", &m);
printf("请输入数到第几只猴子出圈n:");
scanf("%d", &n);
// 创建循环链表
Node* head = (Node*)malloc(sizeof(Node));
head->data = 1;
head->next = NULL;
Node* p = head;
for (int i = 2; i <= m; i++) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = i;
node->next = NULL;
p->next = node;
p = node;
}
p->next = head; // 最后一个节点指向头节点
int count = 0; // 记录出圈的猴子数量
Node* prev = NULL; // 记录当前猴子的前一个节点
while (count < m - 1) { // 还有超过1只猴子未出圈
for (int i = 0; i < n; i++) {
prev = p;
p = p->next;
}
prev->next = p->next; // 删除当前节点
free(p);
p = prev->next; // 更新当前节点
count++;
}
printf("最后一只猴子的编号是%d\n", p->data);
free(p);
return 0;
}
```