遍历数字 [英] Looping over numbers
问题描述
这就是这个问题.
您所在的房间有100张椅子.椅子按从1到100的顺序编号.
You are in a room with a circle of 100 chairs. The chairs are numbered sequentially from 1 to 100.
在某个时间点，将要求1号椅子上的人离开. 2号椅子上的人将被跳过，3号椅子上的人将被要求离开.跳过一个人然后要求下一个人离开的这种模式将继续绕圈，直到幸存者剩下一个人为止.
At some point in time, the person in chair #1 will be asked to leave. The person in chair #2 will be skipped, and the person in chair #3 will be asked to leave. This pattern of skipping one person and asking the next to leave will keep going around the circle until there is one person left, the survivor.
这是我想出的答案.我相信这是正确的答案，我在纸上也做过大约10次，每次都提出74次. 这是一个技巧问题吗?因为我不确定从这里做什么.
And this is the answer I came up with. I believe this is the right answer, I've done it on paper about 10 times as well and came up with 74 every time. Is this a trick question or something? Because I'm not sure what to do from here.
这是jsfiddle http://jsfiddle.net/cQUaH/
Here is the 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
推荐答案
索引稍有变化，您就会遇到 Josephus问题.在传统的公式中，人1杀死人2，3杀死4，依此类推.要转换为这种形式，请按问题说明杀死人1，然后通过减去1给人2-100重新编号，从而给人1-99.
With a minor change in indices, you have the Josephus problem. In the traditional formulation, person 1 kills person 2, 3 kills 4, etc. To convert to that form, kill off person 1, as your problem states, and then renumber people 2-100 by subtracting 1, giving people 1-99.
格雷厄姆(Graham)，克努斯(Knuth)和帕塔什尼克(Patashnik)在《具体数学》第二版中对约瑟夫斯问题进行了很好的处理，包括其起源于公元70-73年的犹太起义. 1.3节. Wikipedia和Wolfram MathWorld都有关于该问题的文章，Wikipedia甚至还包括Josephem在 The Jewish War 中的原始描述.
A good treatment of the Josephus problem, including an account of its origin in the Jewish Revolt of 70-73 CE, is in Concrete Mathematics, 2nd edition, by Graham, Knuth, and Patashnik, Section 1.3. Both Wikipedia and Wolfram MathWorld have articles on the problem, Wikipedia even includes the original description by Josephus in The Jewish War.
这本书给出了该解决方案的一个稍微复杂的递归，以及一个更简单的算法.如果人数是n，而n = 2^l + m其中l尽可能大，则答案是2m+1.因此，由于99 = 2^6 + 35，解决方案是2*35 + 1 = 71.但是您需要反转重新编号，所以真正的答案是72.
The book gives a mildly complicated recursion for the solution, and a simpler algorithm. If the number of people is n, and n = 2^l + m where l is as large as possible, then the answer is 2m+1. So, since 99 = 2^6 + 35, the solution is 2*35 + 1 = 71. But you need to reverse the renumbering, so the real answer is 72.
但是，对于您的编程问题，为什么不将其作为基本操作呢?删除圈子中的第一个人，然后将第二个人移到末尾.因此，使用[1,2,3,4,5]，您删除第一个获取的[2,3,4,5]，并将新的第一个元素移动到最后获取的[3,4,5,2].
As far as your programming problem, however, why don't you take as your basic operation Remove the first person in the circle and move the second person to the end. So, with 5 people, [1,2,3,4,5], you remove the first getting [2,3,4,5]and moving the new first element to the 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.
已添加
找到原始约瑟夫斯问题的结果的简单方法是:
Added
The easy way to find that result for the original Josephus problem is to see that:
如果有2^l个人，那么在第一遍中，所有偶数个人都被杀死，因此第一个人仍然活着.
If there are 2^l people, then in the first pass all the even-numbered people are killed, so the first person remains alive.
1 2 3 4 5 6 7 8
X X X X
现在有2^(l - 1)个人.同样，第一人称幸存:
Now there are 2^(l - 1) people. Again, the first person survives:
1 2 3 4 5 6 7 8
X X X X
X X
重复该过程；每个通行证中第一个幸存者幸存，最后一个幸存者也幸存.
Repeat the process; the first person survives each pass, and so is the last survivor.
现在，假设还有m个额外的人带有m < 2^l.在这里，l = 3和m = 5.杀死第一个m人死亡.
Now, suppose there are m extra people with m < 2^l. Here, l = 3 and m = 5. Kill the first m people to die.
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个人是第一排.这样他就生存了.
Now, there are 2^l people left, and person 2 m + 1 = 11 is the first in line. So he survives.
还应该指出，添加新的索引变量并进行拼接会导致程序员错误.由于您只需要从前面移开并添加到后面，所以请使用数组的基本方法.
One should also point out that adding a new index variable and splicing can lead to programmer error. Since you only need to remove from the front and add to the back, use the basic methods of arrays.
这篇关于遍历数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
