循环数字

Question

所以这是给出的问题.

你在一个有100个椅子的房间里.椅子按顺序从1到100编号.

在某个时间点,#1椅子上的人将被要求离开.将跳过椅子#2中的人,并且将要求椅子#3中的人离开.这种跳过一个人并要求下一个人离开的模式将继续绕着圆圈走,直到有一个人离开,幸存者.

这就是我提出的答案.我相信这是正确的答案,我在纸上做了大约10次,每次都得到74.这是一个棘手的问题还是什么？因为我不知道该怎么做.

这是jsfiddle http://jsfiddle.net/cQUaH/

var console = {
    log : function(s) {
        document.body.innerHTML += s + "<br>";
    }
};

var chairArr = [];
for (var i = 1; i <= 100; i++){
    chairArr.push(i);
}

var j = 2;
while(chairArr.length > 1) {
    console.log('removing ' + chairArr[j]);
    chairArr.splice(j, 1);
    j++;
    if(j >= chairArr.length) {
       console.log('--- Finished pass');
       console.log('--- Array state:');
       console.log(chairArr);
       j = (j == chairArr.length) ? 0 : 1;   
    } 
}
console.log('--- Final result: ' + chairArr); 
//result 74

Answer 1

随着指数的微小变化,你有约瑟夫斯问题.在传统的公式中,人1杀人2,3杀4等.要转换为该形式,杀掉人1,如你的问题所述,然后通过减去1给人2-100,给人1-99.

对约瑟夫斯问题的一个很好的处理,包括它在70-73 CE的犹太人起义中的起源,在Graham,Knuth和Patashnik的第1.3节的具体数学第2版中.维基百科和Wolfram MathWorld都有关于这个问题的文章,维基百科甚至包括约瑟夫斯在犹太战争中的原始描述.

本书为解决方案提供了一个稍微复杂的递归,以及一个更简单的算法.如果人数是n,并且n = 2^l + m在哪里l尽可能大,那么答案是2m+1.所以,因为99 = 2^6 + 35,解决方案是2*35 + 1 = 71.但是你需要反转重新编号,所以真正的答案是72.

然而,就你的编程问题而言,为什么不把你作为你的基本操作取消圈中的第一个人并将第二个人移到最后. 所以,对于5人们来说[1,2,3,4,5],你删除了第一个获取[2,3,4,5]并将新的第一个元素移动到最后[3,4,5,2].

var killAndRotate = function(array) { // say [1,2,3,4,5]
    var dead    = array.shift(),      // dead    = 1, array = [2,3,4,5]
        skipped = array.shift();      // skipped = 2, array = [3,4,5]
    array.push(skipped);              //              array = [3,4,5,2]
}

然后主循环变为:

while (chairArray.length > 1) {
    killAndRotate(chairArray);
}
alert(chairArray[0]); // or console.log, or return.
// In turn, array is:
// [1,2,3,4,5]
// [3,4,5,2]
// [5,2,4]
// [4,2]
// [2] and we alert, log, or return 2.

添加

找到原始Josephus问题的简单方法是看到:

如果2^l有人,那么在第一关中,所有偶数人都被杀死,所以第一个人还活着.

1 2 3 4 5 6 7 8

  X   X   X   X

现在2^(l - 1)有人.再次,第一个人幸存下来:

1 2 3 4 5 6 7 8

  X   X   X   X

    X       X

重复这个过程; 第一个人每次通过幸存者,最后一个幸存者也是如此.

现在,假设有m更多的人m < 2^l.在这里,l = 3和m = 5.杀死第一批m人.

1 2 3 4 5 6 7 8 9 10 11 12 13

  X   X   X   X    X  Y

现在,2^l有人离开了,人2 m + 1 = 11是排在第一位的人.所以他活了下来.

还应该指出,添加新的索引变量和拼接可能会导致程序员错误.由于您只需要从前面删除并添加到后面,因此请使用数组的基本方法.