本帖最后由 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);//最后留下的那人就是要找的 } }
| 
收藏
淘帖
踩
