Josephus 问题。有 n 个人围成一圈，排序排号，从第一个人开始报数（从 1 到 3 报数）， 凡报到 3 的人退出圈子，按顺序依次输出退出的人的编号。C++完整代码

#include <stdio.h>

int main() {
    int n, i, k = 0, m = 0, a[1000];
    scanf("%d", &n);  // 输入人数
    for (i = 0; i < n; i++) {
        a[i] = i + 1;  // 初始化数组，存储编号
    }
    while (m < n) {  // 当退出人数等于总人数时结束循环
        for (i = 0; i < n; i++) {
            if (a[i] != 0) {  // 如果该编号未被退出
                k++;  // 报数加1
            }
            if (k == 3) {  // 如果报数为3
                printf("%d ", a[i]);  // 输出该编号
                a[i] = 0;  // 将该编号标记为已退出
                k = 0;  // 报数清零
                m++;  // 退出人数加1
            }
        }
    }
    return 0;
}

相关问题

Josephus 问题。有 n 个人围成一圈，排序排号，从第一个人开始报数（从 1 到 3 报数）， 凡报到 3 的人退出圈子，按顺序依次输出退出的人的编号。

可以使用循环链表来模拟这个过程。首先将 n 个人连成一个环，然后从第一个人开始报数，每报到 3 就将该人从环中删除。重复这个过程直到只剩下一个人为止，期间删除的人的编号即为 Josephus 问题的解。

具体实现过程如下：

1. 定义一个结构体表示每个人，结构体中包括编号和指向下一个人的指针。

struct Person {
    int id;
    Person *next;
};

2. 创建 n 个人，连成一个环。

Person *createCircle(int n) {
    Person *head = new Person{1, nullptr};
    Person *curr = head;
    for (int i = 2; i <= n; i++) {
        curr->next = new Person{i, nullptr};
        curr = curr->next;
    }
    curr->next = head;
    return head;
}

3. 按照规则报数并删除人。

void josephus(int n) {
    Person *head = createCircle(n);
    Person *prev = nullptr, *curr = head;
    int count = 0;
    while (head->next != head) {  // 只剩下一个人时结束循环
        count++;
        if (count == 3) {
            count = 0;
            cout << curr->id << " ";  // 输出删除的人的编号
            prev->next = curr->next;  // 删除当前节点
            Person *temp = curr;
            curr = curr->next;
            delete temp;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
    cout << head->id;  // 输出最后剩下的人的编号
    delete head;
}

完整代码如下：

有n个人围成一圈顺序排号java_【转】约瑟夫环算法---------题目:有n个人围成一圈,顺序排号,从第一个开始报数(从1到3报数),凡报到3的人退出圈子,问最后最后留下的是原来第几号的那位....

这是经典的约瑟夫环问题，可以用递推或者数学方法解决。下面给出一个基于递推思路的 Java 代码实现：

public static int josephus(int n) {
    List<Integer> circle = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        circle.add(i);
    }
    int index = 0;
    while (circle.size() > 1) {
        index = (index + 2) % circle.size(); // 报数从0开始，所以加2
        circle.remove(index);
    }
    return circle.get(0);
}

这个算法的时间复杂度是 O(n^2)，因为每次删除操作需要移动数组元素。如果使用链表实现，时间复杂度可以优化到 O(n)。