有n个人围成一圈顺序排号java_【转】约瑟夫环算法---------题目:有n个人围成一圈,顺序排号,从第一个开始报数(从1到3报数),凡报到3的人退出圈子,问最后最后留下的是原来第几号的那位....
时间: 2023-12-15 08:22:33 浏览: 171
这是经典的约瑟夫环问题,可以用递推或者数学方法解决。下面给出一个基于递推思路的 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)。
相关问题
有n个人围成一圈顺序排号c语言约瑟夫环算法---------题目:有n个人围成一圈,顺序排号,从第一个开始报数(从1到3报数),凡报到3的人退出圈子,问最后最后留下的是原来第几号的那位..
同样是约瑟夫环问题,使用C语言可以使用循环链表或者模拟法来解决。下面给出一种使用模拟法的解法。
```c
#include <stdio.h>
#include <stdlib.h>
int getLastRemaining(int n) {
int i, count, index;
int *arr = (int*) malloc(n * sizeof(int));
for (i = 0; i < n; i++) {
arr[i] = i + 1;
}
count = 0;
index = 0;
while (n > 1) {
if (arr[index] != 0) {
count++;
}
if (count == 3) {
arr[index] = 0;
count = 0;
n--;
}
index = (index + 1) % n;
}
for (i = 0; i < n; i++) {
if (arr[i] != 0) {
break;
}
}
free(arr);
return arr[i];
}
int main() {
int n;
printf("请输入人数n:");
scanf("%d", &n);
printf("最后留下的是原来第%d号的那位\n", getLastRemaining(n));
return 0;
}
```
在这个解法中,我们使用一个数组来模拟环,数组里的每一个元素表示这个位置上的人是否还在游戏中。在每次报数到3时,我们将该位置的人退出游戏,同时将数组中的对应元素设为0。最后剩下的那个人即为原来的第几号。
有n个人围成一圈顺序排号java_:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。...
这道题可以使用约瑟夫环算法来解决。具体做法如下:
1. 创建一个长度为n的数组,表示n个人是否还在圈子中,初始值都为true。
2. 从第一个人开始报数,每报到3的人就将他的状态改为false,然后重新开始报数。
3. 循环执行步骤2,直到只剩下一个人为止。
4. 遍历数组,找到最后一个状态为true的人,就是最后留下的人。
Java代码实现如下:
```java
public static int lastRemaining(int n) {
boolean[] people = new boolean[n];
Arrays.fill(people, true);
int count = 0, index = 0, left = n;
while (left > 1) {
if (people[index]) {
count++;
if (count == 3) { // 报到3
people[index] = false;
count = 0;
left--;
}
}
index++;
if (index == n) { // 循环遍历
index = 0;
}
}
for (int i = 0; i < n; i++) { // 找到最后一个人
if (people[i]) {
return i + 1;
}
}
return -1;
}
```
其中,n表示圈中的人数,返回最后留下的人的原来编号。
阅读全文