java实现约瑟夫问题

Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

public class Josephu {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		CircleSingleLinkedList circleSingleLinkedList =new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);	//加入5个节点
		circleSingleLinkedList.countBoy(1, 2, 5);
	}

}
//创建节点
class Boy{
	private int no;		//编号
	private Boy next;	//指向下一个节点
	public Boy(int no) {
		this.no =no;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public Boy getNext() {
		return next;
	}
	public void setNext(Boy next) {
		this.next = next;
	}
}
class CircleSingleLinkedList{
	//创建一个first节点，当前没有编号
	private Boy first =new Boy(-1);
	//添加节点，形成环形链表
	public void addBoy(int nums) {
		if(nums<1) {
			System.out.println("nums值不正确");
			return;
		}
		Boy curBoy = null;//辅助指针
		for(int i = 1;i<=nums;i++) {
			Boy boy =new Boy(i);
			if(i==1) {
				first =boy;
				first.setNext(first);//形成环
				curBoy =first;	//让curBoy指向第一个小孩
			}else {
				curBoy .setNext(boy);
				boy.setNext(first);
				curBoy = boy ;
			}
		}
	}
	//遍历链表
	public void showBoy() {
		if(first ==null) {
			System.out.println("链表为空");
			return;
		}
		Boy curBoy =first;
		while(true) {
			System.out.printf("节点编号为%d\n",curBoy.getNo());
			if(curBoy.getNext()==first) {	//遍历完毕
				break;
			}
			curBoy =curBoy.getNext();//curBoy后移
		}
	}
	public void countBoy(int startNo,int countNum, int nums) {
		if(first ==null||startNo<1||startNo>nums) {
			return;
		}
		//创建辅助指针helper
		Boy helper =first;	
		while(true) {		//需要将helper指向最后一个节点
			if(helper.getNext()==first) {
				break;
			}
			helper =helper.getNext();
		}
		//报数前先让first和helper移动k-1次
		for(int j= 0;j<startNo-1;j++) {
			first =first.getNext();
			helper =helper.getNext();
		}
		//报数时first和helper同时移动m-1次，然后出圈
		while(true) {
			if(helper == first ) {	//说明圈中只有一个节点
				break;
			}
			//让first和helper移动m-1次
			for(int j =0;j<countNum-1;j++) {
				first =first.getNext();
				helper =helper.getNext();
			}
			System.out.printf("节点%d出圈\n",first.getNo());
			first =first.getNext();
			helper.setNext(first);
		}
		System.out.println("最后节点编号"+first.getNo());
	}
}