约瑟夫环
问题描述
约瑟夫环是一个非常经典的数学问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。开始报数，数到数字为k的那个人出列；继续，他的下一个人又从1开始报数，数到k的那个人又出列；依此规律重复下去，问最后出列的是谁？
背景故事 39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后下一个人重新从1报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想死，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
解法1
public static void main(String[] args) {
int n = 41;
int k = 2;
LinkedList<Integer> list = new LinkedList<>();
for (int i = 1; i <= n; i++) {
list.add(i);
}
System.out.println(list);
int i = 1; // 开始报数
while (list.size() > 1) { // 循环直到剩最后一人
if (i % k != 0) { // 如果报的不是k的倍数，存活，进入下一轮
list.addLast(list.removeFirst());
} else { // 是k的倍数，被杀
list.removeFirst();
System.out.println(list); // 最后一人为19
}
i++; // 报数加1
}
}
解法2
/*
* 对于总人数n，报数间隔k，f(i) 表示第i轮被杀的人
* 有如下公式：
* 注意人的编号从0开始
* f(1) = 0;
* f(i) = (f(i-1) + k) % i; (i>1)
*
* 如果人的编号从1开始，公式要变为
* f(1) = 1;
* f(i) = (f(i-1) + k - 1) % i + 1; (i>1)
*/
public static void main(String[] args) {
int n = 41;
int k = 2;
int f = 0;
for (int i = 2; i <= n; i++) {
f = (f + k) % i;
}
System.out.println(f+1); // 最后一人为19
}
注意 解法2 只适用于求最后一人
变体
100个人围成一圈，数到3和3的倍数时出圈，问剩下的人是谁？
解法略
自定义单向链表实现
class List {
static class Node {
public int value;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
public Node next;
@Override
public String toString() {
return "Node(" + value + ")->" + next;
}
}
Node first;
Node last;
public List(int n) {
last = new Node(n, null);
Node c = last;
for (int i = n - 1; i >= 1; i--) {
Node p = new Node(i, c);
c = p;
if (i == 1) {
first = p;
}
}
}
// 将第一个节点移动至最后一个
public void movef2l() {
Node t = first.next;
first.next = null;
last.next = first;
last = first;
first = t;
}
// 将第一个节点移除
public void removef() {
first = first.next;
}
}
public static void main(String[] args) {
int m = 41;
int k = 3;
List list = new List(m);
int i = 1;
while (list.first != list.last) {
if (i % k != 0) {
list.movef2l();
} else {
list.removef();
}
i++;
System.out.println(list.first);
}
}