A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 下一秒温存 中级黑马   /  2014-11-11 10:43  /  1606 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

有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);
                    }
                   }
     }
}

2 个回复

倒序浏览
!!!!!!就是一约瑟夫环啊
回复 使用道具 举报
话说,入学考试碰到了相似的题

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