Java一方向ループチェーンテーブルでジョセフ問題を解決する

@lyc1234
Java一方向ループチェーンテーブルによるジョセフ問題の解決
ヨセフ問題:n人が円卓の周りに座って、まずある人から1報数、mまで数えた人が列を出て(つまり席を離れて、後の報数に参加しない)、それから列を出た次の人から再び1報数、mまで数えた人が列を出て、このようにしてすべての人が列を出るまで行って、それらの列の順番を求めてみます.
例えば、n=8,m=4のとき、1番目の人(1人あたりの番号が1,2,...,nの順)から報数を開始すると、得られる列の順序は、4,8,5,2,1,3,7,6である.このアルゴリズムでは,n,m,s(s番目の個人から1回目のカウント)を値パラメータとする必要がある.
構想

javaで一方向ループチェーンテーブル

を先に構築する

javaポインタクラス、チェーンテーブルクラス

挿入アルゴリズム

を記述する

は、同じ回数のポインタを後方に移動するたびに、指定された位置のidを出力し、その位置を削除して次の移動を継続する列アルゴリズムを記述する.

コード実装
1.ポインタクラス

/*
     link  next     link，           ，       
*/
public class Link {
      public int iData; //id
      public double dData; //  
      public double item;//     （        ，         ）
      public Link next;/*        ,         ，
                。         null ，               */
      public Link(int id,double dd)//      {
      {
    	  iData=id;
          dData=dd;
      }
	public void displayLink() {
    	  System.out.println("{"+iData+","+dData+"}");
      }
}

2.一方向循環チェーンテーブル類

/*       ，   ，                 
*/
public class LinkList2 {
	private Link first;//   
	private Link tail;//   
	Link temp1=null;//                  ，       
	public int count=0;//       
    public double item;//     
    LinkList2(){//     
    	first=tail=null;
    	count=0;//    ，        
     }
	public void InsertList(Link k) {//       
		if (count==0) {//     ，        。
			tail=first=k;
			
		}
		else {
			tail.next=k;//        k
			k.next=first;// k       
			tail=k;//          k
	  }
		count++;//     ++
     }
	public int exitList(Link current,int i) {//    ，  i current i     
		int k=1;//     current      id，      k  1  。
		while(k<i) {
				current=current.next;//  i-1      ，          id
				k++;
		  }
		int temp=current.next.iData;
		if(count!=1){//      ，        
	      current.next=current.next.next;//      next         
	      current=current.next;//    
		}
		else {
			current=first=tail=null;//     ，             
		}
		  count--;//    
		  temp1=current;//         ，            
		  return temp;//     
	  }
	public void displaylist() {//    ，                
  		  System.out.println("first --> last");
  		  Link current=first;//  current        
  		  while(current!=tail) {
  			  current.displayLink();//      
  			  current=current.next;//            
  		  }
  		  current.displayLink();
  		  System.out.println("");
  	  }
	public boolean isEmpty() {//        
		return(count==0);
	}
    public void josephus(int n,int m, int s) {//     
    	for(int i=1;i<=n;i++) {
    		this.InsertList(new Link(i,0.0));//     
    	}//     1……n，   1  ，             
    	Link current=first;//          
    	for(int i=0;i<s-1;i++) {//    s    ，   s-1            
    		current=current.next;
    	}
    	while(!this.isEmpty()) {//     ，   
    		int i;//    
    		i=this.exitList(current, m-1);//      ，          ，      m-1   
    		current=temp1;
    		System.out.println(i);
    	}
    }
}

3.メインプログラムクラス

public static  void main(String[] args) {
	 
	 LinkList2 l2=new LinkList2();
	 l2.josephus(8, 4, 1);
}

実はなぜm-1回使うのか、私にもわかりませんでしたが・・・