约瑟夫问题c语言实现
时间: 2024-11-22 14:37:07 浏览: 57
约瑟夫问题是一个经典的算法题目,也被称为“环形链表”或“跳数问题”。其规则是:给定一个包含 n 个人的循环链表,从第一个人开始按顺序编号为 1,然后每个人顺时针移动 k 步。当某个人又回到原来的位置时,问题结束。你需要找出最后停留在起始位置的人的编号。
以下是使用 C 语言实现约瑟夫问题的一个简单版本,假设每个人编号都是整数,且 k 的范围较小:
```c
#include <stdio.h>
// 定义链表结构体
typedef struct {
int data;
struct Node *next;
} Node;
// 初始化链表
Node* createList(int n) {
Node* head = (Node*)malloc(sizeof(Node));
head->data = 1;
head->next = head;
for (int i = 2; i <= n; ++i) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = i;
newNode->next = head->next;
head->next = newNode;
}
return head;
}
// 模拟约瑟夫环问题
int josephusProblem(int n, int k) {
Node* slow = head;
Node* fast = head;
for (int i = 0; fast != NULL && fast != head; i++) {
fast = fast->next;
if (fast == head) { // 如果快指针到达头,则增加一轮
slow = slow->next;
fast = slow->next;
}
if (i % k == 0) { // 当慢指针遇到k的倍数位置时,删除该节点
Node* temp = slow->next;
free(temp);
slow->next = temp->next;
}
}
return slow->data;
}
int main() {
int n, k;
printf("请输入链表长度和步长:");
scanf("%d%d", &n, &k);
Node* head = createList(n);
int result = josephusProblem(n, k);
printf("最后剩下的那个人编号是:%d\n", result);
return 0;
}
```
阅读全文