有100人按编号从1到100围成一个圈,从第一个人开始报数,报道数字5的时候把报数字3的人踢出去,然后从报数字5的下一个人继续报数字1,在这个圈子里一直报下去,最后报到剩下一个人结束报数。那么最后剩下的那个人的编号是多少?
约瑟夫环问题,网上搜一下,会有很多代码的
用Java实现的代码,仅供参考
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < 100; i++) {//初始化100个人
list.add(i+1);
}
int count = 1;//报数1-5,从1开始报
int curIndex = 0;//当前报数人下标,从第一个人开始报数
int removeIndex = 0;//要移除的报数人下标
while(list.size() > 1){//剩下最后一个人的时候退出
if(count == 3)//报到3时,记录当前报数人下标,用于移除
removeIndex = curIndex;
if(count == 5){//报到5时
count = 0;//重新报数
list.remove(removeIndex);//移除报数3的人
if(removeIndex <= curIndex)//移除的人在报数5的前面时,报数5的下标往前移一位
curIndex--;
}
count++;//下一个要报的数
curIndex++;//下一位报数人下标
if(curIndex >= list.size()){//最后一位报数完,回到第一位继续报数
curIndex = 0;
}
}
System.out.println(list.element());//输出剩下的最后一位的编号