当前位置：首页 > news >正文

C语言解决约瑟夫环问题

news 2025/9/13 19:37:18

约瑟夫环问题是一个经典的数学问题，它的描述如下：有n个人围成一圈，从第1个人开始报数，数到第m个人出列，然后从出列的下一个人开始重新报数，数到第m个人出列，如此循环，直到最后一个人出列为止。本文将介绍如何使用链表来解决这个问题。

链表是一种数据结构，它由一系列节点组成，每个节点包含一个值和一个指针，指向下一个节点。链表的优点是可以动态地添加和删除元素，因此非常适合解决约瑟夫环问题。

我们可以使用单向循环链表来模拟约瑟夫环。具体来说，我们可以先创建一个包含n个节点的单向循环链表，每个节点表示一个人，然后从第一个节点开始一次遍历链表，每次遍历m个节点，并将当前节点从链表中删除。当链表中只剩下一个节点时，该节点即为最后一个出列的人。

以下是约瑟夫环问题的具体实现代码：

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
struct node {int value;struct node *next;
};// 创建一个包含n个节点的单向循环链表
struct node *create_list(int n) {struct node *head = NULL;struct node *current = NULL;for (int i = 1; i <= n; i++) {struct node *new_node = (struct node *)malloc(sizeof(struct node));new_node->value = i;new_node->next = NULL;if (head == NULL) {head = new_node;} else {current->next = new_node;}current = new_node;}current->next = head;return head;
}// 解决约瑟夫环问题
int josephus(int n, int m) {struct node *head = create_list(n);struct node *current = head;while (current->next != current) {for (int i = 1; i < m; i++) {current = current->next;}struct node *temp = current->next;current->next = current->next->next;free(temp);}int result = current->value;free(current);return result;
}int main() {int n = 10;int m = 3;int result = josephus(n, m);printf("The last person is %d\n", result);return 0;
}