Зацикливание по номерам

Итак, это вопрос, который задан.

Вы находитесь в комнате с кругом из 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

При незначительном изменении индексов у вас есть проблема Джозефуса. В традиционной формулировке человек 1 убивает человека 2, 3 убивает 4 и т.д. Чтобы преобразовать в эту форму, убейте человека 1, как заявляет ваша проблема, а затем перенумеруйте людей 2-100 путем вычитания 1, давая людям 1-99.

Хорошее отношение к проблеме Иосифа Флавия, в том числе рассказ о его происхождении в еврейском восстании 70-73 года н.э., содержится в разделе "Бетонная математика", второе издание, глэм, Кнут и Паташник, раздел 1.3. В Wikipedia и Wolfram MathWorld есть статьи о проблеме, Wikipedia даже включает в себя оригинальное описание Иосифа Флавия в еврейской войне.

Книга дает слегка сложную рекурсию для решения и более простой алгоритм. Если число людей 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 - первый в строке. Так он выживает.

Следует также отметить, что добавление новой индексной переменной и сплайсинга может привести к ошибке программиста. Поскольку вам нужно только удалить с фронта и добавить обратно, используйте основные методы массивов.

Ответ 2

Что вы описали здесь, это проблема Иосифа и может быть решена с помощью динамического программирования:

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

alert(josephus(100, 2));

Источник: Wikipedia

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

Ответ 3

Мне кажется, что ответ 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]);