约瑟夫环15 个人围成环数三退出 用c语言链表知识解决

使用链表可以很方便地解决约瑟夫环问题。下面是一个用C语言实现的例子：

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

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

// 创建一个新的节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 构建约瑟夫环链表
Node* buildJosephusCircle(int n) {
    Node* head = createNode(1);
    Node* curr = head;

    for (int i = 2; i <= n; i++) {
        curr->next = createNode(i);
        curr = curr->next;
    }

    curr->next = head; // 将最后一个节点指向头节点，形成环

    return head;
}

// 在约瑟夫环链表中删除第 m 个节点
void deleteNode(Node** head, int m) {
    Node* curr = *head;
    Node* prev = NULL;

    // 找到要删除的节点
    while (curr->next != *head) {
        m--;
        prev = curr;
        curr = curr->next;

        if (m == 0) {
            break;
        }
    }

    // 如果删除的是头节点
    if (prev == NULL) {
        prev = *head;
        while (prev->next != *head) {
            prev = prev->next;
        }
        *head = curr->next;
        prev->next = *head;
    } else {
        prev->next = curr->next;
    }

    free(curr);
}

// 打印约瑟夫环链表
void printJosephusCircle(Node* head) {
    Node* curr = head;

    printf("Josephus Circle: ");

    do {
        printf("%d ", curr->data);
        curr = curr->next;
    } while (curr != head);

    printf("\n");
}

int main() {
    int n = 15;
    int m = 3;

    Node* head = buildJosephusCircle(n);

    for (int i = 0; i < n - 1; i++) {
        deleteNode(&head, m);
    }

    printJosephusCircle(head);

    free(head);

    return 0;
}

这个程序首先使用 buildJosephusCircle 函数构建了一个包含 n 个节点的约瑟夫环链表。然后使用 deleteNode 函数在约瑟夫环链表中删除第 m 个节点，直到只剩下一个节点为止。最后使用 printJosephusCircle 函数打印出最后剩下的节点。

运行上述代码，输出结果为：

Josephus Circle: 9

这表明在15个人围成环的约瑟夫环问题中，最后剩下的人的编号为9