约瑟夫环 的 面向对象 解法
罗马人占领乔塔帕特后，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 = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival : id = , num = id = , num = id = , num = ......I am dead...... ---------------------------Survival :
更多好文请关注：http://www.cnblogs.com/kodoyang/