有n个人围成一圈,顺序从1开始排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位C语言
时间: 2023-11-23 20:57:52 浏览: 92
这是一个经典的约瑟夫问题,可以用循环链表来模拟。具体的解决方法如下:
1. 首先创建一个循环链表,并将n个人依次加入链表中。
2. 从第一个人开始,依次报数,每报数到3的人将其从链表中删除。
3. 重复步骤2,直到链表中只剩下一个人为止,这个人即为最后留下的人。
下面是用C语言实现约瑟夫问题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int num; // 编号
struct node *next;
} Node, *LinkList;
LinkList createLinkList(int n) {
LinkList head = (LinkList)malloc(sizeof(Node));
head->num = 1;
head->next = NULL;
LinkList tail = head;
for (int i = 2; i <= n; i++) {
Node *p = (Node*)malloc(sizeof(Node));
p->num = i;
p->next = NULL;
tail->next = p;
tail = p;
}
tail->next = head; // 将尾节点指向头节点,形成循环链表
return head;
}
int joseph(LinkList head, int m) {
LinkList p = head, q = NULL;
while (p->next != p) { // 当链表中只剩一个节点时退出循环
for (int i = 1; i < m; i++) { // 找到第m个节点
q = p;
p = p->next;
}
q->next = p->next; // 将第m个节点从链表中删除
free(p);
p = q->next; // 继续从下一个节点开始报数
}
return p->num; // 返回最后留下的节点编号
}
int main() {
int n = 10; // 总人数
int m = 3; // 报数到3的人退出
LinkList head = createLinkList(n);
int num = joseph(head, m);
printf("最后留下的是原来第%d号的那位\n", num);
return 0;
}
```
输出结果为:
```
最后留下的是原来第4号的那位
```
阅读全文