约瑟夫问题：
自定义链表实现
首先，我们看下什么是约瑟夫问题？
有 M 个人，其编号分别为 1－M。这 M 个人按顺序排成一个圈（如图）。现在给定一个
数 N，从第一个人开始依次报数，数到 N 的人出列，然后又从下一个人开始又从 1 开始依次
报数，数到 N 的人又出列．．．如此循环，直到最后一个人出列为止。输出每次出列的人的下标
【输入格式】
输入只有一行，包括 2 个整数 M，N。之间用一个空格分开(0 < n <= m <= 100)。
【输出格式】
输出只有一行，包括 M 个整数
【样列输入】
8 5
【样列输出】
5 2 8 7 1 4 6 3
我们稍加分析可以发现，这个问题非常适合用循环链表处理，每次遍历N个节点后，将节点删除，数据被删除节点的下标，同时继续向下遍历，因为我们是一个循环链表，再经过N个元素后，继续执行同样的操作就可以了，代码示例如下：
package com.study.spring.transaction.math; import lombok.AllArgsConstructor; import lombok.Data; /** * @author dmz * @date Create in 23:36 2019/8/6 */ public class Main { public static void main(String[] args) { CircleList circleList = new CircleList(); circleList.add(1); circleList.add(2); circleList.add(3); circleList.add(4); circleList.add(5); circleList.add(6); circleList.add(7); circleList.add(8); calculateIndex(circleList, 5); } public static void calculateIndex(CircleList circleList, int period) { while (circleList.getSize() > 0) { CircleList.Node node = circleList.get(period); int remove = circleList.remove(node); System.out.println(remove); } } } /** * 构建一个环 * 为了方便进行删除， * 我们使用双向循环链表 */ @Data class CircleList { // 环中数据的大小 private int size; // 环的第一个节点 private Node first; // 环的最后一个节点 private Node last; // 下次开始的节点,默认从第一个节点开始 private Node next; /** * 环中的每一个节点 * 可以看到，我在定义时，每个节点都持有下一个节点的引用 */ @Data @AllArgsConstructor public class Node { int index; Node next; Node pre; @Override public String toString() { return "current index is " + index; } } /** * 向环中从尾部添加数据 * * @param index 数据 */ public void add(int index) { Node node; if (size == 0) { // 此时环中没有数据 node = new Node(index, null, null); first = node; last = node; first.next = last; last.pre = first; } else { // 将环中的最后一个节点指向添加的节点,同时新增的节点的尾指针指向头节点，构成循环链表 node = new Node(index, first, last); last.next = node; // 链表的尾节点变成node last = node; } size++; } // 每次从当前节点往后遍历period单位个节点 public Node get(int period) { if (next == null) { next = first; } for (int i = 0; i < period-1; i++) { next = next.next; } if (next == null) { throw new RuntimeException("环中无数据"); } Node node = next; next = next.next; return node; } /** * 从环中删除指定节点 * * @return 删除元素的下标 */ public int remove(Node node) { Node pre = node.pre; Node next = node.next; pre.next = next; next.pre = pre; size--; return node.index; } }
执行结果如下：
5 2 8 7 1 4 6 3
可以发现，跟我们预期是一样的
在上面的示例中，我是自己实现了一个双向循环链表的结构，如果有的同学对链表不是很熟悉的话可以参考我的文章：数据结构 | 再也不怕被问链表了
这里对链表的相关知识不再赘述。之所以要使用双向循环链表，完全是为了加快删除的速度，利用空间换时间。
其实大家也可以使用JAVA中的LinkedList解决这个问题，我这里不直接给出答案，答案附在文末，大家可以先自行思考。
可以说，到目前为止，我们已经学会了使用链表解决约瑟夫问题，还有没有其他的解决方案呢？
首先来说，通过数组我们也是可以实现的。思路跟通过链表其实是差不多的
另外我再介绍一个解法，递归：
递归及公式推导：
这部分比较难理解，我尽力讲得明白点，希望大家多多思考，有问题可以留言交流。
对于递归算法而言，最难的是推导出递归公式，我们以之前的例子为例：
现在有(A B C D E F G H)8个人，排列如下：
A B C D E F G H 式1：0 1 2 3 4 5 6 7
我们以5为周期，那么第一个出列的人就是4，出列后排列如下：
A B C D F G H 式2：0 1 2 3 4 6 7
那么，现在我们就要从6的位置上，继续往后数5个人，然后让其出列，就是变成了下面这样的形式
F G H A B C D 式3：5 6 7 0 1 2 3
如果我们能将式3转换成式1这种形式，也就是形如下面这种形式：
// 经过一次出列后，现在剩下的只有7个人了 目标式：1 2 3 4 5 6 7
如果，我们完成转换，那么计算这种情况下第一个人出列的公式为：（n为总人数，m为周期）
推导如下：
8个人，周期为5，第一次出列的人的下标为-------5；（5-1）% 8
7个人，周期为5，第一次出列的人的下标为-------5；（5-1）% 7
6个人，周期为5，第一次出列的人的下标为-------5；（5-1）% 6
5个人，周期为5，第一次出列的人的下标为-------5；（5-1）% 5
4个人，周期为5，第一次出列的人的下标为-------1；（5-1）% 4
3个人，周期为5，第一次出列的人的下标为-------2；（5-1）% 3
2个人，周期为5，第一次出列的人的下标为-------1；（5-1）% 2
1个人，周期为5，第一次出列的人的下标为-------1；（5-1）% 1
为了方便下面的讲解，
我们将目标式第一次出列的人记为：
f(7,5,1)（7代表总人数-1，5代表周期，1代表第一次出列）,同理，原式第二次出列的人记为：f(8,5,2)
总结公式：
上面的公式，就是我们递归时的界。
那么现在的问题就是，我们如何将式3转换成式1呢？
我们一步步来，首先，将其变为1开头的，不难发现，最好的办法就是将所有的数字减去5，这样式3就变成了下面这种形式：
1 2 3 -4 -3 -2 -1
但是现在出现了负数，跟我们期望的还是有很大差距，这个时候我们又要思考了，怎么才能将后面的几个负数，变成4 5 6 7这种形式呢？不难发现，我们可以直接加上8，转换后如下：
9 10 11 4 5 6 7
现在好像又绕回来了，前面三个数又变了，我们期望的是1 2 3，那该怎么办呢？再去减8肯定不行了，又绕回去 了，那么我们不妨试试模运算，我们模8后发现式子变成了下面这种形式：
1 2 3 4 5 6 7
神不神奇，惊不惊喜？居然就成了我们目标式！！！
现在我们比较下，目标式中的人的下标，跟经过一次出列后所得式2的下标
F G H A B C D 式3： 6 7 8 1 2 3 4 目标式：1 2 3 4 5 6 7
我们可以发现，式3中跟目标式中的同一个人有不同的下标，并且它们的关系满足我们推导的流程
在上面我们进行的是一个正序推导，也就是说，我们是要先知道f(8,5,2)的值才能计算出f(7,5,1)的值，在上面的例子中，f(8,5,2) = 2 ,则经过我们上面的推导,f(7,5,1) = (2-5+8) mod 8 = 5
但是现在实际的问题是，我们并不知道f(8,5,2)的解，但我们知道f(7,5,1)的解 = （5-1） mod 7 + 1 = 5，也就是说我们要进行逆推才行。通过观察我们不难得出，逆推的公式为：
对其进行抽象就有
其中，m为总人数，n为周期，k为第几次出列，可以看出这个式子中，k一定大于1
现在我们已经有了递归的关系，同时有了递归的界，可以写代码如下
public class DiGui { // m个人，n为周期，i步 public static int di(int m, int n, int i) { // 这是我们递归的界 if (i == 1) { return (n - 1) % m ; } // 递归公式 return (di(m - 1, n, i - 1) + n ) % m; } public static void main(String[] args) { int n = 5; int m = 8; // 依次输出 // f(8,5,1) 8个人，周期为5，第一次出列的人 // f(8,5,2) 8个人，周期为5，第二次出列的人 for (int i = 1; i < m + 1; i++) { // 我们输出的是下标从0开始，对应队伍中人要加1 System.out.println(di(m, n, i)+1); } } }
对于递归的思考：
在上面的例子中，我们是通过步数来限定递归的界，也就是说8个人，最多8步就可以将所有的人都出队。我们可以思考下，还有没有另外一种方式可以限定递归的界呢？大家可以这样想，步数在递增的过程中，对应着的就是人数的递减，同时当只剩一个人的时候，f(1,n,i) = 0 。基于这种思想，我们可以写代码如下：
public static void main(String[] args) { int n = 5; int m = 8; // 当i = 1 时，下标为0 int lastOne = 0; // f(1,5,1) = 0 // 依次输出 f(2,5,2) // 依次输出 f(3,5,3) // 依次输出 f(4,5,4) // 依次输出 f(5,5,5) // 依次输出 f(6,5,6) // 依次输出 f(7,5,7) // 计算出出 f(8,5,8) for (int i = 2; i <= m; i++) { lastOne = (lastOne + n) % i; } // 这样可以求出最后一个出列的人，我们是从0开始计算，也要加1 System.out.println(lastOne+1); }
思考题答案：
// 这里我特地将注释删除了，希望大家多多思考 // 如果有更好的方法也可以给我留言，一起探讨 // 提供了两种解决方法，一种依赖迭代器，一种直接通过下标 public class YSF { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); for (int i = 1; i < 9; i++) { list.add(i); } // method01(list, 5); method02(list,5); } // 通过下标的方式解决 private static void method01(LinkedList<Integer> list, int period) { // 从0开始遍历 int index = 0; while (!list.isEmpty()) { for (int i = 1; i < period; i++) { if ((index == list.size() - 1)) { index = 0; } else if ((index == list.size())) { index = 0; i--; } else { index++; } } System.out.println(list.get(index)); list.remove(index); } } // 通过迭代器的方式 public static void method02(LinkedList<Integer> list, int period) { int count = 0; Iterator<Integer> iterator = list.iterator(); while (list.size() > 0) { if (iterator.hasNext()) { Integer next = iterator.next(); count++; if (count == period) { iterator.remove(); count = 0; System.out.println(next); } }else { iterator = list.iterator(); } } } }
/
