一共有n个人,围成一圈,从1开始报数,数到m的人出局,然后重新开始报数。算出出局的人的顺序。用链式存储结构
时间: 2023-05-21 16:01:40 浏览: 241
Python使用列表完成程序的编写:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到m报数),凡是报到m的人退出圈子,问最后留下的是原来第几号的人。
5星 · 资源好评率100%
这是一个经典的约瑟夫问题,可以使用循环链表来解决。具体的算法如下:
1. 创建一个循环链表,其中每个节点表示一个人,节点的值为该人的编号。
2. 从第一个节点开始,依次遍历链表,每遍历到第m个节点,就将该节点从链表中删除。
3. 删除节点后,从下一个节点继续遍历,直到链表中只剩下一个节点为止。
4. 最后剩下的节点即为最后一个出局的人。
以下是用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* next;
} Node;
Node* createList(int n) {
Node* head = NULL;
Node* prev = NULL;
for (int i = 1; i <= n; i++) {
Node* node = (Node*)malloc(sizeof(Node));
node->value = i;
node->next = NULL;
if (prev == NULL) {
head = node;
} else {
prev->next = node;
}
prev = node;
}
prev->next = head; // 将链表首尾相连,形成循环链表
return head;
}
void printList(Node* head) {
Node* node = head;
do {
printf("%d ", node->value);
node = node->next;
} while (node != head);
printf("\n");
}
void josephus(int n, int m) {
Node* head = createList(n);
Node* prev = NULL;
Node* node = head;
while (node->next != node) {
for (int i = 1; i < m; i++) {
prev = node;
node = node->next;
}
prev->next = node->next;
printf("%d ", node->value);
free(node);
node = prev->next;
}
printf("%d\n", node->value);
free(node);
}
int main() {
int n, m;
printf("请输入 n 和 m:");
scanf("%d %d", &n, &m);
printf("出局的人的顺序为:");
josephus(n, m);
return 0;
}
```
例如,当输入 n=7, m=3 时,输出结果为:
```
请输入 n 和 m:7 3
出局的人的顺序为:3 6 2 7 5 1 4
```
注意:这个算法的时间复杂度为 O(nm),当 n 和 m 很大时,可能会超时。可以使用数学方法优化算法,将时间复杂度降为 O(n)。但是由于本题只要求用链式存储结构解决,因此不再赘述。
阅读全文