题解 | #24点游戏算法#

• 实数除法，包括小数，必须除尽
• 依次遍历，递归计算：加减乘除和后，剩下的数字是否能组成
• 递归计算：除当前数，剩下数组成的数组和加减乘除后的和

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
import java.util.Scanner;

/**
 * class com.sloera.nowcoder
 * user sloera
 * date 2022/2/22
 */
public class Main {
  public static void main(String[] args) throws ScriptException {
    // 7 9 10 9
    Scanner in = new Scanner(System.in);
    // 注意 hasNext 和 hasNextLine 的区别
    int[] num = new int[4];
    while (in.hasNextInt()) { // 注意 while 处理多个 case
      num[0] = in.nextInt();
      num[1] = in.nextInt();
      num[2] = in.nextInt();
      num[3] = in.nextInt();
      final boolean b = canSum(num, 24, false);
      // final boolean b = canSumByEval(num, 24);
      System.out.println(b ? "true" : "false");
    }
  }

  /**
   * 通过eval计算结果，先穷举出所有的可能，再计算
   * 此种方法表明，可以有括号。1 2 10 2示例输出为true。无括号时，无法得出。
   *
   * @param num
   * @param total
   * @return
   * @throws ScriptException
   */
  private static boolean canSumByEval(int[] num, int total) throws ScriptException {
    int sum = num[0] + num[1] + num[2] + num[3];
    char[] operators = new char[]{'+', '-', '*', '/'};
    final ScriptEngine js = new ScriptEngineManager().getEngineByName("js");
    for (int i = 0; i < num.length; i++) {
      for (int j = 0; j < num.length; j++) {
        // 数字只能用一次
        if (j != i) {
          for (int k = 0; k < num.length; k++) {
            // 数字只能用一次
            if (k != i && k != j) {
              // 循环出所有的数字组合。 接着进行所有的符号组合
              for (int l = 0; l < operators.length; l++) {
                for (int m = 0; m < operators.length; m++) {
                  for (int n = 0; n < operators.length; n++) {
                    final String script = "" + num[i] + operators[l] + num[j] + operators[m] + num[k] + operators[n] + (sum - num[i] - num[j] - num[k]);
                    final Object eval = js.eval(script);
                    System.out.println(script + "\t" + eval);
                    if (Double.valueOf(eval.toString()).intValue() == total) {
                      return true;
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
    return false;
  }

  /**
   * 计算是否可以得到对应的值
   *
   * 7 9 10 9 结果有问题
   *
   * @param addFlag 加减标记。如果外面的运算是乘除，则不可加减。{@code true} 不能有加减
   * @return boolean
   * @date 2022/2/23
   */
  private static boolean canSum(int[] num, int total, boolean addFlag) {
    addFlag = false;
    if (num.length == 0) {
      return 0 == total;
    }
    if (num.length == 1) {
      return num[0] == total;
    }
    for (int i = 0; i < num.length; i++) {
      // a * 4 = 24; a = 24 / 4 && 24 % 4 == 0
      final int[] nextNum = generateNum(num, i);
      if ((total % num[i] == 0 && canSum(nextNum, total / num[i], true)) || canSum(nextNum, num[i] * total, true) || (!addFlag && (canSum(nextNum, total - num[i], false) || canSum(nextNum, total + num[i], false)))) {
        return true;
      }
      // num[i] = 4
      // a / 4 = 24; a = 4 * 24 ~ (4 * 25) - 1
      // 实数除法， 所以只能完全相等
      // for (int j = num[i] * total; j < num[i] * (total + 1); j++) {
      //   if (canSum(generateNum(num, i), j, true)) {
      //     return true;
      //   }
      // }
    }
    return false;
  }

  /**
   * 生成非当前索引的数组
   *
   * @return int[]
   * @date 2022/2/22
   */
  private static int[] generateNum(int[] num, int index) {
    if (num.length <= 1) {
      return new int[]{};
    }
    final int[] ints = new int[num.length - 1];
    int j = 0;
    for (int i = 0; i < num.length; i++) {
      if (i != index) {
        ints[j++] = num[i];
      }
    }
    return ints;
  }


}