Ссылка на Заголовок
292. Ним Игра
Анализ названия
Предположим, вы и ваши друзья играете в игру по сбору камней. Вы и ваши друзья по очереди берете 1-3 камня. Тот, кто получит последний камень, останется один. Первый раунд для вас, чтобы собрать камни. В то же время предположим, что вы и ваши друзья достаточно умны, чтобы каждый раз выбирать наилучшую стратегию.
Теперь дайте несколько камней, чтобы судить, сможете ли вы в конце концов выиграть.
размышляющий
Давайте начнем с меньшего количества камней.
Если есть 1-3 камня, потому что оговаривается, что именно вы должны начать, а также предполагается, что будет принята оптимальная стратегия, то вы можете выиграть. То есть другая сторона не уйдет 1 после того, как заберет камень
Предположим, что есть четыре камня. Возьми одну, и у тебя останется три. Они забирают их всех, Побеждают другую сторону . Ты берешь двоих, и у тебя останется двое. Они забирают их всех, Побеждают другую сторону 。 Возьми три, и у тебя останется один. Они забирают их всех, Побеждают другую сторону . То есть, вы-проигравший.
Предположим, что камней пять. Возьми одну, и у тебя останется четыре. Другая сторона берет одну, остальные три для вас, вы берете их все, вы выигрываете. Другая сторона берет два, оставшиеся два для вас, вы берете их все, вы выигрываете. Другая сторона берет 3, оставшаяся-для вас, вы берете все, вы выигрываете. Ты берешь два, и у тебя останется три. Они забирают их всех, Побеждают другую сторону 。 Возьми три, и у тебя останется два. Они берут их все, Выигрывают другую сторону . Поэтому вы решите взять одного в этом раунде, оставив четырех.
Предположим, что камней шесть. Возьми одну, и у тебя останется пять. Другая сторона берет одну и отдает вам оставшиеся четыре. Обратитесь к ситуации, когда в начале всего четыре, Выиграйте другую сторону 。 Другая сторона берет два, остальные три для вас, вы берете все, вы выигрываете. Другая сторона берет 3, остальные 2 для вас, вы берете их все, вы выигрываете. Ты берешь два, и у тебя останется четыре. Другая сторона берет одну, остальные три для вас, вы берете их все, вы выигрываете. Другая сторона берет два, оставшиеся два для вас, вы берете их все, вы выигрываете. Другая сторона берет 3, оставшаяся-для вас, вы берете все, вы выигрываете. Возьми три, и у тебя останется три. Они берут их все, Выигрывают с другой стороны . Поэтому вы решите взять два в этом раунде, оставив четыре.
Предположим, что камней семь. Возьми одну, и у тебя останется шесть. Другая сторона берет одну и отдает вам оставшиеся пять. Обратитесь к ситуации, когда в начале их всего пять. Ты победил. Другая сторона берет два и оставляет четыре для вас, Выигрывает другая сторона 。 Другая сторона берет три, остальные три для вас, вы берете все, вы выигрываете. Ты берешь два, и у тебя останется пять. Другая сторона берет одну и оставляет вам четыре, Выигрывает другая сторона 。 Другая сторона берет два, остальные три для вас, вы берете все, вы выигрываете. Другая сторона берет 3, остальные 2 для вас, вы берете их все, вы выигрываете. Ты берешь три, и у тебя останется четыре. Другая сторона берет одну, остальные три для вас, вы берете их все, вы выигрываете. Другая сторона берет два, оставшиеся два для вас, вы берете их все, вы выигрываете. Другая сторона берет 3, оставшаяся-для вас, вы берете все, вы выигрываете. Итак, в этом раунде вы выберете
Предположим, что камней восемь. Возьми одну, и у тебя останется семь. Другая сторона берет одну и отдает вам оставшиеся шесть. Обратитесь к ситуации, когда в начале их всего шесть. Ты победил. Другая сторона берет 2 и отдает вам оставшиеся 5. Обратитесь к ситуации, когда в начале всего 5. Ты победил. Другая сторона берет три и оставляет вам четыре, Выигрывает другая сторона . Вы берете два, и у вас останется шесть. Другая сторона берет одну и отдает вам оставшиеся пять. Ты победил. Другая сторона берет две и оставляет вам четыре, Другая сторона выигрывает. Другая сторона берет три, остальные три для вас, вы берете все, вы выигрываете. Возьми три, и у тебя останется пять. Другая сторона берет одну и оставляет вам четыре, Другая сторона выигрывает. Другая сторона берет два, остальные три для вас, вы берете все, вы выигрываете. Другая сторона берет 3, остальные 2 для вас, вы берете их все, вы выигрываете.
Мы можем добиться соблюдения закона. Когда оставшийся камень является целым кратным 4 и обе стороны принимают оптимальную стратегию, первая из них проигрывает.
Таким образом, вопрос очень прост, пока мы судим, является ли данное число целым кратным 4.
Окончательный код
php
class Solution {
/**
* @param Integer $n
* @return Boolean
*/
function canWinNim($n) {
return $n%4!=0;
}
}Если вы считаете, что эта статья полезна для вас, вы можете воспользоваться поддержкой генерации энергии ИИ.