javascript - 遍历数字

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

随着索引的微小变化，您遇到了Josephus 问题。在传统的公式中，人 1 杀死人 2、3 人杀死 4 等。要转换为这种形式，如您的问题所述，杀死人 1，然后通过减去 1 重新编号 2-100，得到 1-99 人。

约瑟夫斯问题的一个很好的处理，包括它在公元 70-73 年犹太人起义中的起源，在 Concrete Mathematics，第 2 版中，Graham、Knuth 和 Patashnik，第 1.3 节。维基百科和 Wolfram MathWorld 都有关于这个问题的文章，维基百科甚至包括约瑟夫斯在犹太 war 中的原始描述。

这本书给出了一个稍微复杂的递归解决方案，以及一个更简单的算法。如果人数是 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 人排在第一位。所以他活了下来。

还应该指出，添加新的索引变量和拼接会导致程序员出错。由于只需要从前面移除，在后面添加，所以使用数组的基本方法。