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

```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. 定义一个结构体表示每个人，结构体中包括编号和指向下一个人的指针。 ```c++ struct Person { int id; Person *next; }; ``` 2. 创建 n 个人，连成一个环。 ```c++ 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. 按照规则报数并删除人。 ```c++ 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 代码实现： ```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)。

阅读全文

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