Игра 2/9 (интервью в Facebook)

Ответ 1

Лучший подход к этому типу вопросов.

Сначала вам нужно иметь базовое понимание теории игр. Действительно основной. То есть вы осознаете тот факт, что для данного номера N существует либо выигрышная стратегия для игрока, который начинает, либо выигрышную стратегию для его оппонента. Поэтому вы должны предположить, что они оба знают стратегию и играют лучшие шаги, которые они могут сделать.

Затем вы начинаете с знакомиться с игрой. Вы тренируетесь на низком уровне. Вы быстро заметили, что за 2-9 стартер выигрывает, а за 10-18 он должен проиграть. Таким образом, ваша функция готова для случая N<=18.

Затем вы начинаете думать об общей стратегии выигрыша. Знание стратегии даст вам алгоритм. Через 5 минут (чем скорее, тем лучше) вы поймете, что не успеете найти выигрышную стратегию, так как в этом случае это не очевидно. Поэтому вы решили дать компьютеру некоторые основные принципы и позволить ему решить загадку для вас. Вы знаете, что будете использовать рекурсию.

Вы пытаетесь найти правило для рекурсии. Вы можете начать с конца или с самого начала. Я опишу подход с самого конца.

Цель игры - направить вашего противника в зону, где он должен дать вам победу. И не попасть в эту зону самостоятельно. С N/9 до N есть зона для выигрыша. Если кто-то подталкивает играть между N/9/2 и N/9, он должен проиграть. (Потому что оба его движения подталкивают его противника в зону выигрыша.) Итак, вы пишете свою функцию:

wins(n) {
  // returns 1, if starting player is able to reach
  // the range [n, 2*n) with his move
  if (n<=18) {
    if (n<=9)
      return 1;
    else
      return 0;
  } else {
    // I must push him to the zone between N/9/2 and N/9
    return wins(n/18);
  }

Если вы достигли этого момента, вы прошли. Остаются детали, например, использовать ли float или int, следует ли округлять вверх или вниз с помощью int. Но в целом вы показали правильный образ мышления, и вы готовы встретиться с интервьюером:)

ИЗМЕНИТЬ. На самом деле ошибка в коде выше. "Победа" - это не то же самое, что "возможность достичь диапазона (n, 2n)". Возможно, здесь нужны 2 функции: wins(n) и reaches_slightly_above(n). Последний будет вызываться рекурсивным образом, а значения, возвращаемые ниже 18, должны быть разными, похожими на значения в решении Peter de Rivaz. Однако нижеприведенное решение и общий подход должны быть в порядке.

Альтернативный подход , идущий снизу вверх, должен был бы использовать функцию:

wins(a,n) {
  if (9*a >= n)
    // I win easily
    return 1;
  else
    // if one of my moves pushes the opponent to the zone
    // where he not able to win, then I win!
    return !wins(2*a, n) || !wins(9*a, n);
}

Если они запрашивают n, вы возвращаете значение win(1,n). Сложность этого алгоритма не очевидна, но я считаю это логарифмическим.

Ответ 2

Так как они должны достигать ровно N, это возможно только в том случае, если N имеет вид 2^a * 9^b, а один из a, b также может быть 0.

Найдите a и b выше: if a + b = even, тогда второй игрок победит, иначе победит первый.

Это связано с тем, что на каждом шаге игрок приближается к a или b на один, а значит, на a + b на один. Таким образом, проблема сводится к: заданному k, если на каждом шаге игрок должен вычесть 1 из k, какой игрок сначала достигнет 0?

Ответ 3

Оптимальное воспроизведение, как правило, должно играть противоположное движение противника, за исключением права в начале и конце.

Сравнивая с рекурсивным решением, оказывается, что ответ может быть вычислен на основе самой значащей цифры в базовом 18 представлении числа-1 следующим образом:

def win29(n):
    if n<=9: return True
    n-=1
    while n>=18:
        n = n//18
    return n==1 or 4<=n<=8

Ответ 4

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

Рассмотрим T = ceil( log(N)/log(18) ), то есть T - наименьшая степень, такая, что 18^T соответствует или превышает N.

Если 18^(T-1) * 9 < N, то первый игрок всегда проигрывает идеальному противнику. Всякий раз, когда первый игрок выбирает 2, второй выбирает 9. И всякий раз, когда первый выбирает 9, второй выбирает 2. Таким образом, второй игрок поворачивается всегда на мощность 18. После T раундов, побеждает второй игрок. Первый игрок не может выиграть в предыдущем раунде, потому что умножения на 9 недостаточно для того, чтобы превысить N (поэтому ни один не умножается на 2).

Итак, теперь рассмотрим 18^(T-1) * 9 >= N и выберите наименьший k такой, что 18^(T-1) * 2^k > N. Существует четыре возможности k = 1, 2, 3, or 4.

• (k = 1) Побеждает первый игрок. Первый игрок может начинать с 2, а затем играть, как второй игрок сделал выше, играя противоположный номер от другого игрока каждый последующий поворот до следующего до последнего раунда. Второй игрок всегда будет сталкиваться с силой в 18 раз от начального 2. При 18 ^ (Т-2) * 2, игрок два может достигать 18^(T-1), умножая на 9, чего недостаточно для победы, и может, по крайней мере, вернуть 18^(T-2)*4, какой игрок можно умножить на 9, чтобы выиграть с помощью 18^(T-1)*2.

• (k = 3) Побеждает и первый игрок. На этот раз игрок начинает игру с 9 и играет по-прежнему. Второй игрок всегда будет сталкиваться с силой в 18 раз от начального 9. В 18 ^ (Т-2) * 9, два игрока могут достичь наибольшего значения 18^(T-2) * 9 * 9 < 18^(T-2) * 18 * 8 = 18^(T-1) * 2^3, поэтому этого недостаточно, чтобы выиграть, и может по крайней мере return 18 ^ (T-1), умножив на 2, который игрок умножит на 9 и выиграет.

• (k = 2 or 4) Побеждает второй игрок. Здесь второй игрок должен сыграть противоположное число, как и раньше, до конца, так что каждый круглый игрок начинает с мощности 18. В 18^(T-2) игрок может достичь максимум 18^(T-2)* 9 < 18^(T-1), поэтому этого недостаточно, чтобы выиграть, Если он вернет 18 ^ (Т-2) * 9, игрок выиграет с 18^(T-2)*9*9 > 18^(T-2)*18*4 = 18^(T-1)*2^2 Если игрок один вместо 18^(T-2)*2, игрок два возвращает 18^(T-2)*4. Затем игрок может сделать максимум 18^(T-2)*4*9 = 18^(T-1)*2, чего еще недостаточно. И теперь игрок может по крайней мере вернуть 18^(T-2)*8, что достаточно для игрока, которому нужно два матча, так как 18^(T-2)*8*9 = 18^(T-1)*4.

Ответ 5

Да, вы должны думать об оптимальной игре от обоих игроков и решать, кто победит.

Здесь простое рекурсивное мышление может привести вас к решению.

Если игрок имеет номер n и n*9 >= N, то текущий игрок выиграет игру.
иначе он будет передавать либо 2*n, либо 9*n, второму игроку. Теперь 1-й игрок проиграет игру, только если обе предоставленные им опции (2*n и 9*n) второму игроку приведут к выигрышному номеру для второго игрока, иначе у него будет шанс выиграть выигрыш номер снова.

Следовательно, мы могли бы написать рекурсивный подход следующим образом: так как все числа в игре будут иметь вид: 2^i * 9^j мы могли бы написать:

 F(i, j) = true; if (2^i * 9^j * 9) >= N
           !(F(i+1, j) && F(i, j+1)); otherwise

будет в F(0, 0), победит ли первый игрок или нет.

Ответ 6

Есть большие ответы, если N можно разделить на 2 и 9, а также хорошая теория игры. Вот простой подход динамического программирования в Javascript, чтобы дать ответ на любой возможный N.

function getWhoWins(n) {
    if(getWhichPlayerWins(0, 1, n) === 0) {
        console.log("First player wins for " + n);
    } else {
        console.log("Second player wins for " + n);
    }
}

// Returns 0 if first, 1 if 2nd player would win
function getWhichPlayerWins(currentPlayer, currentNumber, targetNumber) {
    if(currentNumber * 9 >= targetNumber) {
        return currentPlayer;
    }
    var nextPlayer = (currentPlayer + 1) % 2;
    if(getWhichPlayerWins(nextPlayer, currentNumber *2, targetNumber) === currentPlayer || getWhichPlayerWins(nextPlayer, currentNumber *9, targetNumber) === currentPlayer) {
        return currentPlayer;
    }
    return nextPlayer;
}

Временной сложностью этого решения является O (2 * logN) = O (logN).

Ответ 7

Ответ (я не уверен на 100%):

r = N mod 18

if r belongs to (1,9]  player 1 wins
if r belongs to (9,18) or is =1  then player 2 wins.

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

Я получаю работу?:)

Ответ 8

Двупользовательские, детерминированные игры, подобные этому, изучаются комбинаторной теорией игр. Эта легкомысленная теория игр не имеет отношения к более полезной теории игр Неймана и Нэша, популярной в экономике. Основная работа - восхитительная книга под названием "Победные пути" Конвей, Берлекампа и Гая.

Думать. Для любой игры:

• Существует стратегия, согласно которой второй игрок всегда выигрывает, однако первый игрок играет.
• Существует стратегия, благодаря которой первый игрок всегда выигрывает, однако второй игрок играет.

Ваша игра - это особый случай, беспристрастная игра, в которой состояние игры одинаково выглядит для обоих игроков. Лучший пример - простая игра в спичечную игру под названием Nim. Бывает, что все беспристрастные игры эквивалентны Nim (это теорема Sprague Grundy), поэтому все беспристрастные игры могут быть решены полностью.

Позвольте решить вашу игру. Возможными состояниями игры являются положительные целые числа. Мы будем классифицировать каждое состояние как выигрыш для второго игрока (мы будем называть такие игры с нулевым "0" ), либо выигрышем для первого игрока (мы будем называть такие игры звездами "*" ).

Целые числа, большие или равные N, равны нулю, поскольку в этот момент игра закончена. Кто бы ни двигался, он уже потерял.

Государства, в которых игрок, чей ход он может перейти на нулевые позиции выше, - это звездные игры. Таким образом, целые числа n, N/9 <= n < N - все звездные игры - выигрышный ход должен умножаться на 9.

В тех случаях, когда игрок, чей ход у него нет выбора, кроме как перейти на позицию звезды, снова равен нулю. Итак, целые числа n, N/9/2 <= n < N/9 являются нулевыми позициями. Наш игрок проиграл.

И так далее. Используя аналогичные аргументы, мы в конечном итоге классифицируем все целые числа до одного.

При N = 1000 скажем,

• Целые числа 1000 и выше равны нулю.
• Целые числа от 112 до 999 - это звездные игры (выигрыш, умножение на 9)
• Целые числа от 56 до 111 - это нулевые игры (игрок не может выиграть)
• Целые числа от 7 до 55 - это звездные игры (умножьте соответственно на 9 или 2, чтобы перейти к одной из нулевых игр с 56 по 111).
• Целые числа с 4 по 6 - это игры с нулевым уровнем (игрок не может выиграть)
• Целые числа с 2 по 3 - звездочные игры (умножаются на 2)
• Целое число 1 - это нулевая игра (игрок не может выиграть)

Обобщая вывод Питера fooobar.com/questions/483971/...

Ответ 9

Интересный пост и ответы. У меня возникнет соблазн предложить теоретическую функцию грубой силы, которая перечисляет все комбинаторные пути с использованием 2/9 факторов к N <= 2X10 ^ 12 (или как можно ближе). Я говорю "теоретический", потому что я предполагаю, что такая вычислительная мощность выходит за рамки даже FB?