11

所以这是给出的问题。

你在一个有 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
4

4 回答 4

6

随着指数的微小变化，您就会遇到约瑟夫斯问题。在传统的公式中，人 1 杀死人 2，3 杀死人 4，依此类推。要转换为该形式，请杀死人 1，如您的问题所述，然后通过减去 1 来重新编号人 2-100，得到人 1-99。

约瑟夫斯问题的一个很好的处理方法，包括其起源于公元 70-73 年的犹太人起义的说明，见 Graham、Knuth 和 Patashnik 所著的《具体数学》第 2 版，第 1.3 节。维基百科和 Wolfram MathWorld 都有关于这个问题的文章，维基百科甚至包括约瑟夫斯在犹太战争中的原始描述。

这本书给出了一个稍微复杂的递归解决方案，以及一个更简单的算法。如果人数是n，并且n = 2^l + m哪里l尽可能多，那么答案是2m+1。所以，既然99 = 2^6 + 35，解决方案是2*35 + 1 = 71。但是你需要颠倒重新编号，所以真正的答案是72.

但是，就你的编程问题而言，为什么不把你的基本操作去掉圈内的第一个人，把第二个人移到最后。 因此，对于5people，[1,2,3,4,5]您删除第一个 getting[2,3,4,5]并将新的 first 元素移动到 end getting [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.

添加

找到原始约瑟夫斯问题的结果的简单方法是看到：

如果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是第一个排队的。所以他活下来了。

还应该指出，添加新的索引变量和拼接会导致程序员错误。既然只需要从前面去掉，后面加上，就用数组的基本方法。

于 2013-09-07T02:28:26.703 回答
4

在我看来答案是 72。当您意识到可以跳过它们而不是删除数字时，代码变得非常简短和直接。

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

for (i = 1; i < chairArr.length-2; i = i + 2)
    chairArr.push(chairArr[i]);

console.log('--- Final result: ' + chairArr[i]);
于 2013-09-07T02:44:02.917 回答
3

您在这里描述的是约瑟夫斯问题，可以使用动态规划来解决：

function josephus(n, k) 
{ 
    if (n == 1) { 
        return 1; 
    } else { 
        return ((josephus(n-1, k) + k - 1) % n) + 1; 
    }
}

alert(josephus(100, 2));

资料来源：维基百科

n表示椅子的数量，表示k每第 k 个人离开。

这里的结果是 73。

更新

不幸的是，我没有正确阅读问题。上面的代码解决了一个稍微不同的问题；不是在第一轮中杀死第一个人，而是杀死第二个人。成为幸存者取决于细节:)

解决你的代码问题相当简单，在第一轮从第一个人而不是第三个人开始。

var chairArr = [];

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

var j = 0;
while (chairArr.length > 1) {
    chairArr.splice(j, 1);
    j = (j + 1) % n;
}
于 2013-09-07T02:25:38.983 回答
0

您不需要迭代即可找到结果，有一个公式可用于获得最终椅子：

function findChair (input) {
  return (input - Math.pow(2, Math.floor(Math.log2(input)))) * 2 || (input === 1 ? 0 : input)
}

而对于原来的约瑟夫斯问题，你可以杀死偶数，公式可以简化：

function findChair (input) {
  return (input - Math.pow(2, Math.floor(Math.log2(input)))) * 2 + 1
}

原始问题的最酷之处在于您可以使用二进制文件。例如：

100 = 1100100

取第一个“1”并将其放在最后一个：

1001001 = 73

于 2018-09-11T14:02:57.513 回答