有n人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来的第几号的那位?用C语言写
时间: 2023-11-27 14:54:45 浏览: 41
可以使用循环链表来模拟这个过程。具体的代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义循环链表节点结构体
typedef struct node {
int num; // 编号
struct node *next; // 指向下一个节点的指针
} Node;
// 创建循环链表
Node *createList(int n) {
Node *head = NULL;
Node *prev = NULL;
for (int i = 1; i <= n; i++) {
Node *p = (Node *)malloc(sizeof(Node));
p->num = i;
if (prev != NULL) { // 如果不是第一个节点
prev->next = p;
} else { // 如果是第一个节点
head = p;
}
prev = p;
}
prev->next = head; // 最后一个节点指向头节点,形成循环链表
return head;
}
// 模拟报数过程,返回最后剩下的节点
Node *countOff(Node *head, int m) {
Node *p = head;
while (p != p->next) { // 只要还有两个及以上的节点
// 报数
for (int i = 1; i < m-1; i++) {
p = p->next;
}
// 删除节点
Node *q = p->next;
p->next = q->next;
free(q);
// 下一个节点开始报数
p = p->next;
}
return p; // 最后剩下的节点
}
int main() {
int n, m;
printf("请输入总人数和报数的数字:");
scanf("%d %d", &n, &m);
Node *head = createList(n);
Node *last = countOff(head, m);
printf("最后剩下的是原来的第%d号的那位\n", last->num);
return 0;
}
```
其中,`createList`函数用于创建循环链表,`countOff`函数用于模拟报数过程。最后输出最后剩下的节点的编号即可。