用C语言实现:有n个人围成一圈,顺序排号。从第1个人开始1-3报数,凡报到3的人退出圈子,问最后留下的是原来第几号的那位且记录每个被淘汰的人是在第几圈(1圈中所有人员报数完成后圈数加1)报数时被淘汰的。
时间: 2023-12-27 15:18:20 浏览: 60
好的,以下是用C语言实现约瑟夫问题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int pos;
int round;
} Eliminated;
int josephus(int n, Eliminated eliminated[]) {
int *alive = (int*) malloc(n * sizeof(int));
int cnt = 0, pos = 0, round = 1;
for (int i = 0; i < n; i++) {
alive[i] = 1;
}
while (1) {
if (alive[pos] == 1) {
cnt += 1;
if (cnt == 3) {
eliminated[pos].pos = pos+1;
eliminated[pos].round = round;
alive[pos] = 0;
cnt = 0;
}
}
pos = (pos + 1) % n;
if (pos == 0) {
round += 1;
}
if (n - round + 1 == 1) {
break;
}
}
int result = -1;
for (int i = 0; i < n; i++) {
if (alive[i] == 1) {
result = i+1;
break;
}
}
free(alive);
return result;
}
int main() {
int n;
printf("Enter the number of people: ");
scanf("%d", &n);
Eliminated eliminated[n];
int result = josephus(n, eliminated);
printf("The last person standing is: %d\n", result);
printf("Eliminated people:\n");
for (int i = 0; i < n-1; i++) {
printf("Position: %d, Round: %d\n", eliminated[i].pos, eliminated[i].round);
}
return 0;
}
```
在main函数中,我们首先通过scanf函数获得人数n,然后定义Eliminated结构体数组eliminated,用于记录每个被淘汰的人是在第几圈报数时被淘汰的。接着调用josephus函数,传入人数n和eliminated数组,得到最后留下的人和每个被淘汰的人是在第几圈报数时被淘汰的。最后输出结果即可。
需要注意的是,为了方便记录每个被淘汰的人是在第几圈报数时被淘汰的,我们定义了一个Eliminated结构体,其中包含两个成员变量:pos表示被淘汰的人在原始数组中的位置,round表示被淘汰的人是在第几圈报数时被淘汰的。在josephus函数中,每次淘汰一个人时,我们将其位置和当前圈数记录在eliminated数组中。
阅读全文