顺序表实现Josephus（约瑟夫斯）环问题

旧城等待， 2022-07-15 02:39 124阅读 0赞

背景简介：  
著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特後，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。  
然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。（[源自百度百科][Link 1]）

1、修改我上篇文章的SeqList 构造函数，详情请看[顺序表如何实现增删改查][Link 2]

public class SeqList implements MyList { 
        Object[] element;
        private int length = 0;
        public SeqList (int len){
            length=len;
            element= new Object[len];
            for(int i=0;i<len;i++){
              //由ascii 值设定每个元素的值
                element[i]=(char)(i+65);
            }
    
        }
        public SeqList(Object[] o) {
            element = o;
            length = o.length;
        }
    
        @Override
        public boolean isEmpty() {
            if (length == 0) {
                return true;
            } else {
                return false;
            }
        }
    
        @Override
        public int getLength() {
            return this.length;
        }
    
        @Override
        public Object get(int i) {
            if (this.isEmpty()) {
                return null;
            }
            if (i < 0 || i > this.length) {
                System.out.println("查找位置不合法");
                return null;
            }
    
            return element[i - 1];
        }
    
        @Override
        public void set(int i, Object x) {
            if (i < 0 || i > this.length) {
                System.out.println("位置不合法");
                return ;
            }
    
            element[i]=x;
        }
    
        @Override
        public void insert(int i, Object x) {
            if (i < 0 || i > length) {
                System.out.println("插入位置不合法");
            }
            //用param暂时保存element的值
            Object[] param = this.element;
            // 由于插入 需要多一个存储位 同时长度加1
            element = new Object[++length];
            for (int j = 0; j < param.length; j++) {
                element[j] = param[j];
            }
            //插入处向后挪一位
            for (int j = element.length - 1; j > i; j--) {
                element[j] = element[j - 1];
            }
            element[i] = x;
    
        }
    
        @Override
        public void remove(int i) {
            if (i < 0 || i > length) {
                System.out.println("位置不合法");
            }
    
            for (int j = i+1; j <length; j++) {
               element[j-1]= element[j];
            }
            length--;
    
        }
    
    
    
        @Override
        public void clear() {
             element=null;
             length = 0;
        }
    
        @Override
        public String toString() {
            if (this.isEmpty()) {
                return null;
            }
            String str = "";
            for (int i = 0; i < length; i++) {
                str += element[i] + " ";
            }
            return str;
        }
    }

2、Josephus类

package dataStructure.seqList;
    
    public class Josephus {
        private SeqList s;
        private int length;
        private int start;
        int distance;
    
        public static void main(String[] args) {
            Josephus josephus = new Josephus(41, 0, 3);
            //设置josephus和他的伙伴的值
            josephus.setjosephusinfo();
            josephus.start();
            System.out.println(josephus.toString());
        }
    
    
        public Josephus(int number, int start, int distance) {
            this.length = number;
            this.start = start;
            this.distance = distance;
            System.out.println("number is " + number + " " + "start at " + start
                    + " " + "distance is " + distance);
            s = new SeqList(number);
        }
    
        public void setjosephusinfo() {
            s.set(15, "josephus");
            s.set(30, "partner");
        }
    
        private void start() {
            int move=start;
            //注意事项 移除的时候长度减一了，同时移除的
            while (s.getLength() > 1) {
                move = move + distance-1;
                if (move >= s.getLength()) {
                    move=move%s.getLength();
                } 
                System.out.println(s);
                s.remove(move);
                System.out.println("移除第"+(move+1)+"个");
            }
    
        }
    
        @Override
        public String toString() {
            return s.toString();
        }
    
    }

运行效果：  
由于是数组的原因，**索引15 即 第16位，30位即31位**  
![20161030113020575][]  
最后两步运行结果为josephus和他的partner,  
惊叹他是如何做到的！  
![这里写图片描述][20161030113151479]

[Link 1]: http://baike.baidu.com/link?url=9IhcN-mDQG1iRXHJrkuyGaCsWm6e181FLR54QNtGcTAW5jxYlbFJGJqXoDt2-oMQp0qSHKsZSshlVcKJMbGJHQxOapRqAB0HLsn-Tel3BYS
[Link 2]: http://blog.csdn.net/magicianofcodes/article/details/52966074
[20161030113020575]: /images/20220715/2c8b25e9e4d4442a9058424700cc2bd2.png
[20161030113151479]: /images/20220715/2cba725e21be46d18e767d919c94d3d5.png