数据结构与算法Java版——约瑟夫环问题

浅浅的花香味﹌ 2022-06-06 12:26 156阅读 0赞

有n个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第*k*个人。接着，再越过k-1个人，并杀掉第*k*个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

简单的说就是规定数到第N个人就杀了他，比如杀第五个人，那么 1 2 3 4 5就杀了5。

代码如下:

public class Josephus {
        
        /**
         * 玩游戏的人数
         */
        private final int circleNum = 20;
        /**
         *  数到五个就上天
         */
        private final int unluckyNum = 5;
    
        class Person {
            //这个人的下一个
            Person next;
            int val;
    
            public Person(int val) {
                this.val = val;
            }
        }
    
        public void killPerson() {
            Person header = new Person(1);
            Person x = header;
            Person next = null;
            //构成环
            for (int i = 2; i <= circleNum; i++) {
                next = new Person(i);
                x.next = next;
                x = next;
            }
            //首尾相连
            x.next = header;
    
            int num = 1;
            System.out.println("被杀的顺序为:");
            //循环直到只剩一个人
            while (x.next!=x) {
                if(num==5){
                    System.out.print(x.next.val+" ");
                    x.next = x.next.next;
                    num=1;
                }
                x = x.next;
                num++;
            }
            System.out.println("\n最后剩下："+x.val);
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Josephus josephus = new Josephus();
            josephus.killPerson();
        }
    
    }

如图所示，就完成了这个算法。

![50747737.jpg][]

[50747737.jpg]: http://or0um8wrx.bkt.clouddn.com/17-11-8/50747737.jpg