2 人游戏的算法从给定数字中减去完全平方

Question

我需要一些帮助来解决问题。我最近在一次采访中得到了这个，我试图解决它但没有运气。这是问题：

编写一个由两名玩家组成的游戏的算法。输入为正整数 x。每一轮，玩家从数字中减去一个完美的正方形。玩家可以选择任意一个小于或等于当前数且大于0的完全方格，如果减去后数变为0则当前玩家获胜。

我想这应该使用我不太熟悉的动态 programming/greedy 方法来完成。或者我们可能需要想出一个 winning/losing 数字的序列，如果玩家最终在一个获胜序列中，无论如何他都会赢。但是我们如何得出这样的序列呢？

谁能帮我解决这个问题 Java?

更新：

DAle 建议的解决方案 1：

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

这个游戏中玩家之间的唯一区别是玩家 1 先走。这种类型的游戏称为 impartial game 并且双方玩家的完美策略是相同的。此外，我们可以使用以下规则将游戏的所有状态（整数x）分为两种类型：获胜位置或失败位置：

x=0是亏损仓位
位置 x 是一个获胜位置，如果至少有一个可能导致失败位置的移动。
位置 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这样的完美方格。这将使游戏（和其他玩家）处于失败的位置。如果玩家处于失败的位置，没有什么可以挽救他，每一个可能的完美方块都同样糟糕。

Answer 2

下面的程序将帮助您实现逻辑。我已尝试根据您的 requirement.Make 实现代码，如果您需要改进或澄清对逻辑的任何误解，请务必发表评论。

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);
}

测试结果

2 人游戏的算法从给定数字中减去完全平方

Algorithm for 2 player game subtracting perfect squares from a given number

java

sequence

dynamic-programming

greedy