所以这是给出的问题。
你在一个有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 CE的犹太人起义中的起源，是在 具体数学，第2版，Graham，Knuth和Patashnik，第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.
添加
找到原始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 是排在第一位的。所以他活了下来。
还应该指出，添加新的索引变量和拼接可能会导致程序员错误。由于您只需要从前面移除并添加到后面，因此请使用数组的基本方法。
在我看来答案是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]);
你在这里描述的是Josephus问题，可以使用动态编程解决：
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