约瑟夫环

 

著名的约瑟夫环问题详解

问题概述：

　　已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
　　例如：n = 9, k = 1, m = 5
　　【解答】
　　出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。

　　下面将通过简单例子来实现约瑟夫环的一个具体问题(笔者尽量把问题简单化)：现在有600个人围成一个圈，从编号为0（假设每个人身上都有一个编号，600个人编号从0到599）的那人开始报数，数到3的人便出列，他的下一个人又从1开始报数，数到3的那个人又出列；依次规律重复下去，问：最后一个出列的人原来的编号是多少？

下面用3种解决方法通过eclipse-3.4.2(英文版)编写的代码如下：

方法一：用数组

package wish25MethodNO1;

public class JosephusQuestion {

    public static void main(String[] args) { 

       boolean[] bool = new boolean[600];//定义一个600人的布尔类型的数组用于标示所有人的状态，在圈里的都置为true否则为false

       for(int i = 0;i<bool.length;i++) {

           bool[i]=true;//开始时600人形成一个圈，都在圈里，初始化为true

       }

       int countArrayLength = bool.length;//定义一个整形的变量countArrayLength用来统计在圈里的人数

       int index = 0;//定义一个整形index用来记录在圈里人的编号，即数组的下标

       int count = 0;//定义一个计数器（统计圈里人报的数(1,2,3)，当遇到3便重新置为0），用于圈里人的报数

       while(countArrayLength>1) {//当圈里只有一个人的时候会停止循环

           if(bool[index]==true) {//圈里要有人才能开始报数

              count++;//计数器自加1

              if(count == 3) {//如果报到3这个数（就出列）

                  count = 0;//计数器归0

                  bool[index]=false;//报到3的人出列

                  countArrayLength--;//圈里的人数自减1

              }

           }         

           index++;//在圈里的人依次循环报数

           if(index == bool.length) {//当编号为数组长度时（应置为0，否则会报ArrayIndexOutOfBoundsException异常）

              index = 0;//置为0

           }

       }

       System.out.print("最后一个出列的人原来的编号是：");

       for(int i = 0;i<bool.length;i++) {//经过上面的筛除后，留下的便是要找的

           if(bool[i]==true) {

              System.out.println(i);

           }

       }

    }

}

 

 

方法二：用面向对象的思想来解决问题

在同一个包里新建了3个类，代码如下：（见下一篇）