Java达成 Josephus约瑟夫环问题
发布时间：2021-11-15 15:05:08 所属栏目：教程 来源：互联网
导读：import Java.util.ArrayList; import java.util.ListIterator; import java.util.Scanner; public class Josephus { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m, n; m = sc.nextInt(); n = sc.nextInt(); pass(m
|
import Java.util.ArrayList; import java.util.ListIterator; import java.util.Scanner; public class Josephus { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m, n; m = sc.nextInt(); n = sc.nextInt(); pass(m, n); // 注意这里的m为传递次数，要与报数次数区分开.即：传递次数 = 报数次数-1. } public static void pass(int m, int n) { int i, j, mPrime, numLeft; ArrayList<Integer> L = new ArrayList<Integer>(); // 为队列中的成员编号：从1~n for (i=1; i<=n; i++) L.add(i); // 初始化各个元素 ListIterator<Integer> iter = L.listIterator(); Integer item=0; numLeft = n; mPrime = m % n; // 进行n此循环，每次删除一个成员 for (i=0; i<n; i++) { mPrime = m % numLeft; if (mPrime <= numLeft/2) // 当mPrime小于剩余人数的一般时，进行正移。（向后移next） { if (iter.hasNext()) item = iter.next(); for (j=0; j<mPrime; j++) { if (!iter.hasNext()) iter = L.listIterator(); item = iter.next(); } } else { for (j=0; j<numLeft-mPrime; j++) // 当mPrime大于剩余的一般人数时，进行反移。（向前移previous） { if (!iter.hasPrevious()) iter = L.listIterator(L.size()); item = iter.previous(); } } System.out.print("Removed " + item + " "); iter.remove(); if (!iter.hasNext()) iter = L.listIterator(); System.out.println(); for (Integer x:L) // 利用增强for循环遍历表 System.out.print(x + " "); System.out.println(); numLeft--; } System.out.println(); } } 对于Josephus问题有两个地方是可以进行优化的。 (总人数为N，编号为从0~N-1；经过M次报数去除一个成员，剩余成员个数为numleft， 记M%numleft为mPrime) 1、被移除的成员与上一个成员之间的距离是M%numleft-1（报数次为M%numleft）.当M大于N时，该计算方式将节省大量时间 2、当mPrime大于numleft的时候可以反向遍历该表来查找要去除的成员。这样可以节省时间。同样这也就要求了该表必须是一个双向表才行。（即含有Previous方法） 该算法实现原理即为： 第一轮，必定为编号M%N-1的成员被去除，第二轮为在第一轮的基础上即从编号为M%N的成员开始正移mPrime-1个单位（或者反移numleft-mPrime-1个单位）。若将M%N即为编号0，开始重新编号，那么第二轮被删除的成员编号便是M%（numleft）-1，由此可得该轮要被删除的成员与上一轮去除成员之间的距离为M%numleft，这里可利用迭代器来实现。 这里我们便可以得到成员编号与该轮成员数目的关系是：（n表示该轮所剩余的成员数目，Index（n）表示该轮成员的编号（从0开始）） Index(n) = (Index(n - 1) + m) % n。  （编辑：东莞站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
