JS-约瑟夫环

据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。 所以坐在哪个位置可以活下来呢?

OK。先报数~第一轮,报到3的人自杀了

var arr = [];
for(var i=1;i=<41;i++){
    arr.push(i);
}
var count = 0;
var out = 0;
for(var s=0,len=arr.length;s<len;s++){
    count++;
    if(count == 3){
        count = 0;
        arr.splice(s-out,1);
        out ++;
    }
}

这里有一个arr.splice(s-out,1),按直脑子来说,应该arr.splice(s,1).但splice返回的是被删除后的数组,所以再次splice时,需要把被删除的位给减去,于是 arr.splice(s-out,1);

这一轮for循环之后,第一轮报数结束,得到count,out,arr分别为:

arr:1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26,28,29,31,32,34,35,37,38,40,41;

count:2;

out:13;

数数数到了2,已经出局了13人,再数一个就是出局14人了。

所以又需要一个for遍历,结束遍历的条件是剩两个人。再次循环时,out属于定位专用,需要清0,count数数专用,得接着数,不能断,不能清0:

var arr = [];
for(var i=1;i=<41;i++){
    arr.push(i);
}
var count = 0;
while(arr.length>2){
    var out = 0;
    //遍历
    for(var s=0,len=arr.length;s<len;s++){
        count++;
        if(count == 3){
            count = 0;
            arr.splice(s-out,1);
            out ++;
        }
    }
}

那所有人出局后,剩下最后2人的数组,就是答案了,最后是arr[16,31],坐在16和31位能活。

故事的结局是,joseph坐在第31位,朋友坐在16位,活下来了~

以上方法实际上应用时,会有一个小bug,预留下次~

发表评论

电子邮件地址不会被公开。 必填项已用*标注