现在的位置: 首页 > 综合 > 正文

2013华为校园招聘上机题——约瑟夫环

2013年02月05日 ⁄ 综合 ⁄ 共 1405字 ⁄ 字号 评论关闭
输入一个由随机数组成的数列(数列中每个数均是大于0的整数,长度已知),和初始计数值m。从数列首位置
开始计数,计数到m后,将数列该位置数值替换计数值m,并将数列该位置数值出列,然后从下一位置从新开始
计数,直到数列所有数值出列为止。如果计数到达数列尾段,则返回数列首位置继续计数。
请编程实现上述计数过程,同时输出数值出列的顺序。
 
这道题不难,但发现很多人给出的答案中的数列不是随机生成的,现在加上随机生成的数列的约瑟夫环的实现过程。
packagehuawei;
 
importjava.util.LinkedList;
importjava.util.Random;
 
publicclassTest6_1 {
    privatestaticintscanPeople(String s) {
               //用链表来实现“约瑟夫环”是一种很好的方式,可以方便的动态插入、删除、移动等。
        LinkedList<Integer> plist=newLinkedList<Integer>();
        try{
            intn=Integer.parseInt(s);               
            intstart=1;
            intend=20;
            Random rand=newRandom();
            for(inti=0;i<n;i++){
                 //由于题目要求“数列中每个数均是大于0的整数”,而系统提供的Random是从0开始的,
//故自己写一个任意的范围可控的函数showRandom,如下:
                intj=showRandom(start,end,rand);
                plist.add(j);
                System.out.print(j+" ");               
            }
            System.out.println("***");
            intcirclecount=0;
            while(plist.size()>1){
                for(inti=0;i<plist.size();i++){
                    circlecount++;
                                        //这里的m=3,且m是可以随意设置的
                    if(circlecount==3){
                        plist.remove(i);
                                   //删除了一个元素,后面的元素会整体前移一个单位,故减一
                        i--;
                        circlecount=0;
                    }
                }
            }             
            returnplist.get(0);
        }catch(NumberFormatException e){
            return0;
        }         
    }
     
    privatestaticintshowRandom(intstart,intend,Random rand){
        if(start>end){
            thrownewIllegalArgumentException("start cannot exceed end");
        }
        longrange=(long)(end-start+1);
        longfraction=(long)(range*rand.nextDouble());
        intsum=(int)(start+fraction);
        returnsum;
    }
     
    publicstaticvoidmain(String[] args){
        System.out.println(scanPeople("12"));
        System.out.println(scanPeople("11a"));
         
    }
 
}

抱歉!评论已关闭.