约瑟夫问题

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，数到第九个人就将他扔入大海。该人后面的人从1开始重新报数，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

思路
1. 先建立一个类，有 id 和 isRemove

class Person {      int id;      boolean isRemove;        public Person(int id, boolean isRemove) {          this.id = id;          this.isRemove = isRemove;      }        public boolean isRemove() {          return isRemove;      }        public void setRemove(boolean isRemove) {          this.isRemove = isRemove;      }  }

2.

class Circle {      private ArrayList<Person> circle = new ArrayList<Person>();        private int amount; // 一共多少人        Circle(int amount) {          this.amount = amount;          for (int i = 0; i < amount; i++) {              Person p = new Person(i + 1, false);              circle.add(p);          }      }        /** * * @param index * 最开始扔人的位置，比如第9人 * @param total * 共需要扔几次 */      public void getIndex(int index, int total) {            // 起始位置          int currentIndex = -1;            for (int t = 0; t < total; t++) {              int notRemove = 0;                //本来是notRemove != 9，写死不好              while (notRemove != index) {                  currentIndex++;                  // 或者用 currentIndex % amount 解决                  if (currentIndex == amount) {                      currentIndex = 0;                  }                  if (!circle.get(currentIndex).isRemove) {                      notRemove++;                  }              }                // 将扔的人设为 true              Person p = circle.get(currentIndex);              p.setRemove(true);              circle.set(currentIndex, p);                System.out.printf("第 %-2d 次仍的人id是%4d\n", t + 1, p.id);            }        }    }  

代码建立一个容器来保存各个人，主要就是不移除这个人，而是把他状态设为setRemove(true)，好处这样容器的大小保持不变。如果删掉这样人，容器大小每次减1，算起来麻烦

if (currentIndex == amount) { currentIndex = 0; }

本来是用 currentIndex % amount 实现的，不过本代码都是+1，肯定会有 == amount的情况，用置为0更好

结果

第 1  次仍的人id是   9  第 2  次仍的人id是  18  第 3  次仍的人id是  27  第 4  次仍的人id是   6  第 5  次仍的人id是  16  第 6  次仍的人id是  26  第 7  次仍的人id是   7  第 8  次仍的人id是  19  第 9  次仍的人id是  30  第 10 次仍的人id是  12  第 11 次仍的人id是  24  第 12 次仍的人id是   8  第 13 次仍的人id是  22  第 14 次仍的人id是   5  第 15 次仍的人id是  23  

优化

也可以用数组实现，下标和 boolean 正好模拟上面的 Person 类

static void other() {      boolean[] usaJapa = new boolean[30];      // 用类库初始化      Arrays.fill(usaJapa, true);        int leftCount = usaJapa.length;        int countNum = 0;      int index = 0;      int i = 0;      while (leftCount > 15) {          if (usaJapa[index]) {              countNum++;          }            if (countNum == 9) {              countNum = 0;              usaJapa[index] = false;              leftCount--;              System.out.printf("第 %-2d 次仍的人id是%4d\n", ++i, index + 1);            }            index++;          if (index == usaJapa.length) {              index = 0;          }      }    }

用链表实现，remove 其中的数据

class Circle {      private LinkedList<Person> circle = new LinkedList<Person>();        private int amount; // 一共多少人        Circle(int amount) {          this.amount = amount;          for (int i = 0; i < amount; i++) {              Person p = new Person(i + 1, false);              circle.add(p);          }      }        public void othergetIndex(int mark, int total) {          // remain 是剩下的人数，total 是需要删除的人数          int remain = amount;          int count = 0;          int current = 0;          int i = 0;          while (remain > amount - total) {              count++;              // 注意这人如果达到 mark，比如第9个人              // 删掉第9个人后，再删第9个人，就是删原来的第10个人              if (count == mark) {                  // remove 返回的是删除的 Person                  Person p = circle.remove(current);                  System.out.printf("第 %-2d 次仍的人id是%4d\n", ++i, p.id);                  count = 0;                  remain--;              } else {                  current++;              }              if (current == amount - i) {                  current = 0;              }            }        }  }

用 LinkedList 删除操作更快，

Person p = circle.remove(current);
remove 返回删除的元素

LinkedList<Integer> testList = new LinkedList<Integer>();  for (int i = 0; i < 10; i++) {          testList.add(i);  }  for (int i = 0; i < 5; i++) {      System.out.println(testList.remove(3));  }   /** * 3 * 4 * 5 * 6 * 7 */    

这段代码的输出可以看出，删除了第3个元素，后面元素往前移动