java数据结构题之约瑟夫问题-低调大师

java数据结构题之约瑟夫问题

2018-03-16 733

约瑟夫问题：转载自约瑟夫问题

据说着名犹太历史/数学家约瑟夫（Josephus）有过以下的故事：在罗马人占领乔塔帕特後，40个犹太士兵与约瑟夫躲到一个洞中，眼见脱逃无望，一群人决定集体自杀，约瑟夫建议自杀方式，41个人排成圆圈，由第1个人开始报数，每报数到5的人就必须自杀，然後由下一个重新报数，直到所有人都自杀身亡为止。如果你是约瑟夫，你应该在哪个位置才能活下来（最后只剩下你）?

我的答案：

 
        package 
        p1; 
       
        import 
        java.util.LinkedList; 
       
        import 
        java.util.List; 
       
        public 
        class 
        KillSelf { 
       
        //构造链式列表，用来模拟人。 
       
        private 
        static 
        List<String> list = 
        new 
        LinkedList<String>(); 
       
        //记忆自杀那个人前后的人集合有序子列表 
       
        private 
        static 
        List<String> listBefore,listAfter; 
       
        //自杀那个人的编号从1开始 
       
        private 
        static 
        String killedNum = 
        null
        ; 
       
        private 
        static  
        int 
        KILL_INDEX = 
        4
        ; 
       
        //记录自杀的总人数 
       
        private 
        static 
        int 
        sum = 
        0
        ; 
       
        public 
        static 
        void 
        main(String[] args) { 
       
        //记住每个从最开始的编号 
       
        for
        (
        int 
        i = 
        1
        ;i <= 
        41
        ;i++) 
       
        { 
       
        list.add(i+
        ""
        ); 
       
        } 
       
        //其实自杀的过程，是一个循环的过程，所以用循环来解决。 
       
        while
        (
        true
        ) 
       
        { 
       
        //获取自杀位置前后的子集 
       
        if
        (list.size()>=
        5
        )   
        //当人数大于等于5个人时 
       
        { 
       
        listBefore = 
        new 
        LinkedList<String>(list.subList(
        0
        , KILL_INDEX)); 
        //不能直接用subList的返回值，要包装一下 
       
        listAfter = 
        new 
        LinkedList<String>(list.subList(KILL_INDEX+
        1
        , list.size())); 
       
        }
        else 
        if
        (list.size() > 
        1 
        && list.size() < 
        5
        )       
        //当人数多于1个人但是少于5个人时 
       
        { 
       
        KILL_INDEX = 
        5
        %list.size()-
        1
        ; 
        //这个判断很巧妙 
       
        if
        (KILL_INDEX > 
        0 
        && KILL_INDEX <list.size()-
        1
        ) 
       
        { 
       
        listBefore = 
        new 
        LinkedList<String>(list.subList(
        0
        , KILL_INDEX)); 
        //不能直接用subList的返回值，要包装一下 
       
        listAfter = 
        new 
        LinkedList<String>(list.subList(KILL_INDEX+
        1
        , list.size())); 
       
        }
        else 
        if
        (KILL_INDEX == 
        0
        ) 
       
        { 
       
        listBefore.clear(); 
       
        listAfter = 
        new 
        LinkedList<String>(list.subList(KILL_INDEX+
        1
        , list.size())); 
       
        }
        else 
        if
        (KILL_INDEX == list.size()-
        1
        ) 
       
        { 
       
        listBefore = 
        new 
        LinkedList<String>(list.subList(
        0
        , KILL_INDEX)); 
       
        listAfter.clear(); 
       
        } 
       
        }
        else 
       
        break
        ; 
       
        //将子集的后与前连接起来，更新总的集合 
       
        killedNum = list.get(KILL_INDEX); 
       
        sum++; 
       
        System.out.println(
        "编号" 
        + killedNum + 
        "已自杀!-----自杀总人数达" 
        + sum); 
       
        //更新list 
       
        list.clear(); 
       
        list.addAll(listAfter); 
       
        list.addAll(listBefore); 
       
        System.out.println(
        "剩余人员编号："
        +list); 
       
        System.out.println(
        ""
        ); 
       
        } 
       
        System.out.println(
        ""
        ); 
       
        System.out.println(
        "结论：处在"
        +list.get(
        0
        )+
        "号才不会自杀"
        ); 
       
        } 
       
        }

但是网上的帖子，几行代码就解决问题了，这就是算法的魅力！

本文转自屠夫章哥 51CTO博客，原文链接：http://blog.51cto.com/4259297/1658382，如需转载请自行联系原作者

微信关注我们

原文链接：https://yq.aliyun.com/articles/549020

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

用Python做爬虫时相关tips的参考文章集锦（refreshing）

1.Python 3.x中的urllib的改动 2.Python的hasattr() getattr() setattr() 函数使用方法详解 3.正则表达式 re.findall 用法注意：用$符号表示以html结尾的字符串返回,判断是否字符串结束的字符串只有字符串能匹配模板定义，才会返回模板，否则返回空list（多少一个字母也不行）符号^表示匹配以https开头的的字符串返回, 道理相似，注意more0例子跟more的区别 4.'module' object is not callable 模块名和函数名一样了，负责调用的代码解析的是模块名，不是函数名，因而发生错误。 5.cannot use a string pattern on a bytes-like object 加上object=object.decode('utf-8')#python3这句代码 6.itertools无限迭代器

2018-03-16

626

Java中数组高级之各种排序代码

1.冒泡排序 1 package cn.itcast; 2 3 /* 4 * 冒泡排序基本思路是： 5 * 依次比较相邻的两个数，将小数放在前面，大数放在后面。 6 * 即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。 7 * 然后比较第2个数和第3个数，将小数放前，大数放后，如此继续， 8 * 直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。 9 * 在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数）， 10 * 将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数。（其实在整个数列中是第二大的数）。 11 * 如此下去，重复以上过程，直至最终完成排序。 12 */ 13 public class BubbleSort { 14 public static void sort(int[] data) { 15 for (int i = 0; i < data.length - 1; i++) { 16 for (...

2018-03-16

729

发表评论

资源下载

更多资源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。