约瑟夫环问题的一种描述是: 编号为1,2……n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数),开始时任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时值方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。试设计C语言一个程序,求出出列顺序。 提示:可以利用不带头结点的单向循环链表作为存储结构模拟此过程按照出列顺序打印出各人的编号。 例如,m的初值为20;n=7,7个人的密码依次是3,1,7,2,4,8,4,出列的顺序为6,1,4,7,2,3,5
时间: 2023-04-12 11:00:54 浏览: 234
以下是CSDN开发的C知道的回答:
可以利用不带头结点的单向循环链表作为存储结构模拟约瑟夫环问题。具体实现可以参考以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int num; // 编号
int password; // 密码
struct node *next; // 指向下一个节点的指针
} Node;
int main() {
int m, n, i;
Node *head, *p, *q;
printf("请输入m和n的值:");
scanf("%d%d", &m, &n);
head = (Node *)malloc(sizeof(Node));
head->num = 1;
printf("请输入第1个人的密码:");
scanf("%d", &head->password);
head->next = head;
p = head;
for (i = 2; i <= n; i++) {
q = (Node *)malloc(sizeof(Node));
q->num = i;
printf("请输入第%d个人的密码:", i);
scanf("%d", &q->password);
p->next = q;
q->next = head;
p = q;
}
p = head;
printf("出列顺序为:");
while (p->next != p) {
for (i = 1; i < m; i++) {
q = p;
p = p->next;
}
printf("%d ", p->num);
m = p->password;
q->next = p->next;
free(p);
p = q->next;
}
printf("%d\n", p->num);
free(p);
return 0;
}
```
如果您有其它问题,欢迎继续提问。
阅读全文