package demo11;
/**
      * 約瑟夫問(wèn)題， 化為丟手絹
      * 
      * @author tianq 思路：建立一個(gè)Child類 一個(gè)循環(huán)列表類CyclLink
      */
public class demo11 {
	public static void main(String[] args) {
		CyclLink cyclink = new CyclLink();
		cyclink.setLen(15);
		cyclink.createLink();
		cyclink.setK(2);
		cyclink.setM(2);
		cyclink.show();
		cyclink.play();
	}
}
// 先建立一個(gè)孩子類
class Child {
	// 孩子的標(biāo)識(shí)
	int no;
	Child nextChild;
	// 指向下一個(gè)孩子
	public Child(int no) {
		// 構(gòu)造函數(shù)給孩子一個(gè)id
		this.no = no;
	}
}
class CyclLink {
	// 先定義一個(gè)指向鏈表第一個(gè)小孩的引用
	// 指向第一個(gè)小孩的引用，不能動(dòng)
	Child firstChild = null;
	Child temp = null;
	int len = 0;
	// 表示共有幾個(gè)小孩
	int k = 0;
	//開(kāi)始的孩子
	int m = 0;
	//數(shù)到幾推出
	// 設(shè)置m
	public void setM(int m) {
		this.m = m;
	}
	// 設(shè)置鏈表的大小
	public void setLen(int len)
	  {
		this.len = len;
	}
	// 設(shè)置從第幾個(gè)人開(kāi)始數(shù)數(shù)
	public void setK(int k) {
		this.k = k;
	}
	// 開(kāi)始play
	public void play() {
		Child temp = this.firstChild;
		// 1.先找到開(kāi)始數(shù)數(shù)的人
		for (int i = 1; i < k; i++) {
			temp = temp.nextChild;
		}
		while (this.len != 1) {
			// 2.數(shù)m下
			for (int j = 1; j < m; j++) {
				temp = temp.nextChild;
			}
			// 找到要出圈的前一個(gè)小孩
			Child temp2 = temp;
			while (temp2.nextChild != temp) {
				temp2 = temp2.nextChild;
			}
			// 3.將數(shù)到m的小孩，退出
			temp2.nextChild = temp.nextChild;
			// 讓temp指向下一個(gè)數(shù)數(shù)的小孩
			temp = temp.nextChild;
			// this.show();
			this.len--;
		}
		// 最后一個(gè)小孩
		System.out.println("最后出圈" + temp.no);
	}
	// 初始化環(huán)形鏈表
	public void createLink() {
		for (int i = 1; i <= len; i++) {
			if (i == 1) {
				// 創(chuàng)建第一個(gè)小孩
				Child ch = new Child(i);
				this.firstChild = ch;
				this.temp = ch;
			} else {
				if (i == len) {
					// 創(chuàng)建第一個(gè)小孩
					Child ch = new Child(i);
					temp.nextChild = ch;
					temp = ch;
					temp.nextChild = this.firstChild;
				} else {
					// 繼續(xù)創(chuàng)建小孩
					Child ch = new Child(i);
					temp.nextChild = ch;
					temp = ch;
				}
			}
		}
	}
	// 打印該環(huán)形鏈表
	public void show() {
		Child temp = this.firstChild;
		do {
			System.out.print(temp.no + " ");
			temp = temp.nextChild;
		}
		while (temp != this.firstChild);
	}
}