首页 > 代码库 > 18.n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始， 每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。 当一个数字删除后，从被删除数字的下一个继续删除第m个数字。 求出在这个圆圈中剩下的最后一个数字。
18.n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始， 每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。 当一个数字删除后，从被删除数字的下一个继续删除第m个数字。 求出在这个圆圈中剩下的最后一个数字。
转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4263868.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始， 每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。 当一个数字删除后，从被删除数字的下一个继续删除第m个数字。 求出在这个圆圈中剩下的最后一个数字。
题目分析：
这个题目是一个约瑟夫环的问题，下面给出两种解决方案。
(一) 运用单循环链表解决。
这种方案能按顺序输出每次删除的元素，需要一个有n个结点的环形列表来模拟这个删除的过程，因此内存开销为O(n)。每删除一个数字需要m步运算，总共有n个数字，因此总的时间复杂度是O(mn)。当m和n都很大的时候，这种方法是很慢的。
算法思想：假设已经建立了一个不带头节点的单循环链表，设置计数器count(初始化为1)统计在扫描循环链表的过程中是否技术到m,如果count=m,则输出该节点的编号并删除该节点,遍历的指针往后移动，count复位为1；否则遍历的指针往后移动，count++。
算法实现：
1 //运用循环单链表的方式实现 2 private void josephusList(Node first, int n, int m){ 3 if(n < 1 || m < 1) 4 return; 5 if(n==1){ 6 System.out.print(first.data+" "); 7 } 8 else{ 9 Node pre = first; //当前节点的前驱10 Node p = first.next; //当前节点11 int count = 2;12 while(p!=pre){13 if(count==m){14 System.out.print(p.data+" ");15 Node r = p.next; //删除当前节点16 pre.next = r;17 p=r;18 count = 1;19 }20 else{21 pre = p;22 p = p.next;23 count++;24 }25 }26 System.out.println("\n最后一个删除的元素:"+p.data);27 }28 }
(二) 运用数学分析找出规律,快速求解。
首先：定义最初的n个数字（0,1,…,n-1）中最后剩下的数字是关于n和m的方程为f(n,m)。 在这n个数字中，第一个被删除的数字是m%n-1，为简单起见记为k。那么删除k之后的剩下n-1的数字为0,1,…,k-1,k+1,…,n-1，并且下一个开始计数的数字是k+1。相当于在剩下的序列中，k+1排到最前面，从而形成序列k+1,…,n-1,0,…k-1。该序列最后剩下的数字也应该是关于n和m的函数。由于这个序列的规律和前面最初的序列不一样（最初的序列是从0开始的连续序列），因此该函数不同于前面函数，记为f’(n-1,m)。最初序列最后剩下的数字f(n,m)一定是剩下序列的最后剩下数字f’(n-1,m)，所以 f(n,m)=f’(n-1,m) 。
然后：来我们把剩下的的这n-1个数字的序列k+1,…,n-1,0,…k-1作一个映射，映射的结果是形成一个从0到n-2的序列：
k+1 -> 0
k+2 -> 1
…
n-1 -> n-k-2
0 -> n-k-1
…
k-1 -> n-2
1）把这个映射定义为p，则p(x)= (x-k-1)%n，即如果映射前的数字是x，则映射后的数字是(x-k-1)%n。
2）对应的逆映射是p逆(x)=(x+k+1)%n，即如果映射后的数字是x，则映射前的数字是(x-k-1)%n。
由于映射之后的序列和最初的序列有同样的形式，都是从0开始的连续序列，因此仍然可以用函数f来表示，记为f(n-1,m)。根据我们的映射规则，映射之前的序列最后剩下的数字f’(n-1,m)= p逆 [f(n-1,m)]=[f(n-1,m)+k+1]%n。把k=m%n-1代入得到f(n,m)=f’(n-1,m)=[f(n-1,m)+m]%n。
经过上面复杂的分析，我们终于找到一个递归的公式。要得到n个数字的序列的最后剩下的数字，只需要得到n-1个数字的序列的最后剩下的数字，并可以依此类推。当n=1时，也就是序列中开始只有一个数字0，那么很显然最后剩下的数字就是0。我们把这种关系表示为：
0 n=1
f(n,m)={
[f(n-1,m)+m]%n n>1
注意：f(n,m)这个函数只能用于返回最后一个输出的数字，而不能用于求出过程中每次输出的数字。f(n,m)表示求出[0,1,2...,n-1]中最后一个输出的元素，f(n-1,m)表示求出[0,1,2...,n-2]中最后一个输出的元素.
算法的递归实现：
1 //递归的思想 ,省去了m和n的检查2 private int LastRemaining(int n,int m) { 3 if(n == 1 ) { 4 return 0;5 }6 else7 return (LastRemaining(n-1,m)+m)%n;8 }
算法的非递归实现：
1 //非递归的思想 ,省去了m和n的检查2 private int lastRemain1(int n,int m) { 3 int last = 0;4 for(int i=2;i<=n;i++){5 last = (last+m)%i;6 }7 return last;8 }
java 实现的完整源码：
1 package com.interview; 2 3 /** 4 * n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始， 5 * 每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。 6 * 当一个数字删除后，从被删除数字的下一个继续删除第m个数字。 7 * 求出在这个圆圈中剩下的最后一个数字。 8 * @author wjh 9 * 10 */ 11 public class _18JosephCycle { 12 13 /** 14 * @param args 15 */ 16 public static void main(String[] args) { 17 _18JosephCycle invoker = new _18JosephCycle(); 18 int n = 17,m=5; 19 System.out.println("1)这是用递归的思想求得的最后删除的元素："); 20 System.out.println(invoker.lastRemain(n, m)+"\n"); 21 System.out.println("2)这是用非递归的思想求得的最后删除的元素："); 22 System.out.println(invoker.lastRemain1(n, m)+"\n"); 23 System.out.println("3)这是用单循环链表实现的依此删除的删除的元素："); 24 Node first = invoker.cycleList(n); 25 invoker.josephusList(first, n, m); 26 } 27 28 //递归的思想 ,省去了m和n的检查 29 private int lastRemain(int n,int m) { 30 if(n == 1 ) { 31 return 0; 32 } 33 else 34 return (lastRemain(n-1,m)+m)%n; 35 } 36 37 //非递归的思想 ,省去了m和n的检查 38 private int lastRemain1(int n,int m) { 39 int last = 0; 40 for(int i=2;i<=n;i++){ 41 last = (last+m)%i; 42 } 43 return last; 44 } 45 46 47 //运用循环单链表的方式实现 48 private void josephusList(Node first, int n, int m){ 49 if(n < 1 || m < 1) 50 return; 51 if(n==1){ 52 System.out.print(first.data+" "); 53 } 54 else{ 55 Node pre = first; //当前节点的前驱 56 Node p = first.next; //当前节点 57 int count = 2; 58 while(p!=pre){ 59 if(count==m){ 60 System.out.print(p.data+" "); 61 Node r = p.next; //删除当前节点 62 pre.next = r; 63 p=r; 64 count = 1; 65 } 66 else{ 67 pre = p; 68 p = p.next; 69 count++; 70 } 71 } 72 System.out.println("\n最后一个删除的元素:"+p.data); 73 } 74 } 75 76 77 //创建带头节点的无环单链表,真正的节点有m个 78 private Node cycleList(int n){ 79 Node first = new Node(0,null); //头节点 80 Node r = first; //指向链表的尾节点 81 for(int i=0;i<n;i++){ 82 Node node = new Node(i,null); 83 r.next = node; 84 r = node; 85 } 86 first = first.next; 87 r.next = first; //若是构建无环单链表，此处 r.next = null; 88 return first; 89 } 90 91 //创建一个泛型节点类 92 class Node { 93 public int data; 94 public Node next; 95 public Node() { 96 super(); 97 } 98 public Node(int data, Node next) { 99 super();100 this.data =http://www.mamicode.com/ data;101 this.next = next;102 }103 }104 }
运行结果：
这是用递归的思想求得的最后删除的元素：
10
这是用非递归的思想求得的最后删除的元素：
10
这是用单循环链表实现的依此删除的删除的元素：
4 9 14 2 8 15 5 12 3 13 7 1 0 6 11 16
最后一个删除的元素:10
18.n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始， 每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。 当一个数字删除后，从被删除数字的下一个继续删除第m个数字。 求出在这个圆圈中剩下的最后一个数字。