Цикл по числам

Так что это вопрос, который дается.

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

Решение

При незначительном изменении индексов у вас возникла проблема с Иосифом. В традиционной формулировке человек 1 убивает человека 2, 3 убивает 4 и т. Д. Чтобы преобразовать в эту форму, убейте человека 1, когда ваша проблема констатирует, а затем перенумеруйте людей 2-100, вычитая 1, давая людям 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 указывает на каждого kth человека, уходящего.

Результат здесь 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

Источник
Другие вопросы по тегам