Мы выживем!

В чем проблема Иосифа Флавия?

В информатике и математике проблема Иосифа Флавия является теоретической проблемой.

Ниже приводится постановка проблемы:

There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle.

Задача состоит в том, чтобы выбрать место в начальном круге, чтобы вы остались последними и выжили.

Происхождение истории

В яме с Иосифом и его друзьями спрятано 9 евреев. 9 евреев решили умереть, а не быть пойманными врагом, поэтому они решили, что методом самоубийства 11 человек выстраиваются в круг, и первое лицо сообщает число. После того, как каждое число сообщается третьему лицу, этот человек должен покончить жизнь самоубийством. Затем считайте еще раз, начиная со следующего, пока все не кончат жизнь самоубийством.
Но Иосиф и его друзья не хотели подчиняться. Иосиф попросил своих друзей притвориться повиновением и устроил друзей сам с собой. На 2-й и 7-й позициях они избежали этой смертельной игры.

Как мы решим это на JavaScript?

В общем, классическая задача Иосифа Флавия имеет два параметра: N и K. Формируется круг из N человек, и последовательно для исключения выбирается каждый K-й человек. По мере того, как людей убивают, круг сужается, и цель состоит в том, чтобы определить последнюю оставшуюся позицию.

Мы можем решить проблему Иосифа Флавия для набора из N элементов, используя массив. Массив рассматривается как кольцо.

Сначала мы определяем массив позиций - m (N элементов), инициализируем значение 0.

var man = new Array()
    for (var i = 0; i < N; i++)
        man[i] = 0

Далее определяем положение убитого - значение переменной pos.

do {
    pos = (pos + 1) % N // Ring
    if (man[pos] == 0)
        i++
    if (i == K) {
        i = 0
        break
    }
} while (true)

Затем обновляем убитого в массиве m и переходим к следующему ходу.

man[pos] = count
count++

Продолжаем цикл, пока не дойдем до N. Наконец, вот наше полное решение.

const joseph = function (N, M) {
    var man = new Array()
    for (var i = 0; i < N; i++)
        man[i] = 0
    var count = 1
    var i = 0, pos = - 1
    while (count <= N) {
        do {
            pos = (pos + 1) % N // Ring
            if (man[pos] == 0)
                i++
            if (i == K) {
                i = 0
                break
            }
        } while (true)
        man[pos] = count
        count++
    }
    return man
}

Попробуйте протестировать это решение.

var game = Joseph (11, 3)
<< [ 4, 10, 1, 7, 5, 2, 11, 9, 3, 6, 8 ]

При N = 20, M = 3. На 13-й или 20-й позиции вы избежите этой смертельной игры.

var game = Joseph (20, 3)
[ 7, 18, 1, 12, 8, 2, 15, 17, 3, 9, 13, 4, 19, 10, 5, 16, 14, 6, 11, 20 ]

Легко, правда?

Спасибо, что прочитали 😘, до свидания, и не забудьте 👏 до 50 раз и подпишитесь!