约瑟夫（Josephu）问题

介绍

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

方法

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

创建Boy(小孩)对象，每一个对象就是一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
	}

	@Override
	public String toString() {
		return "Boy [no=" + no + "]";
	}
}

构建单向环形链表思路以及代码实现

  1. 先创建第一个节点, 让 first 一直指向该节点
  2. 再创建一个辅助指针(变量) curBoy，指向first节点
  3. 每创建一个新节点，就让curBoy的next指向新节点，新节点的next指向first，curBoy再指向新节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class CircleSingleLinkedList {
	private Boy first = null;

	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);
			// 当i=1时。另外处理
			if (i == 1) {
				first = boy;
				first.setNext(first);
				curBoy = boy;
			} else {
				curBoy.setNext(boy);
				boy.setNext(first);
				curBoy = boy;
			}
		}
	}
}

遍历环形链表的思路以及代码实现

  1. 先让一个辅助指针(变量) curBoy，指向first节点

  2. 然后通过一个while循环遍历该环形链表，直到curBoy.next == first时结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class CircleSingleLinkedList {
	private Boy first = null;

	public void showBoy() {
		// 判断链表是否为空
		if (first == null) {
			System.out.println("链表为空，没有小孩。");
			return;
		}
		Boy curBoy = first;
		while (true) {
			System.out.println("当前小孩编号为：" + curBoy.getNo());
			if (curBoy.getNext() == first) {
				break;
			}
			curBoy = curBoy.getNext();
		}
	}
}

小孩出圈的思路以及代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 
 * @param startNo  从第几个小孩开始报数
 * @param countNum 数多少下
 * @param nums     环形链表的总人数
 */
public void countBoy(int startNo, int countNum, int nums) {
	if (startNo > nums || startNo < 1 || first == null || countNum < 1) {
		System.out.println("参数错误，请重新输入！");
		return;
	}
	Boy helper = first;
       // 使helper指向链表最后一个节点，紧跟在first后面
	while (true) {
		if (helper.getNext() == first) {
			break;
		}
		helper = helper.getNext();
	}
       // 使first指向开始喊数的节点
	for (int i = 1; i < startNo; i++) {
		first = first.getNext();
		helper = helper.getNext();
	}
	while (true) {
           // 只剩最后一个节点
		if (helper == first) {
			System.out.printf("最后一个编号为%d的小孩出圈。\n", first.getNo());
			return;
		}
           // 开始喊数，first指向喊数者
		for (int i = 1; i < countNum; i++) {
			first = first.getNext();
			helper = helper.getNext();
		}
		System.out.printf("编号为%d的小孩出圈。\n", first.getNo());
		helper.setNext(first.getNext());
		first = first.getNext();
	}
}