使用c语言编写:使用c语言编写:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始以6作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,再从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。 输入格式: 首先输入一个整数T,表示测试数据的组数,然后是T组测试数据。每组测试数据第一行输入n,第二行输入n个不超过20的正整数,依次表示这n个人所持有的密码。 输出格式: 对于每组测试,按照出列的顺序输出各人的编号。每两个编号之间留一个空格。
时间: 2023-10-19 17:07:19 浏览: 144
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100 // 最多人数
int n; // 人数
int m; // 报数上限
int a[MAX_N]; // 密码
int pos[MAX_N]; // 每个人的位置
int out[MAX_N]; // 出列顺序
// 执行约瑟夫环算法
void josephus() {
int i, j;
int cnt = 0; // 已经出列的人数
int cur = 0; // 当前报数的人的位置
for (i = 0; i < n; i++) {
pos[i] = i; // 初始化每个人的位置
}
while (cnt < n) {
int idx = cur % n; // 当前报数的人的编号
int num = a[pos[idx]]; // 当前报数的人的密码
// 如果这个人还没有出列
if (out[pos[idx]] == 0) {
cur++; // 继续报数
if (cur % m == 0) { // 报到m了
out[pos[idx]] = cnt + 1; // 记录这个人的出列顺序
cnt++; // 已经出列的人数加1
m = num; // 更新报数上限
}
}
pos[idx] = (idx + 1) % n; // 更新当前报数的人的位置
}
}
int cmp(const void *a, const void *b) {
int a_idx = *((int *)a);
int b_idx = *((int *)b);
return out[a_idx] - out[b_idx];
}
int main() {
int t, i, j;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
out[i] = 0;
}
m = 6; // 初始报数上限
josephus(); // 执行约瑟夫环算法
// 按照出列顺序排序并输出
qsort(pos, n, sizeof(int), cmp);
for (i = 0; i < n; i++) {
if (i > 0) {
printf(" ");
}
printf("%d", pos[i] + 1);
}
printf("\n");
}
return 0;
}
```
阅读全文