首页 > 代码库 > 约瑟夫环 --- 面向对象 --- java代码
约瑟夫环 --- 面向对象 --- java代码
约瑟夫环 的 面向对象 解法
罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
如有疑问请参考：http://blog.fishc.com/1959.html
实现代码如下：
程序的入口
/Josephus/src/com/kodoyang/Josephus/Demo.java
package com.kodoyang.Josephus;
/**
* ---------------------------------------------------------------------
*
* 在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，
* 39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，
* 41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，
* 然后再由下一个重新报数，直到所有人都自杀身亡为止。
* 然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，
* 他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
* ----------------------------------------------------------------------
*
* 网站上有很多实现了，我提供一种面向对象的实现
* 把约瑟夫环看成一个正多边形，每个人占据顶点的位置
* ----------------------------------------------------------------------
*
* 程序的入口类
*
* @author yuki
*
*/
public class Demo {
// 程序的入口
public static void main(String[] args) {
// 一共41个人
final int N = 41;
// 新建一个具有41条边的正多边形
Ring r = new Ring(N);
// 记录当前生存的人数
int i = N;
// 生存人数为零就结束循环
while(i != 0){
// 调用环的报数方法，返回真说明有点死亡，返回假说明无点死亡
if( r.call() ){
// 打印当前存活人数
$("Survival : " + --i);
}
}
}
/**
* 打印语句的封装
* @param s
*/
private static void $(String s){
System.out.println("---------------------------" + s);
}
}
/Josephus/src/com/kodoyang/Josephus/Vertex.java
定义将要循环自杀的犹太人的类
package com.kodoyang.Josephus;
/**
* 构成环的顶点，它是可以不依赖于环独立存在的
*
* @author yuki
*
*/
public class Vertex {
// 唯一标识，会被构造方法初始化
private int id;
// 当前点所处的状态
private boolean dead;
/**
* 构造方法
* @param id
*/
public Vertex(int id){
this.id = id;
}
/**
* 点被环调用了
* @param num 环让它报的数
* @return
*/
public void act(int num) {
// 报数
System.out.println("id = " + id + ", num = " + num);
// 如果报的数是2
if(num == 2){
// 当前点死亡
System.out.println("......I am dead......");
// 设置当前点的死亡状态
dead = true;
}
}
/**
* 返回当前点的死亡状态
* @return
*/
public boolean isDead() {
return dead;
}
} 
/Josephus/src/com/kodoyang/Josephus/Ring.java
定义犹太人轮流报数的环的类
package com.kodoyang.Josephus;
/**
* 这是一个报数的环，它由数组实现
* 在对象实例化的时候确定了点的个数，不在改变
*
* 它由一个个的点拼接而成
* pos用来记录当前点的位置，num用来记录当前报出的数字
*
* @author yuki
*
*/
public class Ring {
// 它由一个个的点拼接而成
private Vertex[] vers;
// 记录当前点的位置
private int pos;
// 记录当前报出的数字
private int num;
/**
* 构造方法
* @param n 环拥有的节点数
*/
public Ring(int n){
// 创建构成环的点的数组
vers = new Vertex[n];
// 初始化点的数组
for(int i = 0; i < vers.length; ++i){
// 点的构造方法必须接受一个表示点的id的参数
Vertex ver = new Vertex(i);
// 把点初始化给数组的第i个位置
vers[i] = ver;
}
// 构造完毕并不能让他马上进入报数状态，所以设报数值为-1
num = -1;
}
/**
* 报数
* @return 返回true表示有点死亡，否则没有点死亡
*/
public boolean call(){
// 执行，如果当前的位置不在死亡状态就跳出循环
do {
// 获得下一个位置，如果下一个位置是末尾就设为0， 其它情况加1
pos = pos == vers.length - 1 ? 0 : pos + 1;
} while( vers[pos].isDead() );
// 获得下一个要报的数，如果下一个位置是2就设为0， 其它情况加1
num = num == 2 ? 0 : num + 1;
// 让点报数
vers[pos].act(num);
// 当点报出的数为2时，说明报数的点死亡了
return num == 2;
}
} 
运行结果如下：
id = 1, num = 0 id = 2, num = 1 id = 3, num = 2 ......I am dead...... ---------------------------Survival : 40 id = 4, num = 0 id = 5, num = 1 id = 6, num = 2 ......I am dead...... ---------------------------Survival : 39 id = 7, num = 0 id = 8, num = 1 id = 9, num = 2 ......I am dead...... ---------------------------Survival : 38 id = 10, num = 0 id = 11, num = 1 id = 12, num = 2 ......I am dead...... ---------------------------Survival : 37 id = 13, num = 0 id = 14, num = 1 id = 15, num = 2 ......I am dead...... ---------------------------Survival : 36 id = 16, num = 0 id = 17, num = 1 id = 18, num = 2 ......I am dead...... ---------------------------Survival : 35 id = 19, num = 0 id = 20, num = 1 id = 21, num = 2 ......I am dead...... ---------------------------Survival : 34 id = 22, num = 0 id = 23, num = 1 id = 24, num = 2 ......I am dead...... ---------------------------Survival : 33 id = 25, num = 0 id = 26, num = 1 id = 27, num = 2 ......I am dead...... ---------------------------Survival : 32 id = 28, num = 0 id = 29, num = 1 id = 30, num = 2 ......I am dead...... ---------------------------Survival : 31 id = 31, num = 0 id = 32, num = 1 id = 33, num = 2 ......I am dead...... ---------------------------Survival : 30 id = 34, num = 0 id = 35, num = 1 id = 36, num = 2 ......I am dead...... ---------------------------Survival : 29 id = 37, num = 0 id = 38, num = 1 id = 39, num = 2 ......I am dead...... ---------------------------Survival : 28 id = 40, num = 0 id = 0, num = 1 id = 1, num = 2 ......I am dead...... ---------------------------Survival : 27 id = 2, num = 0 id = 4, num = 1 id = 5, num = 2 ......I am dead...... ---------------------------Survival : 26 id = 7, num = 0 id = 8, num = 1 id = 10, num = 2 ......I am dead...... ---------------------------Survival : 25 id = 11, num = 0 id = 13, num = 1 id = 14, num = 2 ......I am dead...... ---------------------------Survival : 24 id = 16, num = 0 id = 17, num = 1 id = 19, num = 2 ......I am dead...... ---------------------------Survival : 23 id = 20, num = 0 id = 22, num = 1 id = 23, num = 2 ......I am dead...... ---------------------------Survival : 22 id = 25, num = 0 id = 26, num = 1 id = 28, num = 2 ......I am dead...... ---------------------------Survival : 21 id = 29, num = 0 id = 31, num = 1 id = 32, num = 2 ......I am dead...... ---------------------------Survival : 20 id = 34, num = 0 id = 35, num = 1 id = 37, num = 2 ......I am dead...... ---------------------------Survival : 19 id = 38, num = 0 id = 40, num = 1 id = 0, num = 2 ......I am dead...... ---------------------------Survival : 18 id = 2, num = 0 id = 4, num = 1 id = 7, num = 2 ......I am dead...... ---------------------------Survival : 17 id = 8, num = 0 id = 11, num = 1 id = 13, num = 2 ......I am dead...... ---------------------------Survival : 16 id = 16, num = 0 id = 17, num = 1 id = 20, num = 2 ......I am dead...... ---------------------------Survival : 15 id = 22, num = 0 id = 25, num = 1 id = 26, num = 2 ......I am dead...... ---------------------------Survival : 14 id = 29, num = 0 id = 31, num = 1 id = 34, num = 2 ......I am dead...... ---------------------------Survival : 13 id = 35, num = 0 id = 38, num = 1 id = 40, num = 2 ......I am dead...... ---------------------------Survival : 12 id = 2, num = 0 id = 4, num = 1 id = 8, num = 2 ......I am dead...... ---------------------------Survival : 11 id = 11, num = 0 id = 16, num = 1 id = 17, num = 2 ......I am dead...... ---------------------------Survival : 10 id = 22, num = 0 id = 25, num = 1 id = 29, num = 2 ......I am dead...... ---------------------------Survival : 9 id = 31, num = 0 id = 35, num = 1 id = 38, num = 2 ......I am dead...... ---------------------------Survival : 8 id = 2, num = 0 id = 4, num = 1 id = 11, num = 2 ......I am dead...... ---------------------------Survival : 7 id = 16, num = 0 id = 22, num = 1 id = 25, num = 2 ......I am dead...... ---------------------------Survival : 6 id = 31, num = 0 id = 35, num = 1 id = 2, num = 2 ......I am dead...... ---------------------------Survival : 5 id = 4, num = 0 id = 16, num = 1 id = 22, num = 2 ......I am dead...... ---------------------------Survival : 4 id = 31, num = 0 id = 35, num = 1 id = 4, num = 2 ......I am dead...... ---------------------------Survival : 3 id = 16, num = 0 id = 31, num = 1 id = 35, num = 2 ......I am dead...... ---------------------------Survival : 2 id = 16, num = 0 id = 31, num = 1 id = 16, num = 2 ......I am dead...... ---------------------------Survival : 1 id = 31, num = 0 id = 31, num = 1 id = 31, num = 2 ......I am dead...... ---------------------------Survival : 0
更多好文请关注：http://www.cnblogs.com/kodoyang/
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。