| 约瑟夫环问题：一群人围成一个圈，开始报数，第三个死，下一个从1开始，问第几位最后不死 | 您所在的位置：网站首页 › 一人问一个问题的游戏 › 约瑟夫环问题：一群人围成一个圈，开始报数，第三个死，下一个从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数组,并且全部赋值true boolean[] array=new boolean[n]; for(int i=0;i1){ 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 |
| CopyRight 2018-2019 实验室设备网 版权所有 |