黑马程序员技术交流社区

标题: 有n个人围成一圈，顺序排号。 [打印本页]

---

作者: 下一秒温存    时间: 2014-11-11 10:43
标题: 有n个人围成一圈，顺序排号。
有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。
import java.util.Scanner;
public class Ex37 {
        public static void main(String[] args) {
                   Scanner s = new Scanner(System.in);
                   int n = s.nextInt();
                   boolean[] arr = new boolean[n];
                   for(int i=0; i<arr.length; i++) {
                    arr[i] = true;//下标为TRUE时说明还在圈里
                   }
                   int leftCount = n;
                   int countNum = 0;
                   int index = 0;
                   while(leftCount > 1) {
                    if(arr[index] == true) {//当在圈里时
                     countNum ++; //报数递加
                     if(countNum == 3) {//报道3时
                      countNum =0;//从零开始继续报数
                      arr[index] = false;//此人退出圈子
                      leftCount --;//剩余人数减一
                     }
                    }
                    index ++;//每报一次数，下标加一
                    if(index == n) {//是循环数数，当下标大于n时，说明已经数了一圈，
                     index = 0;//将下标设为零重新开始。
                    }
                   }
                   for(int i=0; i<n; i++) {
                    if(arr[i] == true) {
                     System.out.println(i);
                    }
                   }
     }
}

---

作者: M_______r    时间: 2014-11-11 17:45
！！！！！！就是一约瑟夫环啊

---

作者: lighter    时间: 2014-11-11 19:33
话说，入学考试碰到了相似的题

/**
* 10.有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，从1报数，到14退出。
*           问：最后剩下的是100人中的第几个人？
*
* 思路：
*                 方法一：标准循环解法：用一个ArrayList存储100个数，从1开始数，数到14的倍数，集合中对应的元素被移除，
*                                 以此类推，直到剩下一个元素为止，这个元素的数字就为题目的答案。
*                 方法二：约瑟夫标准循环非递归解法：假设总人数为n-1时从第1个开始数剩下的是第s个；总人数增到n个人(增加
*                                 1个人到最后)：提前14个位置开始数,增加的那个人第一个循环就退出了,剩下的还是第s个人；即从第
*                                 -14个人（因为是一圈，不包含0）开始数，剩下的是第s个人，那么从第一个人开始数，剩下的是第s+14
*                                 个人；以此类推。
*/

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2