又见约瑟夫环:有M个人围坐成一圈, 编号依次从1开始递增直到M,现从编号为1的人开始报数,报到N的人出列,然后再从下一人开始重新报数,报到N的人出列;重复这一过程,直至所有人出列。所有出列的人再次按出列顺序围坐成一圈,并从第1人开始报数,这次为报到K的人出队列,然后再从下一人开始重新报数,报到K的人出列;重复这一过程,直至所有人出列。求最后出列次序。题目输入包括M、N、K三个正整数;N、K可能为1。题目要求按最后出队列顺序输出他们的编号,每个测试用例结果占一行,每个编号占4位。
时间: 2024-03-13 10:45:49 浏览: 379
这是一道经典的约瑟夫环问题,可以使用数组或链表来模拟这个过程。下面是一个使用数组来解决问题的示例代码:
```c
#include <stdio.h>
int main() {
int M, N, K;
scanf("%d%d%d", &M, &N, &K);
int nums[M];
for (int i = 0; i < M; i++) {
nums[i] = i + 1;
}
int count = 0;
int index = 0;
while (M > 0) {
count++;
if (count == N) {
printf("%-4d", nums[index]);
nums[index] = -1;
count = 0;
M--;
}
index++;
if (index == M) {
index = 0;
}
}
printf("\n");
for (int i = 0; i < M; i++) {
nums[i] = i + 1;
}
count = 0;
index = 0;
while (M > 0) {
count++;
if (count == K) {
printf("%-4d", nums[index]);
nums[index] = -1;
count = 0;
M--;
}
index++;
if (index == M) {
index = 0;
}
}
printf("\n");
return 0;
}
```
首先,读入 M、N、K 三个数,然后创建一个长度为 M 的数组 nums,用来表示每个人的编号。初始化数组为 1 到 M。
接下来,使用 count 和 index 变量来模拟报数和删除的过程。每次循环,count 加 1,如果 count 等于 N 或 K,就输出当前人的编号并将其从数组中删除,M 减 1。然后,index 加 1,如果 index 等于 M,就将其重新赋值为 0。直到数组中的所有人都被删除完为止。
最后,输出第一次和第二次删除的编号序列。注意,每个编号占 4 个字符,可以使用 printf 函数的格式化输出来实现。
这是一个简单的解决方案,如果您有其他实现方式或优化建议,欢迎分享!
阅读全文