约瑟夫环
问题来源
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
例如 10 个人，每报数到第3人自杀，求最后活下来的人。
所以最终活下的是第4位和第10位
Java代码(链表)：
import java.util.*;
public class YueSeFuHuan {
public static Integer[] live(int count, int k) {
// count 指人数, 每报数到第 k 人自杀
// livearr 存放最后活下来的人, 作为返回值。数组长度选取 k-1 和 count 较小的值即可
Integer livearr[] = new Integer[Math.min(count, k-1)];
// 如果 count 小于 k, 这 count 都可以存活
if(count < k) {
int index = 0;
while(index < count)
livearr[index++] = index;
return livearr;
}
// 使用链表，删除速度更快
LinkedList<Integer> people = new LinkedList<Integer>();
// 使用数组也可以(将上一行注释，下一行去注释即可)
// List<Integer> people = new ArrayList<Integer>();
// 初始化链表
for(int i = 0;i < count;i++)
people.add(i+1);
// point 指向链表元素, number 指报数
int point = 0, number = 0;
// 只留下 k-1 个人
while(people.size() >= k) {
number++;
// 如果 point 到了链表末尾, 再返回指向链表开头(因为是环)
if(point >= people.size())
point = 0;
// 如果报数到第 k 人，则从链表中删除(自杀)
// 如果是 number == 3 , 需要把 number = 0 (重置0)，此处取余可以避免重置0
if(number%k == 0)
people.remove(point);
// 继续指向链表下一元素
else
point++;
}
// 将 people 转化为数组返回
return people.toArray(livearr);
}
public static void main(String[] args) {
int count = 10, k = 3;
Integer [] livepeople = live(count, k);
for(int i = 0;i < livepeople.length;i++)
System.out.print(livepeople[i] + " ");
}
}
/*
* Code Running Results
* 4 10
*/
Java代码(数组)：
import java.util.*;
public class YueSeFuHuanTwo {
public static Integer[] live(int count, int k) {
// count 指人数, 每报数到第 k 人自杀
// livearr 存放最后活下来的人, 作为返回值。数组长度选取 k-1 和 count 较小的值即可
Integer livearr[] = new Integer[Math.min(count, k-1)];
// 如果 count 小于 k, 这 count 都可以存活
if(count < k) {
int index = 0;
while(index < count)
livearr[index++] = index;
return livearr;
}
// 使用数组
List<Integer> people = new ArrayList<Integer>();
// 初始化数组
for(int i = 0;i < count;i++)
people.add(i+1);
// point 指向数组元素, number 指报数
int point = 0, number = 0;
// count-k+1 表示需要自杀人数
for(int i = 1;i <= count-k+1;) {
// 如果 point 到了数组末尾, 再返回指向数组开头(因为是环)
if(point >= people.size())
point = 0;
// 如果此人已自杀, 继续指向数组下一元素
if(people.get(point) < 0)
point++;
else { // 否则此人活着
number++;
// 如果报数到第 k 人，则从数组中设置为 -1 (代表自杀)
if(number%k == 0) {
// 用 -1 来标记自杀的人
people.set(point, -1);
i++; // 自杀人数加一
// 否则继续指向数组下一元素
} else
point++;
}
}
int index = 0;
for(int i = 0;i < people.size();i++)
// 存活的放在数组
if(people.get(i) > 0)
livearr[index++] = people.get(i);
return livearr;
}
public static void main(String[] args) {
int count = 10, k = 3;
Integer [] livepeople = live(count, k);
for(int i = 0;i < livepeople.length;i++)
System.out.print(livepeople[i] + " ");
}
}
/*
* Code Running Results
* 4 10
*/
Java代码(队列)：
import java.util.*;
public class YueSeFuHuanThree {
public static Integer[] live(int count, int k) {
// count 指人数, 每报数到第 k 人自杀
// livearr 存放最后活下来的人, 作为返回值。数组长度选取 k-1 和 count 较小的值即可
Integer livearr[] = new Integer[Math.min(count, k-1)];
// 如果 count 小于 k, 这 count 都可以存活
if(count < k) {
int index = 0;
while(index < count)
livearr[index++] = index;
return livearr;
}
// 使用队列
Queue<Integer> people = new LinkedList<Integer>();
// 初始化队列
for(int i = 0;i < count;i++)
people.add(i+1);
// number 指报数
int number = 0;
// 只留下 k-1 个人
while(people.size() >= k) {
number++;
Integer item = people.remove(); // 出队
// 如果此人不需要自杀, 再入队
if(number%k != 0)
people.add(item);
}
int index = 0;
while(!people.isEmpty()) {
livearr[index++] = people.remove();
}
return livearr;
}
public static void main(String[] args) {
int count = 10, k = 3;
Integer [] livepeople = live(count, k);
for(int i = 0;i < livepeople.length;i++)
System.out.print(livepeople[i] + " ");
}
}
/*
* Code Running Results
* 4 10
*/
另一种问题，只剩下一个人。
上面我们讲的是每到第K个删除，如果count大于等于k的话，最终会留下k-1个。现在无论多少个，最后只留下1个，就是说如果数量小于k个的时候我们继续循环删除，直到留下最后一个的为止。
例如 n 个人，每报到 k 的人自杀(这里从 0 开始)
Java代码(递归)：
public class YueSeFuHuanFour {
public static int live(int n, int k) {
// 由于从 0 开始，所以结果加一
return fun(n, k) + 1;
}
public static int fun(int n, int k) {
// 只有一个人时返回 0
if (n == 1)
return 0;
return (fun(n - 1, k) + k) % n;
}
public static void main(String[] args) {
System.out.println(live(10, 3));
}
}
/* Code Running Results:
* 4
*/
Java代码(循环)
public class YueSeFuHuanFive {
public static int live(int n, int k) {
// 只有一个人时返回 0
int result = 0;
// 从又二个人开始执行循环
for(int i = 2;i <= n;i++)
result = (result+k) % i;
// 由于从 0 开始，所以结果加一
return result+1;
}
public static void main(String[] args) {
System.out.println(live(10, 3));
}
}
/* Code Running Results:
* 4
*/
欢迎评论