c语言假设n个旅客排成一个环形,依次顺序编号1,2,…,n。从某个指定的第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到剩下k个旅客为止
时间: 2024-03-31 11:34:51 浏览: 50
有N个人围成一环形圈,第一个人从1开始报数,报道M的人出列,直到最后一个同学,请写出算法。.txt
可以使用循环链表来模拟这个过程,具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int num;
struct Node* next;
} Node;
// 创建一个长度为n的循环链表
Node* createList(int n) {
Node* head = (Node*)malloc(sizeof(Node));
Node* p = head;
for (int i = 1; i <= n; i++) {
Node* node = (Node*)malloc(sizeof(Node));
node->num = i;
p->next = node;
p = node;
}
p->next = head->next;
return head->next;
}
// 让从start开始的链表每m个节点删除一个,直到只剩下k个节点
void josephus(Node* start, int m, int k) {
Node* p = start;
while (p->next != p) {
// 找到第m个节点的前一个节点
for (int i = 1; i < m - 1; i++) {
p = p->next;
}
printf("%d ", p->next->num);
// 删除第m个节点
Node* tmp = p->next;
p->next = tmp->next;
free(tmp);
// 从下一个节点开始重新计数
p = p->next;
}
printf("%d\n", p->num);
}
int main() {
int n = 10;
int m = 3;
int k = 4;
Node* start = createList(n);
josephus(start, m, k);
return 0;
}
```
上面的代码中,createList函数用于创建一个长度为n的循环链表,josephus函数用于让从start开始的链表每m个节点删除一个,直到只剩下k个节点。最后在main函数中调用createList和josephus函数即可。
运行结果为:3 6 9 2
表示在10个旅客中,每数到第3个人就让其出列,最终只剩下4个旅客,他们在原来的序列中的位置分别为3、6、9、2。
阅读全文