题解 | #24点游戏算法#
24点游戏算法
https://www.nowcoder.com/practice/fbc417f314f745b1978fc751a54ac8cb
1. 先两两组合，一共四个数，分成互不相同的两个一组（顺序无所谓），共有6种分法。比如数组 [4, 1, 3, 7] 可以分成[4,1]、[4,3]、[4,7]、[1,3]、[1,7]、[3,7]
2. 将以上6种分法进行遍历，传入计算函数calc24, 一共传入两个参数：selected 被选中的数组，与之配对的剩余数组left。 比如原数组[4, 1, 3, 7] ，我们选[4,1]，则剩下[3, 7] , 将这两个数组都传入计算函数。
3. 在计算函数calc24 内部，先判断 left的长度，如果left 长度为2，则意味着这是该组初次进入计算，此时需计算 selected[] 的结果 和 left[] 的结果能不能得出24。比如：原数组[1,9,6,3]，分组后 取一组 selected 为[1,9]，则剩余left为[6,3] ，此时需计算[1,9]的结果 和 [6,3]的结果能不能组成24，此例是可以组成的，比如 9-1 = 8； 6-3 = 3； 8*3 = 24。
- 如果能，则标记flag，退出递归，return
- 如果不能得出24，则将left 数组里每一个数，单独与 selected[] 数组的6种加减乘除运算结果遍历(注意：减法和除法各有两种结果)，分别组成新的 selected[] 和 left[]。比如：原数组[2,4,5,8]，selected为 [2,4] , left 为[5, 8]。selected里面两个数加减乘除res1[] 、 left里两个数加减乘除res2[], res1和 res2 无法组成24， 则将res1[]里每个元素分别于 5 和8 组成新的selected，比如 res1 其中一个元素为2+4 = 6, 6与left 中的5 组合，组成[6, 5], left 中剩余[8], 则新的selected数组为[6, 5] ， 新的 left 数组为[8]。
4. 递归退出条件，① 找到24，flag标记位true，return； ② left 数组为空，flag还是false，则没有找到符合的组合计算方式，return false
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
// Write your code here
while ((line = await readline())) {
let cards = line.split(" ").map(Number);
let flag = false; // 标志位，标记有没有找到能算出24的解法，默认为false，还没找到
for (let i = 0; i < cards.length - 1; i++) {
for (let j = i + 1; j < cards.length; j++) {
let t = [cards[i], cards[j]];
let cl = [...cards]; // 一定要深拷贝
cl.splice(i, 1);
cl.splice(j - 1, 1);
calc24(t, cl);
}
}
console.log(flag);
function calc24(selected, left) {
// selected 数组，被选中的组合的元素，left 被选中后剩下的元素
let save_calc = six_op(selected[0], selected[1]);
if (left.length == 0) {
// 如果left数组为空，则说明已经递归完成，只需判断selected数组里的两个元素能不能组成24即可。
for (let i = 0; i < save_calc.length; i++) {
if (Math.abs(save_calc[i] - 24) <= 0.0001) {
flag = true;
return true;
}
}
} else if (left.length == 2) {
// 如果left数组长度为2，则说明这是刚进入第一次递归，calc24()传入的两个参数是[1,9] [6,3] 这种，则需计算[1,9]的结果 和 [6,3]的结果能不能组成24，此例是可以组成的，比如 9-1 = 8； 6-3 = 3； 8*3 = 24
let save_left_calc = six_op(left[0], left[1]);
save_calc.forEach((item, i) => {
// 6*6
save_left_calc.forEach((nt, j) => {
if (
Math.abs(item + nt - 24) <= 0.000001 ||
Math.abs(item - nt - 24) <= 0.000001 ||
Math.abs(nt - item - 24) <= 0.000001 ||
Math.abs(item * nt - 24) <= 0.000001 ||
Math.abs(item / nt - 24) <= 0.000001 ||
Math.abs(nt / item - 24) <= 0.000001
) {
flag = true;
return true;
}
});
});
}
if (!flag) {
if (left.length == 0) {
// left数组都用完了，还是没找到，则说明没有满足24的解法
return false;
} else {
// left 数组还有，继续跑
for (let j = 0; j < left.length; j++) {
let r = [...left];
r.splice(j, 1);
save_calc.forEach((item) => {
calc24([item, left[j]], r); // 加
});
}
}
}
}
function six_op(num1, num2) {
let res = [];
res.push(num1 + num2); // 加
res.push(num1 - num2); // 减1
res.push(num2 - num1); // 减2
res.push(num1 * num2); // 乘
res.push(parseFloat((num1 / num2).toFixed(7))); // 除1
res.push(parseFloat((num2 / num1).toFixed(7))); // 除2
return res;
}
}
})();
投递字节跳动等公司10个岗位 >
