c 语言约瑟夫环问题

C语言中的约瑟夫环问题是一个经典的数学问题，它的描述如下：有n个人围成一圈，从第一个人开始报数，报到m的人出列，然后从出列的下一个人开始重新报数，直到所有人都出列为止。现在让我们来介绍一种解决这个问题的常见方法。

一种常见的解决方法是使用循环链表来模拟这个过程。首先，我们可以创建一个包含n个节点的循环链表，每个节点表示一个人，并且节点之间通过指针连接成一个环形结构。然后，我们从第一个节点开始，依次遍历链表，每次遍历m个节点，将第m个节点从链表中删除。重复这个过程，直到链表中只剩下一个节点为止。

下面是一个使用C语言实现约瑟夫环问题的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建循环链表
Node* createCircularLinkedList(int n) {
    Node* head = NULL;
    Node* prev = NULL;
    
    for (int i = 1; i <= n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;
        
        if (head == NULL) {
            head = newNode;
        } else {
            prev->next = newNode;
        }
        
        newNode->next = head;
        prev = newNode;
    }
    
    return head;
}

// 解决约瑟夫环问题
void josephusProblem(Node** head, int m) {
    Node* current = *head;
    Node* prev = NULL;
    
    while (current->next != current) {
        // 找到第m个节点
        for (int i = 1; i < m; i++) {
            prev = current;
            current = current->next;
        }
        
        // 删除第m个节点
        prev->next = current->next;
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    
    *head = current;
}

// 打印最后剩下的节点
void printLastNode(Node* head) {
    printf("最后剩下的节点是：%d\n", head->data);
}

int main() {
    int n, m;
    printf("请输入总人数n：");
    scanf("%d", &n);
    printf("请输入报数m：");
    scanf("%d", &m);
    
    Node* head = createCircularLinkedList(n);
    josephusProblem(&head, m);
    printLastNode(head);
    
    return 0;
}

这段代码首先通过`createCircularLinkedList`函数创建了一个包含n个节点的循环链表，然后通过`josephusProblem`函数解决约瑟夫环问题，最后通过`printLastNode`函数打印出最后剩下的节点。