用C用语言写有n人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来的第几号的那位
时间: 2023-12-23 16:49:56 浏览: 30
这是经典的约瑟夫问题,可以使用循环链表来解决。
具体思路如下:
1. 定义一个链表节点结构体,包含当前节点编号和指向下一个节点的指针。
2. 构建一个循环链表,将n个人依次插入链表中。
3. 从第一个节点开始,按照1、2、3的顺序报数,每报到3就将当前节点从链表中删除。
4. 循环执行上述步骤,直到链表中只剩下一个节点,这个节点就是最后留下的人的编号。
下面是C语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int num; // 当前节点编号
struct Node* next; // 指向下一个节点的指针
} Node;
// 构建循环链表
Node* buildList(int n) {
Node* head = NULL;
Node* tail = NULL;
for (int i = 1; i <= n; i++) {
Node* node = (Node*)malloc(sizeof(Node));
node->num = i;
node->next = NULL;
if (head == NULL) {
head = node;
} else {
tail->next = node;
}
tail = node;
}
tail->next = head; // 将链表尾部连接到头部,形成循环链表
return head;
}
// 约瑟夫问题求解函数
int josephus(int n) {
Node* head = buildList(n); // 构建循环链表
Node* prev = NULL;
Node* curr = head;
int count = 0;
while (curr->next != curr) { // 当链表中只剩下一个节点时结束循环
count++;
if (count == 3) { // 报数到3,删除当前节点
prev->next = curr->next;
free(curr);
curr = prev->next;
count = 0;
} else {
prev = curr;
curr = curr->next;
}
}
int result = curr->num; // 最后留下的节点就是链表中唯一的节点
free(curr);
return result;
}
int main() {
int n = 10; // 有10个人
int result = josephus(n);
printf("The last person is number %d.\n", result);
return 0;
}
```
运行结果:
```
The last person is number 4.
```
说明最后留下的是原来的第4号的那位。