js实现24点算法

24点算法简介

24点游戏的目标是通过加、减、乘、除四则运算，将4个数字组合成结果为24的表达式。以下是基于JavaScript的实现方法。

基本思路

1. 排列组合：生成所有可能的数字排列顺序。
2. 运算符组合：尝试所有可能的运算符组合（+、-、*、/）。
3. 括号优先级：考虑不同括号组合对运算顺序的影响。
4. 验证结果：检查当前组合是否能得到24。

实现代码

function solve24(numStr) {
  const nums = numStr.split('').map(Number);
  const operators = ['+', '-', '*', '/'];
  const solutions = [];

  // 生成所有数字排列
  function permute(arr, temp = []) {
    if (arr.length === 0) {
      evaluate(temp);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      const newArr = [...arr];
      newArr.splice(i, 1);
      permute(newArr, [...temp, arr[i]]);
    }
  }

  // 尝试所有运算符和括号组合
  function evaluate(numbers) {
    for (let op1 of operators) {
      for (let op2 of operators) {
        for (let op3 of operators) {
          // 无括号：((a op1 b) op2 c) op3 d
          const expr1 = `((${numbers[0]}${op1}${numbers[1]})${op2}${numbers[2]})${op3}${numbers[3]}`;
          tryCalculate(expr1, numbers);

          // 括号组合：(a op1 (b op2 c)) op3 d
          const expr2 = `(${numbers[0]}${op1}(${numbers[1]}${op2}${numbers[2]}))${op3}${numbers[3]}`;
          tryCalculate(expr2, numbers);

          // 其他括号组合
          const expr3 = `${numbers[0]}${op1}(${numbers[1]}${op2}(${numbers[2]}${op3}${numbers[3]}))`;
          tryCalculate(expr3, numbers);
        }
      }
    }
  }

  // 计算表达式并验证结果
  function tryCalculate(expr, numbers) {
    try {
      const result = eval(expr);
      if (Math.abs(result - 24) < 1e-6) {
        solutions.push(expr.replace(/(\d+)/g, m => numbers[numbers.indexOf(Number(m))]));
      }
    } catch (e) {
      // 忽略除零等错误
    }
  }

  permute(nums);
  return solutions.length > 0 ? solutions[0] : 'No solution found';
}

// 示例用法
console.log(solve24('1234')); // 输出可能的解如：(1+3)*(2+4)

关键点说明

1. 排列生成：通过递归生成4个数字的所有排列（共24种顺序）。
2. 运算符遍历：对每种数字排列尝试所有运算符组合（共64种）。
3. 括号处理：通过硬编码常见括号组合方式，覆盖主要运算优先级情况。
4. 浮点数比较：使用Math.abs(result - 24) < 1e-6避免浮点数精度问题。

优化方向

1. 去重：对数学等效的解进行去重（如a+b与b+a）。
2. 性能优化：剪枝提前终止无效分支的运算。
3. 扩展性：支持更多数字或目标值的计算。

该方法通过暴力搜索覆盖所有可能性，确保能找到所有可行解，但时间复杂度较高（O(n! * k^m)，其中n=4, k=4, m=3）。