js实现24点算法

24点算法实现思路

24点游戏要求通过加、减、乘、除四则运算，使得4个数字的运算结果为24。以下是用JavaScript实现的核心方法：

递归穷举所有可能组合

采用递归方式遍历所有数字和运算符的排列组合：

function calculate24(numbers) {
  if (numbers.length === 1) {
    return Math.abs(numbers[0] - 24) < 1e-6;
  }

  for (let i = 0; i < numbers.length; i++) {
    for (let j = 0; j < numbers.length; j++) {
      if (i === j) continue;

      const remaining = numbers.filter((_, index) => index !== i && index !== j);
      const a = numbers[i], b = numbers[j];

      // 尝试所有运算符
      if (tryCombine(a + b, remaining)) return true;
      if (tryCombine(a - b, remaining)) return true;
      if (tryCombine(b - a, remaining)) return true;
      if (tryCombine(a * b, remaining)) return true;
      if (b !== 0 && tryCombine(a / b, remaining)) return true;
      if (a !== 0 && tryCombine(b / a, remaining)) return true;
    }
  }
  return false;
}

function tryCombine(value, remaining) {
  return calculate24([value, ...remaining]);
}

优化版本记录运算过程

以下实现会记录具体的运算步骤：

function solve24(numStr) {
  const nums = numStr.split('').map(Number);
  const solutions = [];

  function dfs(list, path) {
    if (list.length === 1) {
      if (Math.abs(list[0] - 24) < 1e-6) {
        solutions.push(path[0]);
      }
      return;
    }

    for (let i = 0; i < list.length; i++) {
      for (let j = 0; j < list.length; j++) {
        if (i === j) continue;

        const next = [];
        const newPath = [];
        for (let k = 0; k < list.length; k++) {
          if (k !== i && k !== j) {
            next.push(list[k]);
            newPath.push(path[k]);
          }
        }

        const a = list[i], b = list[j];
        const aPath = path[i], bPath = path[j];

        // 加法
        next.push(a + b);
        newPath.push(`(${aPath} + ${bPath})`);
        dfs(next, newPath);
        next.pop(); newPath.pop();

        // 减法（两种顺序）
        next.push(a - b);
        newPath.push(`(${aPath} - ${bPath})`);
        dfs(next, newPath);
        next.pop(); newPath.pop();

        next.push(b - a);
        newPath.push(`(${bPath} - ${aPath})`);
        dfs(next, newPath);
        next.pop(); newPath.pop();

        // 乘法
        next.push(a * b);
        newPath.push(`(${aPath} * ${bPath})`);
        dfs(next, newPath);
        next.pop(); newPath.pop();

        // 除法（两种顺序，且除数不为0）
        if (b !== 0) {
          next.push(a / b);
          newPath.push(`(${aPath} / ${bPath})`);
          dfs(next, newPath);
          next.pop(); newPath.pop();
        }

        if (a !== 0) {
          next.push(b / a);
          newPath.push(`(${bPath} / ${aPath})`);
          dfs(next, newPath);
          next.pop(); newPath.pop();
        }
      }
    }
  }

  dfs(nums, nums.map(String));
  return solutions.length > 0 ? solutions[0] : "No solution found";
}

使用示例

console.log(solve24("1234"));  // 输出类似：(4 * (1 + (3 + 2)))
console.log(calculate24([1, 2, 3, 4])); // 输出: true

注意事项

1. 浮点数比较使用近似判断Math.abs(result - 24) < 1e-6，避免精度问题
2. 除法运算时需要检查除数不为0
3. 算法时间复杂度为O(4! * 4^3) ≈ O(1536)，对于4个数字完全可接受
4. 如需显示所有解而非第一个解，可以收集solutions数组中的所有结果

这种方法通过深度优先搜索遍历所有可能的运算顺序和组合，能够找到是否存在解以及具体的运算步骤。