c语言用结构体要从n只猴子中选出一位大王。它们决定使用下面的方法: n只猴子围成一圈,从1到n顺序编号。从第q只猴子开始,从1到m报数,凡报到m的猴子退出竞选,下一次又从退出的那只猴子的下一只开始从1到m报数,直至剩下的最后一只为大王。请问最后哪只猴子被选为大王。 【输入形式】 控制台输入三个整数n,m,q。 【输出形式】 输出最后选为大王的猴子编号。 【样例输入】 7 4 3 【样例输出】 4 【样例说明】 输入整数n = 7,m = 4,n = 3,输出4
时间: 2024-02-11 10:09:27 浏览: 115
好的,这是一个经典的约瑟夫问题,可以用循环链表或者数组模拟。
以下是使用数组模拟的C语言代码实现:
```
#include <stdio.h>
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
int monkey[n];
for (int i = 0; i < n; i++) {
monkey[i] = i + 1;
}
int index = q - 1; // 从第q个猴子开始
while (n > 1) {
int count = m % n;
if (count == 0) {
count = n;
}
index = (index + count - 1) % n;
for (int i = index; i < n - 1; i++) {
monkey[i] = monkey[i + 1];
}
n--;
}
printf("%d", monkey[0]);
return 0;
}
```
代码逻辑如下:
1. 读入n,m,q。
2. 定义一个长度为n的数组,表示n只猴子的编号。
3. 初始化数组,将每只猴子的编号存入数组中。
4. 定义变量index,表示当前报数的猴子在数组中的下标,初始化为q-1。
5. 当猴子数量大于1时,进行循环:
1. 计算要报数的次数count,需要对猴子数量取模,如果count为0,说明要报到最后一只猴子,即count为猴子数量。
2. 根据count计算出下一个退出竞选的猴子在数组中的下标,即(index+count-1)%n。
3. 将退出竞选的猴子从数组中删除,即将其后面的所有猴子往前移动一位。
4. 猴子数量减少1。
6. 循环结束后,数组中剩下的最后一只猴子即为大王,输出其编号即可。
注意:数组下标从0开始,因此要将输入的q减1才能得到对应的下标。
阅读全文