约瑟夫环问题（josephus problem）详解
约瑟夫环问题描述:
编号为1,2,3...n的人一词围成一圈，从第k个人开始报数（从1开始），数到m的人退出。接着下一个人又从1开始报数，数到m的人退出，以此类推。问：剩下的人的编号是多少？
如：n=6,m=3,k=1
原始序列： 1 2 3 4 5 6 ； 从编号1开始报数
第一轮数完后的序列为： 1 2 4 5 ； 3、6出列——从编号1开始报数
第二轮数完后的序列为： 1 2 5 ； 4出列——从编号5开始报数
第三轮数完后的序列为： 1 5 ； 2 出列——从5开始报数
第四轮数完后的序列为： 1 ；5 出列
所以，最后出列的编号为1.
求解方法一：模拟报数过程，时间复杂度O(M*N)
该方法的思想是将所有的编号构造成一个环形链表，然后移动到编号为k的节点开始报数，数到M的时候移除链表节点，接着从下一个节点开始报数，移除数到M的节点。以此类推，直到只剩下一个节点。
public static int josephusOMN(int n, int m) {return josephusOMN(n, m, 1);}public static int josephusOMN(int n, int m, int k) {if (n <= 0 || m <= 0 || k <= 0)return -1;// consruct josephus circleJosephusNode header = new JosephusNode(1);JosephusNode nodes = header;for (int i = 2; i <= n; i++) {nodes.mNext = new JosephusNode(i);nodes = nodes.mNext;}nodes.mNext = header;// endfor (int i = 1; i < k; i++) {nodes = nodes.mNext; // move to start off person}while (nodes != nodes.mNext) {for (int i = 1; i < m; i++) {nodes = nodes.mNext;}// System.out.print(nodes.mNext.mNum + " , ");nodes.mNext = nodes.mNext.mNext;}return nodes.mNum;}private static class JosephusNode {public int mNum;public JosephusNode mNext;public JosephusNode(int num) {this(num, null);}public JosephusNode(int num, JosephusNode node) {mNum = num;mNext = node;}}求解方法二：方便求解最后的胜利者同时也适合打印 出列 序列的，时间复杂度O(N).
下面方法借鉴自Java程序练习-约瑟夫环问题
public static int josepusONWithList(int n, int m) {return josepusONWithList(n, m, 1);}public static int josepusONWithList(int n, int m, int k) {if (n <= 0 || m <= 0 || k <= 0)return -1;LinkedList list = new LinkedList();for (int i = 1; i <= n; i++)list.add(i);int outPos;while (list.size() > 1) {outPos = (int) (k + m - 2) % list.size();// System.out.print(list.get(outPos)+" , ");list.remove(outPos);k = outPos + 1;}// System.out.println(list.get(0));return list.get(0);} 求解方法三：对模拟方法的改进——数学优化方法，时间复杂度O(N)。具体思想参见约瑟夫环的数学优化方法
public static int josephusON(int n, int m) {return josephusON(n, m, 1);}/*** Josephus 环的一个O(N)算法* * @param n 总人数* @param m 数到m的人出列* @param k 开始报数人的编号* @return 最后一个出列的编号*/public static int josephusON(int n, int m, int k) {int p = 0;for (int i = 2; i <= n; i++) {// System.out.print((p + k == n ? n : (p + k) % n)+" ");p = (p + m) % i;}return p + k == n ? n : (p + k) % n; // 返回最后一人的位置}在有时候需要知道出列的序列，上述System.out部分就是出列序列。
约瑟夫环问题求解就先写到这里，朋友们若有其他方法也别忘了告诉楼主哦^_^... 收集到其他求解方法后再补充。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！