Skip to main content
 首页 » 编程设计

java算法之单链表应用(3)循环链表解决约瑟夫问题

2022年07月18日120yxwkf
//循环列表场景:传说有这样一个故事,在罗马人占领乔塔帕特后,39 个犹太人与约瑟夫及他的朋友躲到一个洞中,39个犹太人决 
    //定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,第一个人从1开始报数,依次往 
    //后,如果有人报数到3,那么这个人就必须自杀,然后再由他的下一个人重新从1开始报数,直到所有人都自杀身亡 
    //为止。然而约瑟夫和他的朋友并不想遵从。于是,约瑟夫要他的朋友先假装遵从,他将朋友与自己安排在第16个与 
    //第31个位置,从而逃过了这场死亡游戏 。 
    //以下代码打印这41个人依次被杀的下标。 
    public static void main(String[] args) { 
        //构造循环列表 
        Node first = new Node(0,null); 
        Node pre = first; 
        for(int i = 1; i < 41;i++){ 
            Node middle = new Node(i,null); 
            pre.next = middle; 
            pre = middle; 
        } 
        pre.next = first; 
 
        Node report = first; //初始化第一个人报数 
        Integer count = 1; //报1 
        Node preReport = null; //上一个人为null 
        while (!report.equals(report.next)){ 
            preReport = report;  // 上一个报数的人 
            report = report.next; //当前报数的人 
            count++; //继续报数 
            if(count == 3){ //当前人报到3,剔除此人 
                System.out.print(report.t + "  "); 
                preReport.next = report.next; 
                count = 0; 
            } 
        } 
        System.out.println("最后活着的人:" + report.t); 
    } 
 
    private static class Node<T>{ 
        private T t; 
        private Node next; 
 
        public Node(T t, Node next) { 
            this.t = t; 
            this.next = next; 
        } 
    }

本文参考链接:https://www.cnblogs.com/maohuidong/p/14216304.html
阅读延展