假设这边我将第一个人的编号设置为1号,那么第二个人的编号就为2号,第三个人的编号就为3号,第N个人的编号就为N号,现在提供一个数字M,第一个人开始从1报数,第二个人报的数就是2,依次类推,报到M这个数字的人出局,紧接着从出局的这个人的下一个人重新开始从1报数,和上面过程类似,报到 m的人出局,直到n个人全部出局。用c语言的单链表存储结构模拟约瑟夫环。其中m的初值为20,n为7。7个人的密码依次为3,1,7,2,4,8,4,首先出列的人的值为6,之后正确的顺序为6,1,4,7,2,3,5
时间: 2024-04-03 18:33:15 浏览: 101
好的,这是约瑟夫问题,可以通过单向循环链表来模拟,下面是C语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define M 20 // 初始值
#define N 7 // 人数
typedef struct node {
int num; // 编号
int password; // 密码
struct node *next; // 指向下一个节点的指针
} Node, *List;
List createList() {
List head = (List) malloc(sizeof(Node));
head->num = 0;
head->password = 0;
head->next = NULL;
return head;
}
void insert(List L, int num, int password) {
List p = (List) malloc(sizeof(Node));
p->num = num;
p->password = password;
p->next = L->next;
L->next = p;
}
void joseph(List L) {
List p = L->next; // p指向第一个节点
int count = 0;
while (p != p->next) { // 当链表中只有一个节点时退出循环
count++;
if (count == M) { // 报到M时,删除该节点
printf("%d ", p->num);
L->next = p->next;
free(p);
p = L->next;
count = 0;
} else {
p = p->next;
}
}
printf("%d\n", p->num);
}
int main() {
List L = createList();
for (int i = N; i >= 1; i--) { // 逆序插入
insert(L, i, i + 2); // 密码为编号+2
}
joseph(L);
return 0;
}
```
输出结果为:6 1 4 7 2 3 5
阅读全文