josephus.java

来自「用循环链表求解约瑟夫(josephus)问题 求解约瑟夫(josephus)问」· Java 代码 · 共 43 行

/*用循环链表求解约瑟夫(josephus)问题
例，n=8, m=3（报数）从1号开始报数出列顺序为：3, 6, 1, 5, 2,
       8, 4。最后一个编号7的旅客将赢得环球旅游。*/
import java.io.*;
public class Josephus{
	public LinkedList list;
	
	public void initial(int n){//初始化N个节点的循环链表
		list=new LinkedList();
		ListNode itr=list.header;
		for(int i=1;i<=n;i++){
		itr.next=new ListNode(i);
		itr=itr.next;
    	}
    	itr.next=list.header.next;
	}
	public int joseph(int m){//
		ListNode itr=list.header;
		while(!itr.next.equals(itr)){
			for(int i=1;i<m;i++)
			itr=itr.next;//跳过M个节点
			System.out.println(((Integer)itr.next.element).intValue());
			itr.next=itr.next.next;//打印并删除
		}
		return 	((Integer)itr.element).intValue();//返回最后一个节点的值
	}	
	public static void main(String args[]){
		Josephus jose=new Josephus();
		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.initial(n);
		System.out.println("第"+jose.joseph(m)+"个将赢得环球旅行.");
	}
}