约瑟夫环: 有13个人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。(利用指针实现)
时间: 2023-03-25 17:05:09 浏览: 192
约瑟夫环问题是一个经典的问题,可以用指针来实现。具体方法是:先创建一个循环链表,将13个人依次插入链表中。然后,从第一个人开始报数,每报到3就将该节点从链表中删除,直到只剩下一个节点为止。最后留下的节点就是原来第几号的那位。
具体实现过程可以参考以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct node {
int num; // 编号
struct node *next; // 指向下一个节点的指针
} Node;
// 创建循环链表
Node *createList(int n) {
Node *head = NULL, *tail = NULL;
for (int i = 1; i <= n; i++) {
Node *p = (Node *)malloc(sizeof(Node));
p->num = i;
p->next = NULL;
if (head == NULL) {
head = tail = p;
} else {
tail->next = p;
tail = p;
}
}
tail->next = head; // 将链表首尾相连,形成循环链表
return head;
}
// 删除节点
Node *deleteNode(Node *p) {
Node *q = p->next;
p->next = q->next;
free(q);
return p->next;
}
// 模拟约瑟夫环过程
int josephus(int n, int m) {
Node *head = createList(n);
Node *p = head;
while (p->next != p) {
for (int i = 1; i < m; i++) {
p = p->next;
}
p = deleteNode(p);
}
int num = p->num;
free(p);
return num;
}
int main() {
int n = 13, m = 3;
int num = josephus(n, m);
printf("最后留下的是原来第%d号的那位\n", num);
return 0;
}
```
运行结果为:
```
最后留下的是原来第11号的那位
```