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注意事项
- 浮点数比较使用近似判断
Math.abs(result - 24) < 1e-6，避免精度问题 - 除法运算时需要检查除数不为0
- 算法时间复杂度为O(4! * 4^3) ≈ O(1536)，对于4个数字完全可接受
- 如需显示所有解而非第一个解，可以收集
solutions数组中的所有结果
这种方法通过深度优先搜索遍历所有可能的运算顺序和组合，能够找到是否存在解以及具体的运算步骤。
