Java Love
约瑟夫环问题求解

        用数组实现约瑟夫出圈问题，n个人排成一圈，从第一个开始报数，报到m的人出圈，
剩下的人继续开始从1报数，直到所有的人都出圈为止。对于给定的n，m，
求出所有的人出圈顺序。

class OutOfCircle {
     public OutOfCircle(int nn, int mm) {
          n = nn;
          m = mm;
          man = new int[n];                    //使用man数组表示N个人，man[i]为1表示i还在圈中，为0则表示i已经不在圈中
          count = new int[n];                  //保存出圈顺序
          java.util.Arrays.fill(man, 1);     //初始化man，一开始所有人都在圈中，所以都为1
     }

     public int[] out() {
          int c = 0;                      //当前人报的数
          int j = 0;
          while (total(man) != 0) {      //当圈中没人时，man中元素之和为0
               for (int i = 0; i < n; i++) {
                   c = c + man[i];                     //报数，出去的人为0，相当于没报
                    if (c != 0 && c % m == 0) {        //表示当前c!=0一定要加上，因为0对任何数取余都为0
                         man[i] = 0;                             //出圈，置为0
                         count[j++] = i + 1;                //保存出圈人的编号
                         c = 0;                                //重新开始报数  
                    }
               }
          }
          return count;
     }

     private int total(int[] t) {  //求INT数组的和
          //int sum = 0;
          for (int i : t) {
               //sum += i;
                    if(t[i]!=0) return 1;
              }
             return 0;
          //return sum;
     }

     private int n;    
     private int m;   
     private int[] man;
     private int[] count; 
}
posted on 2008-11-19 17:34 Bom Wu 阅读(2196) 评论(7)  编辑  收藏
Comments
  • # re: 约瑟夫环问题求解[未登录]
    littleq
    Posted @ 2008-11-20 12:30
    判断圈内是否有人，用total这个方法，好像有点多余吧，你既然用for循环了，那就
    if(t[i]!=0)return 1;
    这样还能少循环几次
      回复  更多评论   
  • # re: 约瑟夫环问题求解
    Bom Wu
    Posted @ 2008-11-20 14:42
    @littleq
    对对对，不用关心还有几个人，只要存在t[i]==1那就表示有人，不用全加起来了，多谢指教呀！  回复  更多评论   
  • # re: 约瑟夫环问题求解
    object
    Posted @ 2008-11-20 14:57
    import java.util.ArrayList;
    import java.util.List;


    /**
     *     @author huangjie
     * @createDate 2008-11-20
     * @package 
     * @fileName OutofCircle.java
     *    */
    public class Test{
            public static void main(String[] args){
            OutOfCirle ooc    =new OutOfCirle(1000,10000);
            ooc.begin();
        }
    }
    class OutOfCirle {
            //报出了这个数的都退出
        public static int outNumber;
            //总的有多少个人
        public static int manSize;
            //上面2个一开始就固定好了，所以我就声明成static
        
            //圈中的人
        private List<Man> allMan;
            //现在已经报到第几号了,初始化为1
        private int nowNumber=1;
            //现在已经报到第几个人了，初始化为0;
        private int nowMan=0;
        
            public OutOfCirle(int manSize,int outNumber){
            OutOfCirle.manSize    =manSize;
            OutOfCirle.outNumber    =outNumber;
            init();
        }
            private void init(){
            allMan    =new ArrayList();
                //初始化所有人，即把所有人编上号
            int manNumber=0;
                while(OutOfCirle.manSize!=manNumber){
                allMan.add(    new Man(++manNumber));
            }
        }
            public void begin(){
                while(allMan.size()>0){
                Man man     =this.select();
                    //把这个人T出去
                allMan.remove(man);
                    //当T的是最后一个的时候,又从第一个开始数
                if(nowMan==allMan.size()){
                    nowMan    =0;
                }
                    //说明T的不是最后一个
                    //T的人的后面的都会往前移一个位置
                    //这样就把原来的nowman代替了,就可以从nowman开始数了
                else{
                    
                }
                    //选出来了以后又从1开始报
                nowNumber=1;
                System.out.println(    "我是第"+man.getNumber()
                            +"号，我现在被T出去了,我是第"
                            +(manSize-allMan.size())+"个被T的"
                            +"，还有"+allMan.size()+"在圈里");
            }
            System.out.println(    "所有人都被T出去完了");
        }
            //找出报outNumber的人
        private Man select(){
            Man man    =null;
                //没选出来就一直报数
            while(man==null){
                    //nowman报数
                Man m=allMan.get(nowMan);
                    boolean right=m.reckon(nowNumber);
                    //就是他了
                if(right){
                    man    =m;
                }
                    //说明不是他
                else{
                        //报的数字到下一个
                    nowNumber++;
                        //人也到下一个去
                    nowMan++;
                        //说明已经到了最后一个了
                    if(nowMan==allMan.size()){
                            //又从第一个开始报数
                        nowMan=0;
                    }
                }
            }
                return man; 
        }

    }
    class Man{
            private int number;
            public Man(int number){
                this.number=number;
        }
            public int getNumber() {
                return number;
        }
            //报数：判断报出的数字是否和outNumber
        public boolean reckon(int num){
                return num==OutOfCirle.outNumber;
        }
    }
    你的方法太不面向对象了,看我写的
      回复  更多评论   
  • # re: 约瑟夫环问题求解
    object
    Posted @ 2008-11-20 14:59
    你的太不面向对象了,看我的   回复  更多评论   
  • # re: 约瑟夫环问题求解
    Bom Wu
    Posted @ 2008-11-20 15:08
    看来对面向对象的理解还真是不一样。多谢指教！  回复  更多评论   
  • # re: 约瑟夫环问题求解
    object
    Posted @ 2008-11-20 15:32
    其实每个人都有自己的一套理解方式,呵呵,对象这个东西,有的时候给别人讲解的时候根本就讲解不出来
      回复  更多评论   
  • # re: 约瑟夫环问题求解
    小七群
    Posted @ 2008-11-20 16:59
    要考虑到n<m的情况吗？  回复  更多评论   

只有注册用户登录后才能发表评论。
网站导航:
 
 
Powered by:
BlogJava
Copyright © Bom Wu