Josephus问题之Java乱弹篇
女儿生病住了几天医院，在我为女儿担心的同时也使我深深的感受到医疗产业化的伟大之处，在它一切向钱看的伟大精神指导之下，医生的工作积极性有了空前的提高，“开放思想，积极创收”成为各个医院的热门话题。我想大家也都发现了这种情况，那就是“没病当成有病看的多了，小病当成大病看的多了，大病当成重病看的多了”。为了让大家能看的起病，医疗产业化是不是到了该让它离开，还医院一f份圣洁的时候呢。
呵呵，说到离开，不禁让我想到编程中的一个算法问题：
说有10个小孩围成一圈做游戏，从第3个小孩起，顺时针方向数，每数到第5个小孩时，该小孩离开。小孩不断离开，圈子不断缩小，最后剩下的一个小孩便是胜利者。大家可能会说，这不就是Josephus问题吗。
不错，这就是Josephus问题。那大家知道这个问题的典故吗？
Josephus问题是建立在历史学家Joseph ben Matthias（成为Josephus）的一个报告的基础之上，该报告讲述了他和40个士兵在公元67年被罗马军队包围期间签定的一个自杀协定，Josephus建议每个人杀死他的邻居，他很聪明的使自己成为这些人中的最后一个，因此获得生还。呵呵，是不是觉得这个人很坏呢。
好了，说完这个典故，让我们来看看Josephus问题的具体算法实现吧。
public class Josephus {
public static void main(String args[])
{
int num = 10; //孩子总数
int interval = 5; //每次数interval个孩子，就让该孩子离开
int []child =new int[num+1]; //孩子树组
int []flag =new int[num+1]; //每个孩子是否在圈子的标志，1：在 0：不在
for(int i=1;i<=num;i++){
child[i]=i;
flag[i]=1; //开始每个孩子都在圈内
System.out.println("第"+i+"个孩子的名字："+child[i]);
}
int n = 0;
int i = 3; //从第几个孩子开始
int j = 1; //从1开始记数
boolean noEnd = true; //是否结束的标志
while(noEnd)
{
while(j<interval){
i =(i+1>num?1:i+1);
j+=flag[i];
}
flag[i]=0;
n++;
if(n==num){
noEnd = false;
System.out.println("第"+i+"个孩子最后胜利");
}
else{
System.out.println("第"+i+"个孩子离开");
j=0; //j达到interval时，从新开始记数
}
}
}
}
大家可以改变数字试一下，挺有意思的。查看执行结果，我总觉得这里面似乎有什么规律，不过我还暂时没总结出来，如果那位朋友能总结出来，希望能让大家知道。
最后，把下面这几句我编的东东送给大家就算作个结束礼物吧。
医院不是电影院，不是想看就能看。
医院不是福利院，不是想拿就能拿，
医院不是养老院，不是想养就能养。
医院不是国务院，不是想进就能进。
|
本类阅读TOP10