有一道java编程题求组

Question

有500个小朋友，围成一个圈，从第一个开始数1，数到3的小朋友退出，后面继续从1开始数，数到3的小朋友退出，这样执行下去，最后留下的小朋友是哪个我还没有学动态数组，用基本数组与循环应该如何写这个，求思路啊，头发都要想掉了就是转不出来

Answer 1

public static void main(String[] args) {

int[] all = new int[500];

for (int i = 0; i < 500; i++) {

all[i] = i + 1;

}

while (all.length >= 3) {

int length = all.length;

int j = 0;

for (int i = 0; i < length; i++) {

if ((i + 1) % 3 == 0) {

all[i] = 0;

} else {

j++;

}

}

int[] newary = new int[j];

int a = 0;

for (int i = 0; i < length; i++) {

if (all[i] != 0) {

newary[a++] = all[i];

}

}

all = new int[j];

all = newary;

}

for (int i = 0; i < all.length; i++) {

System.out.println(all[i]);

}

}

Answer 2

简单讲一下下思路吧，设一个数组，里面有500个1，被踢掉就从1变成0，用循环加判断语句执行

Answer 3

典型的约瑟夫环问题。

1. 最普通的方式就是模拟整个过程，建立boolean数组，true表示此人已出列，false表示此人还在圈子中。模拟整个过程。时间复杂度为（3*500）（如果不懂可以再追问）

2. 用数学方法得到递推公式：F(i) = ( F(500-1)+3 )%500

   
   

3. public class ProgramTest {
       public static void  main(String[] args) {
           final int N =500;
           final int M =3;
           
           int result =0;
           for(int i=2;i<=N;++i){
               result = (result+M)%i
           }
           
           System.out.print(result);
           
       }
   }