java用链表实现约瑟夫环算法 约瑟夫环Java实现

  面试中可能经常会遇到约瑟夫环问题，逻辑上很简单，就是看怎么实现了，一般而言，最简单最直观的就是利用链表，然后构建一个循环结构，正好是环，最后计算出结果。

  遍历环形链表会是一个无限循环，如果链表中的数据逐渐减少，不控制终究会一个不剩，这又不满足我们问题的求解java用链表实现约瑟夫环算法 约瑟夫环Java实现，因此我们需要定义出循环结束的条件，按照约瑟夫环的规则，只剩下一个的时候就结束，在环形链表结构中java用链表实现约瑟夫环算法，那就是结点本身的下一个节点就是它自己。这样就可以结束遍历了。最后打印出剩下的结点，问题解决。

  这里给出Java版本的实现：

  //约瑟夫环java实现

  //约瑟夫环问题的起源来自犹太历史学家约瑟夫和他的朋友以及39其余的犹太人，总共41人为了躲避敌人，藏在一个山洞中，39个犹太人决定宁愿死也不被敌人抓到，于是决定自杀，所有人排成一个圈，由第一个人开始报数，每当数到3，就自杀。这个游戏接着从自杀的位置开始，还是从1数到3。依次类推，约瑟夫将朋友和自己安排在了16和31的位置，最后顺利逃过了自杀这一劫java用链表实现约瑟夫环算法，因为最后就剩他朋友了。

   package com.nowcoder.community.算法;

    /**
     * @author 找花插的牛粪
     * @apiNote 约瑟夫环
     */
    public class 约瑟夫环 {
        /**
    <p>

         * 方法入口
         */
        public static void getman(int n){
            //数到3就自杀
            int k=3;
            //构建头结点 @prame=null，和他的引用对象
            Node head = new Node();
            Node cur = head;
            //构建环
            for (int i = 1; i 2->3 ,其实应该走2步，但是for循环再此处走了一步
                for (int i = 1; i 2   4   再此处删除了3 然后拼接 4   1->2->4
                //所以我们必须拿到 2这个节点,否则不能实现链表元素的删除，谁让咱用的是单链表呢
                System.out.println(begin.next.data+"号犹太人"+" go die");
                //此时begin为2节点
                begin.next = begin.next.next;
                begin = begin.next;
            }
            //最后剩下的一个结点
    &emsp;&emsp;![用顺序表实现约瑟夫环_java用链表实现约瑟夫环算法_用单链表实现约瑟夫环][1]

            System.out.println("最后胜出者为:"+begin.data+"号");
        }
        public static void main(String[] args) {
            //以4个人为例
            getman(4);
            System.out.println("========================");
            //以41个人为例 16胜出
            getman(41);
        }
    }
    &emsp;&emsp;![用单链表实现约瑟夫环_用顺序表实现约瑟夫环_java用链表实现约瑟夫环算法][2]

    /**
     * @author 找花插的牛粪
     * @apiNote  构建链表成员
     */
    class Node{
        int data;
        Node next;
        public Node(){};
        public Node(int data){this.data=data;}
    }

</p>
  运行程序，打印结果：

  

  

  文章来源:https://blog.csdn.net/weixin_41677268/article/details/110726500