约瑟夫环问题：一群人围成一个圈，开始报数，第三个死，下一个从1开始，问第几位最后不死

题目

有n个人围成一圈，顺序排号，从第一个人开始报数（从1~3报数），凡报到3的人退出圈子，
问最后留下的人原来排在第几号

分析

有n个人，围成一圈,顺序排号，从某人开始数到第三个的人出列，再接着从下一个人又从1开始报数，最终输出最终出列的人

java代码

package d0225;/*** @description: ${description}* @create: 2019-02-25* 约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。* 从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，* 数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。* 通常解决这类问题时我们把编号从0~n-1，最后 [1]  结果+1即为原问题的解* 有n个人围成一圈，顺序排号，从第一个人开始报数（从1~3报数），凡报到3的人退出圈子，问最后留下的人原来排在第几号**/
public class F {public static int f(int n){//初始化一个长度为n的boolean数组,并且全部赋值trueboolean[] array=new boolean[n];for(int i=0;i<n;i++){array[i]=true;}int result=0;//最终留在队伍里面的人:即数组的下标+1int index=0;//数组下标int numberOfArray=n;//循环后,数组的长度int counter=0;//报数的数组(1,2,3)while (numberOfArray>1){if(array[index]){//当index这个位置为默认true的时候,counter才加1,如果被改变为falsle则不计数counter++;//反方向思考,如果这个位置是false的话,代表这个人走了,那么就是下个人来喊,下个人要是还走了,就让下下个人来喊}if(counter==3){//计数到3且满足楼上的情况下array[index]=false;//人离开numberOfArray--;//人数减一counter=0;//从零计算}index++;//下标递增if(index==n){//下标循环index=0;}}for(int i=0;i<n;i++){//找出唯一剩下的人if(array[i]==true){result=i;break;}}return result+1;//默认数组是1-n(原先是0~n-1),需要加一}public static void main(String[] args) {System.out.println(f(3));System.out.println(f(4));System.out.println(f(5));System.out.println(f(6));System.out.println(f(7));}
}

结果

心得

让index下标递增,先处理好counter的增加(必须是true)
然后再处理报数是3的(删,计数归零,数组长度减一)