约瑟夫环问题：

约瑟夫问题，是一个计算机科学和数学中的问题，在计算机编程的算法中，类似问题又称为约瑟夫环，又称“丢手绢问题”。

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

这里我们换成孩子出环形队列的问题，杀人有点血腥.....

用Java链表实现

1.创建一个孩子的节点类：

class BoyNode{
	private int number;
	private BoyNode next;
	public BoyNode(int no) {
		this.number=no;
	}
	public int getNumber() {
		return number;
	}
	public void setNumber(int number) {
		this.number = number;
	}
	public BoyNode getNext() {
		return next;
	}
	public void setNext(BoyNode next) {
		this.next = next;
	}
}

 这里的变量都是private私有型变量，所以使用set和get方法来调用和获取。

2.通过添加节点的方法来创建一个环形列表

public void addBoy(int num) {
		if(num<2) {
			System.out.println("num数字不符合要求");
			return;
		}
		//使用循环创建环形链表
		//创建一个辅助节点
		BoyNode curboy=null;//默认辅助节点为空
		for(int i=1;i<=num;i++) {
			BoyNode boy = new BoyNode(i);
			if(i==1) {
				first=boy; 
				first.setNext(first);
				curboy=first;
			}
			curboy.setNext(boy);
			boy.setNext(first);
			curboy=boy;
		}
	}
	

 3.遍历环形列表，检查是否有误

public void showList() {
		if(first==null) {
			System.out.println("当前循环链表为空");
			return;
		}
		BoyNode curboy=first;
		while(true) {
			System.out.printf("小孩的编号分别为%d\n",curboy.getNumber());
			if(curboy.getNext()==first) {
				break;
			}
			curboy=curboy.getNext();//curboy辅助变量向后移动。
		}
	}
	

4.约瑟夫环问题出列表

/**
	 * @param startnum  开始报数的位置
	 * @param count    数count个出环形链表
	 * @param num      总高有多少人
	 */
	public void countBoy(int startnum,int count,int num) {
		//先对数据进行校验
		if(first==null||startnum<1||startnum>num) {
			System.out.println("输入的数据不符合约定，请重新输入");
			return;
		}
		//创建辅助节点指向需要出链表的节点的前一个节点
		BoyNode helper=first;
		while(helper.getNext()!=first) {
			helper=helper.getNext();
		}
		
		//需要从哪一个孩子开始报数  就移动startnum-1次
		//此时first指向需要开始报数的孩子。
		for(int j=0;j<startnum-1;j++) {
			first=first.getNext();
			helper=helper.getNext();
		}
		while(helper!=first) {
			for(int j=1;j<count;j++) {
				first=first.getNext();
				helper=helper.getNext();
			}
			System.out.printf("%d号小孩出链表\n",first.getNumber());
			first=first.getNext();
			helper.setNext(first);
		}
		System.out.printf("最后一位孩子为%d号\n", first.getNumber());
		
	}
}

5.最后代码预览：

package Josephu;

public class Josephu {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		//测试代码
		CircleSingleLinkList list1=new CircleSingleLinkList();
		list1.addBoy(5);
		list1.showList();
		list1.countBoy(1, 2, 5);
	}

}
class CircleSingleLinkList{
	private BoyNode first = new BoyNode(-1);
	//添加孩子节点（其他节点）
	public void addBoy(int num) {
		if(num<2) {
			System.out.println("num数字不符合要求");
			return;
		}
		//使用循环创建环形链表
		//创建一个辅助节点
		BoyNode curboy=null;//默认辅助节点为空
		for(int i=1;i<=num;i++) {
			BoyNode boy = new BoyNode(i);
			if(i==1) {
				first=boy; 
				first.setNext(first);
				curboy=first;
			}
			curboy.setNext(boy);
			boy.setNext(first);
			curboy=boy;
		}
	}
	
	//遍历循环链表
	public void showList() {
		if(first==null) {
			System.out.println("当前循环链表为空");
			return;
		}
		BoyNode curboy=first;
		while(true) {
			System.out.printf("小孩的编号分别为%d\n",curboy.getNumber());
			if(curboy.getNext()==first) {
				break;
			}
			curboy=curboy.getNext();//curboy辅助变量向后移动。
		}
	}
	
	//按规则依次推出循环链表的顺序
	
	/**
	 * @param startnum  开始报数的位置
	 * @param count    数count个出环形链表
	 * @param num      总高有多少人
	 */
	public void countBoy(int startnum,int count,int num) {
		//先对数据进行校验
		if(first==null||startnum<1||startnum>num) {
			System.out.println("输入的数据不符合约定，请重新输入");
			return;
		}
		//创建辅助节点指向需要出链表的节点的前一个节点
		BoyNode helper=first;
		while(helper.getNext()!=first) {
			helper=helper.getNext();
		}
		
		//需要从哪一个孩子开始报数  就移动startnum-1次
		//此时first指向需要开始报数的孩子。
		for(int j=0;j<startnum-1;j++) {
			first=first.getNext();
			helper=helper.getNext();
		}
		while(helper!=first) {
			for(int j=1;j<count;j++) {
				first=first.getNext();
				helper=helper.getNext();
			}
			System.out.printf("%d号小孩出链表\n",first.getNumber());
			first=first.getNext();
			helper.setNext(first);
		}
		System.out.printf("最后一位孩子为%d号\n", first.getNumber());
		
	}
}

//创建一个节点类
class BoyNode{
	private int number;
	private BoyNode next;
	public BoyNode(int no) {
		this.number=no;
	}
	public int getNumber() {
		return number;
	}
	public void setNumber(int number) {
		this.number = number;
	}
	public BoyNode getNext() {
		return next;
	}
	public void setNext(BoyNode next) {
		this.next = next;
	}
}

 写在最后：小兰学编程（一个学编程的一年级新生）

更多内容请关注微信公众号：小兰小栈

欢迎各位大神指点一二！！！