Joseph问题:设编号为1,2,…,n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,他的下一位又从1开始报数,数到m的那个人又出列,…依次类推,直到所有的人出列为止,因此产生一个出列编号的序列。 提示:应创建循环链表来存储数据,链表结点的数据域用来存储该结点的编号,出列结点应从链表中删除,直到最后一个结点为止。用C语言编程实现
时间: 2024-02-23 17:58:25 浏览: 74
好的,这是一个经典的约瑟夫问题,我可以为您提供一个基于循环链表的C语言实现。以下是代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int num;
struct Node* next;
} Node;
// 创建循环链表
Node* create_list(int n) {
Node* head = (Node*)malloc(sizeof(Node));
head->num = 1;
head->next = NULL;
Node* prev = head;
for (int i = 2; i <= n; i++) {
Node* cur = (Node*)malloc(sizeof(Node));
cur->num = i;
cur->next = NULL;
prev->next = cur;
prev = cur;
}
prev->next = head;
return head;
}
// 删除结点
Node* delete_node(Node* prev, Node* cur) {
prev->next = cur->next;
Node* next = cur->next;
free(cur);
return next;
}
// 约瑟夫问题求解
void joseph(int n, int m) {
Node* head = create_list(n);
Node* cur = head;
Node* prev = NULL;
while (cur->next != cur) {
for (int i = 1; i < m; i++) {
prev = cur;
cur = cur->next;
}
printf("%d ", cur->num);
cur = delete_node(prev, cur);
}
printf("%d\n", cur->num);
free(cur);
}
int main() {
int n, m;
printf("请输入总人数n和报数m:");
scanf("%d %d", &n, &m);
printf("出列的顺序为:");
joseph(n, m);
return 0;
}
```
您可以在主函数中输入总人数n和报数m,程序会输出出列的顺序。
阅读全文