Javaジョセフ環問題の2つの解法（循環配列、一方向リングチェーン）

1.問題
Josephuの問題は、番号を1、2、・・nとするn個人が一回り囲んで、約束番号をk（1）（=k（=n）とする人が1から数え、mまで数える人が出てきます。その次は1から数えて、mまで数える人がまた出て、順番に類推して、全員が列に出るまで、チーム番号を出す順番ができます。
2.解決方法一：循環配列
ヒント：毎回の新聞数は、ループの条件を満たすと、配列要素を-1に設定し、次の報数で-1をスキップします。配列の最後の要素が−1になるまで、ループが終了し、配列の循環はダイ取を用いて行われる。解決

//     :  +  
public static void JosephuByArr(int total,int startNum,int m){
	int []Arr=new int[total];
	int leave=total;                           //     
	int count=0;                               //  （0-1-2-3-4-5····）
	int index=startNum;                        //     
	//     （      ，            0 ,         ）
	Arr[0]=total;
	for(int i=1;i0){
		count++;                               //  
		//     count     
		if(Arr[index%total]==-1){
			while(Arr[index%total]==-1){
				index++;
			}
		}
		//      ，  （     -1）
		if(count%m==0){
			System.out.print(Arr[index%total]+"\t");
			Arr[index%total]=-1;
			leave--;
		}
		//       
		index++;
	}
}

3.解決方法2：一方向リングチェーン表
ヒント：まずn個の結点がある単循環チェーンを構成し、その後k結点から1から数え始め、mまで計算すると、対応する結点はチェーンから削除され、その後、削除された結点の次の結点からまた1から数え始め、最後の結点がチェーンから削除されるまでアルゴリズムは終了します。一方向リングチェーンの構築：

class CNode{
	private int val;
	private CNode next;
	public CNode(int val) {
		super();
		this.val = val;
	}
	
	public CNode() {
		super();
	}

	public int getVal() {
		return val;
	}
	public void setVal(int val) {
		this.val = val;
	}
	public CNode getNext() {
		return next;
	}
	public void setNext(CNode next) {
		this.next = next;
	}

	@Override
	public String toString() {
		return val+"\t";
	}
	
}

//          
class CircularList{
	private CNode first=null;       //       
	private int length;             //      
	
	//      
	public void create(int num){
		if (num<1) {
			System.out.println("num    ");
			return;
		}
		CNode pre=null;                   //         
		for(int i=1;i<=num;i++){
			CNode tmp=new CNode(i);
			if(i==1){
				first=tmp;
				first.setNext(first);
				pre=tmp;
				length++;
			}
			else{
				pre.setNext(tmp);
				tmp.setNext(first);
				pre=tmp;
				length++;
			}
		}
	}

	//      
	public void list(){
		if(first==null){
			System.out.println("    ");
			return;
		}
		CNode tmp=first;
		while(true){
			if(tmp.getNext()==first){
				System.out.print(tmp);
				break;
			}
			System.out.print(tmp);
			tmp=tmp.getNext();
		}
	}
	
	//        
	public CNode getCNodebyIndex(int index){
		index=index%length;
		if(index==0){
			index=length;
		}
		CNode cur=first;
		for(int i=1;i

解決:

//     ：        
public static void JosephuByCL(int total,int startNum,int m){
	//        
	CircularList CL=new CircularList();
	CL.create(total);
	
	//count     ,  m         ，         ，  
	CNode tmp=CL.getCNodebyIndex(startNum);  //   startNode
	int count=0;
	while(CL.getLength()>0){
		count++;
		if(count%m==0){
			System.out.print(tmp);
			CL.del(tmp);
		}
		tmp=tmp.getNext();
	}
}