编号是 1,2,„„,n 的 n 个人按照顺时针方向围坐一圈,每个人只有一个密码(正 整数)。一开始任选一个正整数作为报数上限值 m,从第一个仍开始顺时针方向自 1 开始顺序 报数,报到 m 时停止报数。报 m 的人出列,将他的密码作为新的 m 值,从他在顺时针方向 数据结构课程设计题目 8 的下一个人开始重新从 1 报数,如此下去,直到所有人全部出列为止。设计一个程序来求出 出列顺序利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。
时间: 2023-10-19 22:07:21 浏览: 83
约瑟夫(Josephus)环问题:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)
5星 · 资源好评率100%
好的,下面是一个用 C 语言单向循环链表实现约瑟夫环问题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct node {
int num; // 编号
int password; // 密码
struct node *next;
} Node;
// 定义链表结构体
typedef struct list {
Node *head;
Node *tail;
} List;
// 初始化链表
void init_list(List *list) {
list->head = NULL;
list->tail = NULL;
}
// 添加节点
void add_node(List *list, int num, int password) {
Node *new_node = (Node *) malloc(sizeof(Node));
new_node->num = num;
new_node->password = password;
new_node->next = NULL;
if (list->head == NULL) {
list->head = new_node;
} else {
list->tail->next = new_node;
}
list->tail = new_node;
list->tail->next = list->head;
}
// 删除节点
void delete_node(List *list, Node *prev, Node *current) {
if (prev == NULL) {
list->tail->next = current->next;
list->head = current->next;
} else {
prev->next = current->next;
}
printf("%d ", current->num); // 输出出列的编号
free(current);
}
// 约瑟夫环问题求解
void josephus(int n, int m) {
List list;
init_list(&list);
for (int i = 1; i <= n; i++) {
add_node(&list, i, rand() % 1000); // 随机生成密码
}
Node *prev = NULL;
Node *current = list.head;
int count = 0;
while (list.head != NULL) {
count++;
if (current->password == m) {
Node *next = current->next;
delete_node(&list, prev, current);
current = next;
m = current->password;
} else {
prev = current;
current = current->next;
m--;
}
}
printf("\n出列的总人数为:%d\n", count);
}
int main() {
int n, m;
printf("请输入总人数n和报数上限m:\n");
scanf("%d %d", &n, &m);
printf("出列的顺序为:");
josephus(n, m);
return 0;
}
```
在该程序中,我们使用了单向循环链表来模拟人围成一圈的情况,并使用链表的删除操作来模拟人出列的情况。在 `josephus` 函数中,我们先随机生成每个人的密码,然后依次遍历链表,模拟报数的过程。当报数为 m 时,删除当前节点,并将下一个节点的密码作为新的 m 值;否则,将当前节点设置为下一个节点,并将 m 减一。最终,当链表为空时,输出出列的总人数。
阅读全文