josephus2.java

用循环链表求解约瑟夫(josephus)问题 求解约瑟夫(josephus)问题,用数组实现

/*求解约瑟夫(josephus)问题,用数组实现*/
import java.io.*;
public class Josephus2{
	static CursorNode[] cursorSpace;
	public void josephus(int n,int m){
		cursorSpace=new CursorNode[n];
		for(int i=0;i<n;i++)
		cursorSpace[i]=new CursorNode(i+1,i+1);
		cursorSpace[n-1].next=0;//初始化N个节点的伪循环链表	
		int p=n-1;
		for(int i=0;i<n;i++){
			for(int j=1;j<m;j++)
			p=cursorSpace[p].next;//跳过M个节点
			System.out.println(cursorSpace[cursorSpace[p].next].element);
			cursorSpace[p].next=cursorSpace[cursorSpace[p].next].next;
			//删除并打印
		}
		System.out.println("第"+cursorSpace[p].element+"个将赢得环球旅行.");
		
	}
	public static void main(String args[]){
		Josephus2 jose=new Josephus2();
		int m=0,n=0;
		try{
			BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
			System.out.println("输入总人数：");
			n=Integer.parseInt(in.readLine());
			System.out.println("输入间隔");
			m=Integer.parseInt(in.readLine());
		}
		catch(IOException e){
		System.out.println(e);
     	}
		jose.josephus(n,m);
	}
}