js实现24点算法
24点算法实现思路
24点游戏要求通过加、减、乘、除四则运算，使用给定的4个数字计算出24。JavaScript实现可以通过递归或穷举所有可能的运算组合来找到解法。
基本算法步骤
生成所有数字排列组合 利用递归或交换法生成4个数字的全排列，确保每个数字在不同位置被尝试。
生成所有运算符组合
三个运算符（连接两个数字）可以是+、-、*、/，共4^3=64种可能组合。
考虑运算优先级和括号 通过不同的运算顺序（即括号位置）来改变优先级，共有以下5种表达式结构：
((a op b) op c) op d(a op (b op c)) op d(a op b) op (c op d)a op ((b op c) op d)a op (b op (c op d))
JavaScript代码实现
function solve24(nums) {
const ops = ['+', '-', '*', '/'];
const solutions = [];
function evaluate(a, b, op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
}
function calculate(permutation, opsCombination) {
const [a, b, c, d] = permutation;
const [op1, op2, op3] = opsCombination;
// 尝试5种不同的括号组合
const expressions = [
`((${a} ${op1} ${b}) ${op2} ${c}) ${op3} ${d}`,
`(${a} ${op1} (${b} ${op2} ${c})) ${op3} ${d}`,
`(${a} ${op1} ${b}) ${op2} (${c} ${op3} ${d})`,
`${a} ${op1} ((${b} ${op2} ${c}) ${op3} ${d})`,
`${a} ${op1} (${b} ${op2} (${c} ${op3} ${d}))`
];
for (const expr of expressions) {
try {
const result = eval(expr);
if (Math.abs(result - 24) < 1e-6) {
solutions.push(expr);
}
} catch (e) {
// 忽略除以零等错误
}
}
}
// 生成所有数字排列
function permute(arr, start = 0) {
if (start === arr.length - 1) {
// 生成所有运算符组合
for (const op1 of ops) {
for (const op2 of ops) {
for (const op3 of ops) {
calculate([...arr], [op1, op2, op3]);
}
}
}
return;
}
for (let i = start; i < arr.length; i++) {
[arr[start], arr[i]] = [arr[i], arr[start]];
permute(arr, start + 1);
[arr[start], arr[i]] = [arr[i], arr[start]];
}
}
permute(nums);
return solutions.length > 0 ? solutions : ['No solution found'];
}
// 示例用法
console.log(solve24([1, 5, 5, 5])); // 输出可能的解法优化方向
避免重复计算 可以缓存已计算过的数字和运算符组合，减少重复计算。
提前终止 当找到第一个解时立即返回，而不是计算所有可能性。
浮点数精度处理
使用Math.abs(result - 24) < 1e-6而非result === 24来避免浮点数精度问题。
避免eval
可以构建表达式树或使用其他方式计算表达式值，避免使用eval带来的安全风险。
示例输出
对于输入[1, 5, 5, 5]，可能的输出包括：
["(5 - (1 / 5)) * 5"]这个实现通过穷举所有可能的数字排列、运算符组合和括号位置来寻找解法，虽然效率不高但对于4个数字的情况已经足够。
