количество setbits в ряде и игра, основанная на setbits

Question

Я пытался эту проблему на манипуляции битами пришли через этот:

Красота числа является число установленных битов в том числе. A и B начинают играть в игру, где на борту есть номер N, игрок, чей ход должен двигаться, переходит на борт и записывает новый номер NK, где k < = N, а красота K равна 1. Это также важно что красота НК должна быть равна красоте Н. Последний игрок, успешно завершивший свой ход, выигрывает игру.

Они оба играют в игру оптимально.

P.S. Я не ищу код здесь. Я хочу знать, как подойти к этому?

Answer 1

Это типичная проблема теории игр. Игроки играют оптимально, означает, что любой игрок сделает ход таким, чтобы он максимизировал его шанс выиграть (учитывая, что, когда игрок 2 получает шанс, он также будет готов сделать то же самое).

Теперь в этом случае давайте посмотрим, какие ходы допускаются:.

По мере необходимости красоту ряда должны оставаться таким же и k должны иметь красоту 1т.е. только 1 набор битов (напр 00000100)

Для дополнительной иллюстрации предположим, что у нас есть только 8-битное число.

Если вы видите внимательно, за красоту N оставаться же, бит установлен в k находится в (один из) индекса, при котором N имеет 0 и 1 находится слева рядом с ним. Приведу пример:

Скажем, N - 01010001. сейчас k может быть 00100000, 00001000. Если вы видите N-k, красота остается такой же. После операции вы заметите, что 1 перемещается вправо и, следовательно, 0 перемещается влево. Например, когда N=01010001 и k=00100000(N-k) = 00110001.

Также конечная позиция игры будет такой, что все 0's находятся слева, а все 1's находятся справа (00000111). Вы можете подсчитать количество возможных ходов с учетом номера N. Если это нечетно, тогда игрок начинает выигрывать, иначе он проигрывает.

Теперь, чтобы подсчитать количество таких ходов, это простая проблема перечисления.