/**
 * 	约瑟夫问题:设编号为1，2，。。。n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，
 * 	他的下一位又从1开始报数，数到m的人又出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列。求最
 *      后剩下人的编号。
 * 
 * 	很容易想到循环链表，我这里用的双向循环链表解法。
 */
package com.yosephu;
public class Yosephu 
{
	public static void main(String[] args) 
	{
		//测试用例
		Link link = new Link();
		link.setLen(10);
		link.setK(1);
		link.setM(10);
		link.init();
		link.show();
		link.play();
	}

}
//节点类
class Node
{
	int num;
	Node pre;
	Node next;

	public Node(int num)
	{
		this.num = num;
	}
}
//链表类
class Link
{
	Node h = null;
	Node temp = null;
	//链表大小
	int len = 0;
	public void setLen(int len)
	{
		this.len = len;
	}
	int k = 0;
	int m = 0;
	public void setK(int k) {
		this.k = k;
	}
	public void setM(int m) {
		this.m = m;
	}
	//初始化链表
	public void init()
	{
		for(int i=1;i<=len;i++)
		{
			Node node = new Node(i);
			if(i == 1)
			{
				h = node;
				temp = node;
			}
			else
			{
				if(i == len)
				{
					node.pre = temp;
					temp.next = node;
					node.next = h;
					h.pre = node;
				}
				else
				{
					node.pre = temp;
					temp.next = node;
					temp = node;
				}
			}
		}
	}
	public void play()
	{
		Node temp = this.h;
		//1。先找到开始数数的第k个人
		for(int i=1;i<k;i++)
		{
			temp = temp.next;
		}
		while(this.len !=1)
		{
			//2。数m下
			for(int j=1;j<m;j++)
			{
				temp = temp.next;
			}

			//打出出列人的编号
			System.out.println("出列人的编号:"+temp.num);

			//3。将数到m的人，踢出链表
			temp.pre.next = temp.next;
			temp.next.pre = temp.pre;
			temp = temp.next;
			this.len--;
		}
		System.out.println("最后一个是:"+temp.num);
	}

	public void show()
	{
		Node t = this.h;
		do
		{
			System.out.println(t.num);
			t = t.next;
		}
		while(t != this.h);
	}

}