循环数字

所以这是给出的问题。

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

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

对约瑟夫斯问题的良好处理，包括其起源于公元70-73年的犹太起义，见格雷厄姆，高德纳和帕塔什尼克的《具体数学》第2版，第1.3节。维基百科和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.

添加

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

如果有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人排在第一位。所以他活了下来。

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

在我看来

，答案是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]);

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

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;
}

你不需要迭代来找到结果，有一个公式可以用来获得最终的椅子：

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

添加

相关内容

最新更新

热门标签：