количество сетбит в числе и игра, основанная на сетбитах
Я пытался эту проблему на биты манипуляций пришел через это:
Красота числа — это число установленных битов в этом числе. A и B начинают играть в игру, где на доске написано число N, а игрок, чей ход должен двигаться, подходит к доске и записывает новое число N-K, где k<= N и красота K равна 1. Также важно, чтобы красота N-K была равна красоте N.
Последний игрок, успешно завершивший свой ход, выигрывает игру.
Они оба играют в игру оптимально.
Постскриптум Я не ищу код здесь. Я хочу знать, как подойти к этому?
Решение
Это типичная проблема теории игр. Игра игроков оптимально означает, что любой игрок сделает ход таким образом, чтобы он максимально увеличил свои шансы на выигрыш (принимая во внимание, что, когда у игрока 2 есть шанс, он также будет готов сделать то же самое).
Теперь давайте посмотрим, какие ходы разрешены:
При необходимости красота номера должна оставаться неизменной, а k должна иметь красоту 1 то есть установлен только 1 бит (например, 00000100)
Для дальнейшей иллюстрации предположим, что у нас есть только 8-битное число.
Если вы внимательно посмотрите, для красоты N чтобы остаться таким же, бит установлен в k находится в (одном из) индексе, по которому N имеет 0 а также 1 находится слева от него. Я возьму пример:
Скажем N является 01010001, теперь к может быть 00100000, 00001000, Если ты видишь N-k красота остается такой же. После операции вы заметите, что 1 движется вправо и, следовательно, 0 движется влево. Например, когда N=01010001 а также k=00100000 (N-k) = 00110001,
Также конечная позиция игры будет такой, что все 0's слева и все 1's направо (00000111). Вы можете посчитать количество возможных ходов, учитывая число N, Если это нечетно, то игрок, стартующий выигрывает, иначе проигрывает.
Теперь подсчитать количество таких ходов — простая задача перечисления.
Другие решения
Других решений пока нет …