使用C语言 编写程序，有n个人围成一圈，顺序排号。从第1个人开始1—3报数，凡报到3的人退出圈子，问最后留下的是原来第几号的那位。

好的，下面是使用C语言实现的代码，实现了约瑟夫问题的算法：

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

int josephus(int n);

int main()
{
    int n = 10;
    printf("最后留下的是原来第%d号的人\n", josephus(n));
    return 0;
}

int josephus(int n)
{
    int i, idx = 0;
    int *circle = (int*)malloc(sizeof(int) * n);
    for (i = 0; i < n; i++) {
        circle[i] = i + 1;
    }
    while (n > 1) {
        idx = (idx + 2) % n;
        int j;
        for (j = idx; j < n - 1; j++) {
            circle[j] = circle[j+1];
        }
        n--;
    }
    int last = circle[0];
    free(circle);
    return last;
}

这个算法的思路是，首先将所有人编号，然后将这些人放入一个圆圈中。从第一个人开始，每数到第三个人就将其删除，直到圆圈中只剩下一个人为止。最后留下的那个人就是原来第几号的人。

相关问题

编写c语言程序3．有 n 个人围成一圈，顺序排号。从第一个人开始报数（从 1 到 3 报数），凡报到 3 的人 退出圈子，问最后留下的是原来第几号的那位

以下是使用循环链表实现的 C 语言程序：

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

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

int main() {
    int n, count = 0, m = 3;
    printf("请输入总人数 n：");
    scanf("%d", &n);

    // 创建循环链表
    Node* head = (Node*)malloc(sizeof(Node));
    Node* p = head;
    for (int i = 1; i <= n; i++) {
        p->num = i;
        if (i == n) {
            p->next = head;
        } else {
            p->next = (Node*)malloc(sizeof(Node));
            p = p->next;
        }
    }

    // 开始报数
    while (p->next != p) {
        count++;
        if (count == m) {
            count = 0;
            printf("%d 号出圈\n", p->num);
            Node* q = p->next;
            p->num = q->num;
            p->next = q->next;
            free(q);
        }
        p = p->next;
    }

    printf("剩下的是 %d 号\n", p->num);

    return 0;
}

程序运行时，先输入总人数 n，然后程序会创建一个包含 n 个节点的循环链表。接下来，程序会模拟报数的过程，每当报到 3 时，程序会删除该节点。最后，当链表中只剩下一个节点时，程序输出该节点的编号，即为最后留下的人的编号。

用C语言编写程序解决问题：有 n 个人围成一圈，按顺序排号。从第 1 个人开始报数（从 1 到 3 报数），凡报到 3 的人退出圈子，问最后留下的那 位是原来的第几号。

这是一个经典的约瑟夫问题，可以使用循环链表来解决。具体思路如下：

1. 首先创建一个循环链表，表示 n 个人围成一圈。

2. 然后从第一个人开始，依次报数直到 3，把报数为 3 的人从链表中删除。

3. 继续从下一个人开始报数，重复步骤 2 直到只剩下一个人为止。

4. 返回最后剩下的那个人的编号。

下面是用 C 语言实现的代码：

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

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

int josephus(int n) {
    Node *head = NULL, *prev = NULL, *curr = NULL;
    int i, count;

    // 创建循环链表
    for (i = 1; i <= n; i++) {
        curr = (Node*)malloc(sizeof(Node));
        curr->number = i;
        if (prev) {
            prev->next = curr;
        } else {
            head = curr;
        }
        curr->next = head;
        prev = curr;
    }

    // 开始报数
    curr = head;
    while (curr->next != curr) {
        for (count = 1; count < 3; count++) {
            curr = curr->next;
        }
        prev = curr->next;
        curr->next = prev->next;
        free(prev);
    }

    // 返回最后剩下的那个人的编号
    return curr->number;
}

int main() {
    int n = 10;
    int winner = josephus(n);
    printf("The winner is %d\n", winner);
    return 0;
}

这个程序的时间复杂度为 O(n^2)，可以使用递推公式将时间复杂度优化到 O(n)。