用数组实现约瑟夫出圈问题,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 阅读(2197) 评论(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的情况吗?  回复  更多评论   

只有注册用户登录后才能发表评论。


网站导航: