ZGGSONG WIKI

Java约瑟夫环问题

约瑟夫环问题:人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,执行下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。

例题

设有n个人围坐一圈并按顺时针方向从1到n编号,从第1个人开始进行1到m的报数,报数到第个m人,此人出圈,再从他的下一个人重新开始1到m的报数,如此进行下去直到所剩下一人为止。

解决方法:LinkedList + Iterator

  • LinkedList类是双向链表,列表中的每个节点都包含了对前一个和后一个元素的引用
  • Iterator是Java迭代器最简单的实现,为List设计的ListIterator具有更多的功能,它可以从两个方向遍历List,也可以从List中插入和删除元素
  • hasNext:没有指针下移操作,只是判断是否存在下一个元素
  • next:指针下移,返回该指针所指向的元素
  • remove:删除当前指针所指向的元素,一般和next方法一起用,这时候的作用就是删除next方法返回的元素

代码

public static void main(String[] args) {
        int n = 10, m = 3;
        LinkedList<Integer> L = new LinkedList<>();
        for (int i = 1; i <= n; i++) L.add(i);
        Iterator<Integer> iterator = L.iterator();
        while (L.size() > 1) {
            for (int cnt = 0; cnt < m; cnt++) {
                if (iterator.hasNext())
                    iterator.next();
                else {
                    iterator = L.iterator();
                    iterator.next();
                }
            }
            iterator.remove();
        }
        System.out.println("The last one is: " + L.getFirst());
    }
Copyright © 2020 ZGGSONG