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

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

2018-03-16 673

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

据说着名犹太历史/数学家约瑟夫（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-17

561

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-17

656

发表评论

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

腾讯云软件源

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

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Spring

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