Алгоритм игры для двух игроков, вычитающий идеальные квадраты из заданного числа

Question

Мне нужна помощь с проблемой. Я недавно получил это в интервью, и я пытался решить это, но безуспешно. Вот вопрос:

Код алгоритма для игры, состоящей из двух игроков. На входе положительное целое число х. Каждый раунд игрок вычитает идеальный квадрат из числа. Игрок может выбрать любой идеальный квадрат, если он меньше или равен текущему числу и больше 0. Текущий игрок выигрывает, если число становится 0 после его удержания.

Я полагаю, что это должно быть сделано с использованием динамического программирования / жадного подхода, с которым я не очень хорошо разбираюсь. Или нам может понадобиться создать последовательность выигрышных / проигрышных чисел, и если игрок окажется в выигрышной последовательности, он выиграет несмотря ни на что. Но как мы можем придумать такую ​​последовательность?

Может кто-нибудь помочь мне решить этот вопрос, возможно, на Java?

UPDATE:

Решение 1, предложенное DAle:

public int subtractPerfectSquares(int n)
   {
      if (n <= 0)
         return 1;
      boolean[] isWinningCase = new boolean[n + 1];

      for (int i = 1; i <= n; i++)
      {
         for (int num = 1; num * num <= i; num++)
         {
            if (!isWinningCase[i - (num * num)])
            {
               isWinningCase[i] = true;
               break;
            }
         }
      }

      return isWinningCase[n] ? 1 : 2;
   }

Решение2 изменено для лучшего понимания:

 public int subtractPerfectSquares2(int n)
   {
      if (n <= 0)
         return 1;
      boolean[] isWinningCase = new boolean[n + 1];

      // if we reach 0, we win
      isWinningCase[0] = true;
      // 1 is a win 
      isWinningCase[1] = true;
      // 2 is a losing condition. We must define this as this state dictates losing scenarios for further states
      isWinningCase[2] = false;

      // we start from 3
      for (int i = 3; i <= n; i++)
      {
         for (int num = 1; num * num <= i; num++)
         {
            int prefectSquare = num * num;
            // if we get to 0 from current number or if we get to a losing scenario (to be faced by next player) from current number, then the current state is a winning position
            if (i - prefectSquare == 0 || !isWinningCase[i - prefectSquare])
            {
               isWinningCase[i] = true;
               break;
            }
         }
      }

      // return player 1 if given number is a winning state else player 2 wins
      return isWinningCase[n] ? 1 : 2;
   }

Answer 1

Программа ниже поможет вам реализовать логику. Я попытался реализовать код в соответствии с вашими требованиями. Обязательно прокомментируйте, если вам нужны улучшения или чтобы уточнить любые недоразумения в логике.

public class Game {

public static void main(String[] args) {
    int number = 0;
    int count = 1;
    int player = 1;
    System.out.println("Please Enter a positive integer");
    try (Scanner sc = new Scanner(System.in);) {
        number = sc.nextInt();
        while (number > 0) {
            int numberArray[] = generatePerfectSquare(1, number);
            System.out.println("===================");
            System.out.println("perfect square numbers");
            for (int i : numberArray) {
                System.out.print(i);
                System.out.print("   ");
            }
            System.out.println("");
            System.out.println("===================");

            player = ((count % 2 == 0) ? 2 : 1);
            System.out.println("Round : " + count + "   Player : " + player);
            System.out.println("Please Enter your prefered perfect square number");

            number = number - sc.nextInt();
            if (number <= 0) {
                System.out.println("****************");
                System.out.println("You won the game");
                System.out.println("===================");
            } else {
                System.out.println("===================");
                System.out.println("You should try more");
                System.out.println("===================");
            }
            count++;
        }
    } catch (Exception e) {
        System.out.println(e);
    }

}

private static int[] generatePerfectSquare(int start, int end) {

    if (start > end || start < 0) {
        throw new IllegalArgumentException();
    }
    int[] perfectSquares = new int[end - start];
    int n = 0;
    int candidate = (int) Math.ceil(Math.sqrt(start));
    int square;
    while ((square = candidate * candidate) < end) {
        perfectSquares[n++] = square;
        candidate++;
    }
    return Arrays.copyOf(perfectSquares, n);
}

Результат теста

Answer 2

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

1. x=0 - проигрышная позиция
2. позиция x - это выигрышная позиция, если есть хотя бы одно возможное движение, которое приводит к проигрышной позиции.
3. позиция x - это проигрышная позиция, если каждое возможное движение приводит к выигрышной позиции.

Тогда нам нужно определить тип всех позиций от 1 до x.Возможная реализация:

boolean[] isWinning = new boolean[x+1];
for (int state = 0; state <= x; ++state) {
    isWinning[state] = false;
    for (int i = 1; i*i <= state; ++i) {
        int perfectSquare = i*i;
        if (!isWinning[state - perfectSquare]) {
            isWinning[state] = true;
            break;
        }
    }
}

Если текущий игрок находится на выигрышной позиции (isWinning[x] == true), вам следует выбрать такой идеальный квадрат, что isWinning[x - perfectSquare] == false.Это приведет игру (и другого игрока) к проигрышной позиции.Если игрок находится в проигрышной позиции, ничто не может спасти его, каждый возможный идеальный квадрат одинаково плох.