黑马程序员技术交流社区

标题: 约瑟夫环 [打印本页]
作者: yzqiong5566    时间: 2012-11-25 00:18
标题: 约瑟夫环
本帖最后由 yzqiong5566 于 2012-11-25 09:12 编辑

著名的约瑟夫环问题详解
问题概述：
　　已知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的那个人又出列；依次规律重复下去，问：最后一个出列的人原来的编号是多少？
下面用2种解决方法通过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=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==true) {
              System.out.println(i);
           }
       }
    }
}



方法二：用面向对象的思想来解决问题
在同一个包里新建了3个类，代码如下：

package wish25MethodNO2;

public class Person {//定义人的类
    public int id;//编号
    public Person leftPerson;//左边的人
    public Person rightPerson;//右边的人
}

package wish25MethodNO2;
public class PersonCircle {//定义人形成的一个圈的类  
    private int number;//用于统计圈里的人数（默认为0）
    private Person firstPerson;//用于标示圈里的第一个人
    private Person lastPerson;//用于标示圈里的最后一个人

    public int getNumber() {//得到圈里的人数
       return number;
    }
    public Person getFirstPerson() {//得到圈里位置为第一的那人
       return firstPerson;
    }


    public PersonCircle(int number) {//定义一生成number个人的圈的构造方法
       for(int i=0; i<number; i++) {
           addPerson();
       }
    }  

    public void addPerson() {//往圈里加人，即形成一个多大的圈
       Person person = new Person();//先new一个人出来以便往圈里加
       person.id = number;//给加进圈里的人上一编号
       if(number<=0) //如果圈里没人时（加进去的那人便充当了所有角色）
       {
           firstPerson = person;
           lastPerson = person;
           person.leftPerson = person;
           person.rightPerson = person;

       } else {//如果有人时   （看下图：1-1）     
           lastPerson.rightPerson = person;//原来最后那人右边的人变成了刚加进来的person这人
           firstPerson.leftPerson = person;//原来第一个人左边的人变成了刚加进来的person这人
           person.leftPerson = lastPerson;//加进来的person这人左边是原来的最后那人
           person.rightPerson = firstPerson;//加进来的person这人右边是原来的第一个那人
           lastPerson = person;//最后，新加进来的person这人变成了圈里的最后一个人
       }
       number++;//圈里人数增加
    }

    public void deletePerson(Person person) {//从圈里删除人
       if(number <= 0) {//如果没人，就退出
           return;
           //System.exit(0);
       } else if(number == 1) {//如果就一个人，删除后都为空
           firstPerson = lastPerson = null;
           person.leftPerson = person.rightPerson = null;
       } else {
           person.leftPerson.rightPerson = person.rightPerson;
           person.rightPerson.leftPerson = person.leftPerson;
           if(person == firstPerson) {//如果删除那人刚好是第一个人
              firstPerson = person.rightPerson;//删除那人person的右边的人往前补上成为新的firstPerson
           } else if(person == lastPerson) {//如果删除那人刚好是最后那个人
              lastPerson = person.leftPerson;//删除那人person的左边的人便补上成为新的lastPerson
           }
       }
       number--;//删除后人数减少
    }
}
package wish25MethodNO2;
public class JosephusQuestionTestDemo {
    public static void main(String[] args) {      
       PersonCircle per = new PersonCircle(600);//生成一个600人的圈
       int count = 0;//定义一个计数器（统计圈里人报的数(1,2,3)，当遇到3便重新置为0），用于圈里人的报数
       Person p = per.getFirstPerson();//用圈里的第一个人初始化，开始报数
       while(per.getNumber()>1) {//当圈里人数大于1时循环筛选
           count++;//计数器自加1
           if(count == 3) {//如果报到3这个数（就出列）
              count = 0;//计数器归0
              per.deletePerson(p);//报到3的人被删除
           }
           p = p.rightPerson;//删除人的右边的人重新开始报数
       }
       System.out.println("最后一个出列的人原来的编号是："+p.id);//最后留下的那人就是要找的
    }
}



作者: 杨千里    时间: 2012-11-25 15:10
哥们 你刚进来么？可以看出你是非常有实力的，有些帖子该加分，有些不该加，请联系你发帖所在的板块版主
我是javaee+云区的小小版主，该板块内我有权利审核任一个帖子，如果你在其它板块发帖或者提问，请联系其他版块 所在的版主

例如：你在 javaee+android区发帖，你认为应该加分而没有给你加，请联系该板块版主，如对加分不满，可以向官方管理员提出异议，谢谢合作
作者: yzqiong5566    时间: 2012-11-25 15:15
杨千里 发表于 2012-11-25 15:10
哥们 你刚进来么？可以看出你是非常有实力的，有些帖子该加分，有些不该加，请联系你发帖所在的板块版主
我 ...

是刚进来的，才完成了基础测试。好的，太谢谢您了。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2