C语言中不使用链表的约瑟夫环

以下是用C语言实现约瑟夫环的代码，不使用链表：

#include <stdio.h>

int josephus(int n, int m) {
    int idx = 0;
    for (int i = 2; i <= n; i++) {
        idx = (idx + m) % i;
    }
    return idx + 1;
}

int main() {
    int n = 5;
    int m = 3;
    printf("The last person left is at position: %d\n", josephus(n, m));
    return 0;
}

该算法利用数学方法，每次求出要删除的节点在当前剩余节点中的位置，然后直接计算出下一个要删除的节点在新的剩余节点中的位置。通过循环执行该过程，直到只剩下一个节点为止。该算法的时间复杂度为O(n)。

相关问题

用c语言写的循环链表约瑟夫环

循环链表约瑟夫环问题是一个经典的问题，可以用C语言来实现。以下是一个简单的C语言代码示例：

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

typedef struct node {
    int data;
    struct node *next;
} Node;

Node *createList(int n) {
    Node *head = NULL, *tail = NULL;
    for (int i = 1; i <= n; i++) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = i;
        newNode->next = NULL;
        if (head == NULL) {
            head = tail = newNode;
        } else {
            tail

c语言使用循环链表解决约瑟夫环问题

约瑟夫环问题是一个经典的数学问题，具体描述如下：有n个人（编号为1~n），围成一个圆圈，从第一个人开始报数，报到m的人出圈，然后从他的下一个人开始重新报数，重复这个过程，直到剩下最后一个人。

下面是使用循环链表解决约瑟夫环问题的C语言实现：

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

typedef struct node {
    int num;
    struct node *next;
} Node;

void create_circle(Node **head, int n) {
    Node *tail = NULL, *p = NULL;
    for (int i = 1; i <= n; i++) {
        p = (Node *)malloc(sizeof(Node));
        p->num = i;
        if (*head == NULL) {
            *head = p;
            tail = p;
        } else {
            tail->next = p;
            tail = p;
        }
    }
    tail->next = *head; // 将尾节点指向头节点，形成循环链表
}

void josephus_circle(Node **head, int m) {
    Node *p = *head, *q = NULL;
    int count = 0;
    while (p->next != p) {
        count++;
        if (count == m) {
            q->next = p->next;
            printf("%d出圈\n", p->num);
            free(p);
            p = q->next;
            count = 0;
        } else {
            q = p;
            p = p->next;
        }
    }
    printf("剩下%d号\n", p->num);
    *head = p;
}

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

首先，使用 `create_circle` 函数创建一个有 n 个节点的循环链表，其中头节点指针保存在 `head` 变量中。

然后，使用 `josephus_circle` 函数来模拟约瑟夫环问题。使用两个指针 `p` 和 `q` 遍历循环链表， `count` 记录报数的次数。当 `count` 等于 `m` 时，删除节点 `p`，并输出其编号。否则，指针 `p` 和 `q` 向后移动。当循环链表中只剩下一个节点时，输出其编号并退出循环。

最后，将头节点指针 `head` 指向最后剩下的节点，返回其编号。