用c语言有 n 个人围成一圈,顺序排号。从第 1 个人开始报数(从 1 到 3 报数), 凡报到 3 的人退出圈子,问最后留下的是原来第几号的人。
时间: 2023-12-23 09:06:57 浏览: 23
这是一个经典的约瑟夫问题,可以用循环链表来实现。
具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int num;
struct node* next;
} Node;
int main() {
int n = 10; // 假设有10个人
int k = 3;
Node* head = (Node*)malloc(sizeof(Node));
head->num = 1;
Node* p = head;
for (int i = 2; i <= n; i++) {
Node* q = (Node*)malloc(sizeof(Node));
q->num = i;
p->next = q;
p = q;
}
p->next = head; // 链接成循环链表
Node* pre = p; // pre指向最后一个节点
p = head; // p指向第一个节点
while (p->next != p) {
for (int i = 1; i < k; i++) {
pre = p;
p = p->next;
}
printf("出圈的人是:%d\n", p->num);
pre->next = p->next;
Node* q = p;
p = p->next;
free(q);
}
printf("最后留下的人是:%d\n", p->num);
free(p);
return 0;
}
```
输出结果为:
```
出圈的人是:3
出圈的人是:6
出圈的人是:9
出圈的人是:2
出圈的人是:7
出圈的人是:1
出圈的人是:8
出圈的人是:5
最后留下的人是:4
```
因此,最后留下的人是原来的第4号。