约瑟夫环之递归算法

本文主要是介绍约瑟夫环之递归算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。由第一个人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到最后剩下一个人。
一般的思路就是通过一个count计数的方法，循环遍历链表，逐一删除。但是这样的方法时间复杂度要有O（n×m），（总共要删除n-1个数，每删除一个需要遍历m次）。那有没有什么办法直接就找到我们需要删除的那个节点呢，比如给你链表1→2→3→4→5→1，这是环状链表。如果m=3的话，最后留下的是第4个节点。这里我们就需要借用数学的方式来进行推到公式，利用递归的方式求解了。
递归求解思路：
（我通过递归的方式，返回需要删除第几个节点，所以，节点编号从1开始，返回的也是第几个节点）
第一次删除第m个节点很简单，就是m%n的那个节点，但是第二次删除节点就有点困难了，为什么，因为，你需要从第m+1的节点重新从1开始数，数到第m个节点再次删除。其实，不知道你们有没有发现，其实第二次开始数的第1个节点，就是上一次的m+1号节点。所以前一个链表节点和后一个链表节点对应的编号关系就是：
oldNum=（newNum+m-1）%（当前节点数）+1 （1）
下面从图片分析下：
这里写图片描述

根据公式（1）的关系，你就可以由新链表找到对应就链表的编号位子了。当链表中由i个节点时，编号对应的公式是：num(i) = （num（i-1）+m-1）%i +1;
（如果链表从0开始编号的话，那么公式就是num(i) = （num（i-1）+m）%i ），返回的是下标值，且最后num（1） = 0；）

代码实现：

public class JosephusProblem {//链表节点类public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}public static Node josephusKill2(Node head, int m) {if (head == null || head.next == head || m < 1) {return head;}Node cur = head.next;int tmp = 1; // 表示链表长度/**计算链表长度*/while (cur != head) {tmp++;cur = cur.next;}tmp = getLive(tmp, m); // 返回链表中应该删除的那个值位置while (--tmp != 0) {head = head.next;}head.next = head;return head;}public static int getLive(int i, int m) {if (i == 1) {//如果从0开始编号的话，此处return 0return 1;}//如果从0开始编号的话，此处(getLive(i - 1, m) + m) % i，返回的就是下标值return (getLive(i - 1, m) + m - 1) % i + 1;//这个就是上述公式实现}
}