Josephus问题：假设有n个人排成一个圈，从第一个人开始报数，数到第m个人的时候这个人从圈里出列，然后继续在环里数到第m个人，让其出列，直到所有人都出列，求最后圈里剩下的那个人，在以前n个人里是第几个？
其中，有许多类似的问题，都属于约瑟夫问题，如：
500个小孩围成一圈，从第一个开始报数：1，2，3，1，2，3，1，2，3……每次报3的小孩退出，然后再从1开始报数，问最后剩下的那个小孩，在以前500人里是第几个？
package test;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 约瑟夫问题 500个小孩围成一圈，从第一个开始报数：1，2，3，1,2,3,1,2,3,……每次报3的小孩退出，然后再从1开始报数，
* 问最后剩下的那个小孩，在以前500人里是第几个？
*
* 思路1：数组，可以通过ArrayList实现，将所有的小孩放到ArrayList里，然后判断小孩的位置是否是3，是的话，将其remove掉；
* 思路2：链表，可以通过LinkedList实现；
* 思路3：队列，可以通过LinkedList实现；
* 思路4：递归；
* 思路5：循环；
*/
public class Josephus {
/**
* 数组实现第一种方式
* @param num
* @param quitNum
* @return
*/
public static int baoshu2(int num, int quitNum) {
List<Integer> lists = new ArrayList<Integer>();
for (int i = 1; i <= num; i++) {
lists.add(i);
}
int index = 0;
while (lists.size() > 1) {
for (int i = 0; i < lists.size(); i++) {
index++;
if (index % quitNum == 0) {
index = 0;
lists.remove(i);
i--;
}
}
}
return lists.get(0);
}
/**
* 数组实现第二种方式
* @param num
* @param quitNum
* @return
*/
public static int baoshu(int num, int quitNum) {
// 用来放置n个小孩，list每个元素的值，存放小孩的初始位置
List<Integer> list = new ArrayList<Integer>();
// 初始化list
for (int i = 1; i <= num; i++) {
list.add(i);
}
// 小孩开始报数，数3的小孩出来,index代表小孩的当前位置
int index = 0;
while (list.size() > 1) {
// 当前位置加上报数就是报数后的位置
index = (index + quitNum - 1) % list.size();
// 移除当前小孩
// System.out.println(index + "--" + list.get(index));
list.remove(index);
}
return list.get(0);
}
/**
* 链表实现
* @param num
* @param quitNum
* @return
*/
public static int getCountOffResult(int num, int quitNum) {
// 入口参数检查
if (num <= 0 || quitNum <= 0) {
return 0;
}
// 定义并生成小孩数组列表，编号从1到numberOfChildren
List<Integer> children = new LinkedList<>();
for (int ii = 1; ii <= num; ii++) {
children.add(ii);
}
Iterator<Integer> childrenIterator = children.iterator();
while (num > 1) {
Integer childNo = 0;
for (int ii = 0; ii < quitNum; ii++) {
// 判断链表是否到了最后一个节点
if (!childrenIterator.hasNext()) {
childrenIterator = children.iterator();
}
childNo = childrenIterator.next();
}
childrenIterator.remove();
num--;
}
childrenIterator = children.iterator();
return childrenIterator.next();
}
/**
* 队列，使用LinkedList实现，因为LinkedList实现了Queue接口
*
* @param num 小孩总数
* @param quitNum 第几个小孩
* @return
*/
public static int queue(int num, int quitNum) {
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 1; i <= num; i++) {
q.add(i);
}
// 将数1、2的小伙伴放到队尾，将数3的小伙伴扔出去
while (q.size() > 1) {
for (int i=1;i < quitNum ;i++) {
q.add(q.remove());
}
q.remove();
}
// 打印出最后一个小伙伴的位置
Integer position = 0;
if ((position = q.poll()) != null) {
return position;
} else {
return 0;
}
}
/**
* 递归实现
*
* @param num 小孩总数
* @param quitNum 第几个小孩
* @param i 次数
* @return
*/
public static int fun(int num, int quitNum, int i) {
if (i == 1) {
return (num + quitNum - 1) % num;
} else {
return (fun(num - 1, quitNum, i - 1) + quitNum) % num;
}
}
/**
* 约瑟夫循环非递归解法
* 思路：采用倒推方式
*
* @param num 小孩总数
* @param quitNum 第几个小孩
* @return
*/
public static int getLastChild(int num, int quitNum) {
int index = 0;
for (int i = 2; i <= num; i++) {
index = (index + quitNum) % i;
}
return index + 1;
}
public static void main(String[] args) {
System.out.println(fun(400, 3, 400) + 1);
System.out.println(baoshu2(400, 3));
System.out.println(baoshu(400, 3));
System.out.println(queue(400, 3));
System.out.println(getCountOffResult(400, 3));
System.out.println(getLastChild(400, 3));
}
}
其中程序参考自：