Java解决约瑟夫问题代码实例

importjava.util.ArrayList;

/**
 *Java约瑟夫问题：n个人（不同id）围成一个圈，从startId(任意数)个开始报数m(任意数)个数，数m的人出列排成新队列，m清零，
 *然后又从下一个人开始数m个数开始，数到m就出列接在新队列尾部，如此重复，知道所有人都出列为止。
 *打印出列后的新队列
 *
 *eg
 *intn=10;//总人数
 *intm=3;  //报数个数
 *intstartIndex=1; //起点位置
 *@authorHulk  2014 0320
 *
 */
publicclassJosephListTest{
   publicstaticvoidmain(String[]args){
       longstartTime=System.currentTimeMillis();
       JosephListTesttest=newJosephListTest();
       intn=10;//总人数
       intm=3;//报数个数
       intstartIndex=12;//起点位置
       System.out.println("JosephListTest:n="+n+",m="+m+
           ",startIndex="+startIndex+"\n\nQUEUERESULT:");

       ArrayList<Person>queueList=test.queuePreson(n,m,startIndex);

       for(Personperson:queueList){
           System.out.println("OUTperson:"+person);
       }

       System.out.println("usetime="+
           (System.currentTimeMillis()-startTime));
   }

   privateArrayList<Person>queuePreson(intn,intm,intstartIndex){
       ArrayList<Person>queueList=null;
       PersonListlist=createList(n);

       //list.search();
       if((list!=null)&&(list.head!=null)){
           queueList=newArrayList<JosephListTest.Person>();

           PNodepNode=list.head;

           if(startIndex>0){
               startIndex=startIndex%n;
               pNode=list.getNode(startIndex);
           }else{
               pNode=list.head;
           }

           intcount=1;

           while(list.size>0){
               PersonoutPerson=null;

               //find
               if(count==(m-1)){
                   //deletenextnode
                   Personprev=pNode.person;
                   outPerson=list.remove(prev);
                   queueList.add(outPerson);
                   //System.out.println("OUTperson:"+outPerson+",size="+list.size);
                   count=0;
               }

               pNode=pNode.next;
               count++;
           }
       }

       returnqueueList;
   }

   privatePersonListcreateList(intn){
       PersonListlist=newPersonList();

       for(inti=0;i<n;i++){
           Personperson=newPerson(i,"name_"+(i+1));
           list.add(i,person);
       }

       returnlist;
   }

   publicclassPersonList{
       PNodehead=null;
       intsize=0;

       publicPersonList(){
       }

       publicPersonList(Personperson){
           head=newPNode(person,head);
           size++;
       }

       publicPersonList(PNodehead){
           this.head=head;
           head.setNext(head);
           size++;
       }

       publicPNodegetHead(){
           returnhead;
       }

       publicvoidsetHead(PNodehead){
           this.head=head;
       }

       publicintgetSize(){
           returnsize;
       }

       publicvoidsetSize(intsize){
           this.size=size;
       }

       publicvoidsize(intsize){
           this.size=size;
       }

       publicbooleanisEmpty(){
           returnthis.size<=0;
       }

       publicvoidinitHead(Personperson){
           if(size==0){
               head=newPNode(person,head);
           }else{
               PNodeno=head;
               head=newPNode(person,no);
           }

           size++;
       }

       publicvoidadd(intindex,Personperson){
           if(size==0){
               head=newPNode(person,head);
               head.setNext(head);

               //System.out.println("head:"+head);
           }else{
               if(index<0){
                   index=0;
               }

               if(index>size){
                   index=size;
               }

               PNodeno=head;

               for(inti=0;i<(index-1);i++){
                   no=no.next;
               }

               PNodenewNode=newPNode(person,no.next);
               no.next=newNode;
           }

           size++;
       }

       publicPersondelete(intindex){
           PNodepNode=remove(index);

           if((pNode!=null)&&(pNode.next!=null)){
               returnpNode.next.person;
           }

           returnnull;
       }

       publicPNoderemove(intindex){
           if(size==0){
               returnnull;
           }else{
               if((index<0)||(index>=size)){
                   returnnull;
               }
           }

           PNodeno=head;

           for(inti=0;i<(index-1);i++){
               no=no.next;
           }

           no.next=no.next.next;
           size--;

           if((no!=null)&&(no.next!=null)){
               returnno.next;
           }

           returnnull;
       }

       /**
       *removenextnodeofpersonnode,andreturnthedeletedperson
       *@paramprePerson
       *@return removedPerson
       */
       publicPersonremove(PersonprePerson){
           if(prePerson==null){
               returnnull;
           }

           if(size==0){
               returnnull;
           }

           PNodepreNode=head;
           intindex=-1;

           for(inti=0;i<size;i++){
               if(preNode.person.id==prePerson.id){
                   index=i;

                   break;
               }else{
                   preNode=preNode.next;
               }
           }

           PersonremPerson=null;

           if(size<=1){
               //onlyonenode,getitspersonandsetitasnull
               remPerson=preNode.person;
               preNode=null;
           }else{
               //preNode.next.personisdestone
               remPerson=preNode.next.person;
               preNode.next=preNode.next.next;
           }

           size--;

           //System.out.println("deleteingindex="+index+": "+remPerson+",size="+size);
           returnremPerson;
       }

       publicintupdate(Personsrc,Persondest){
           if(src==null){
               return-1;
           }

           intindex=-1;
           PNodeno=head;

           for(inti=0;i<size;i++){
               if(src.id==no.person.id){
                   no.person=dest;

                   break;
               }else{
                   no=no.next;
               }
           }

           returnindex;
       }

       publicbooleanset(intindex,Personperson){
           if(person==null){
               returnfalse;
           }

           if(size==0){
               returnfalse;
           }else{
               if((index<0)||(index>=size)){
                   returnfalse;
               }
           }

           PNodeno=head;

           for(inti=0;i<index;i++){
               no=no.next;
           }

           no.person=person;

           returntrue;
       }

       publicPersonget(intindex){
           PNodeno=getNode(index);

           if(no!=null){
               returnno.person;
           }

           returnnull;
       }

       publicPNodegetNode(intindex){
           if(size==0){
               returnnull;
           }else{
               if((index<0)||(index>=size)){
                   returnnull;
               }
           }

           PNodeno=head;

           for(inti=0;i<index;i++){
               no=no.next;
           }

           returnno;
       }

       publicvoidsearch(){
           intsizeLong=size;
           PNodeno=head;

           for(inti=0;i<sizeLong;i++){
               System.out.println("searchindex="+i+",  "+no);
               no=no.next;
           }
       }
   }

   publicclassPNode{
       Personperson;
       PNodenext=null;

       publicPNode(){
       }

       publicPNode(Personperson){
           this.person=person;
       }

       publicPNode(Personperson,PNodenext){
           this.person=person;
           this.next=next;
       }

       @Override
       publicStringtoString(){
           return"PNode[person="+person.id+",next="+next.person.id+
           "]";
       }

       publicPersongetPerson(){
           returnperson;
       }

       publicvoidsetPerson(Personperson){
           this.person=person;
       }

       publicPNodegetNext(){
           returnnext;
       }

       publicvoidsetNext(PNodenext){
           this.next=next;
       }
   }

   publicclassPerson{
       intid=0;
       Stringname="";

       publicPerson(){
       }

       publicPerson(intid,Stringname){
           super();
           this.id=id;
           this.name=name;
       }

       @Override
       publicStringtoString(){
           return"Person[id="+id+",name="+name+"]";
       }
   }
}