js穷举法写24点游戏算法
时间: 2023-11-10 16:08:35 浏览: 52
首先,需要明确一下24点游戏的规则:给定4个数字,可以通过加减乘除和括号的运算,使得最终的结果为24。
穷举法的思路就是将所有可能的组合都尝试一遍,看看是否有符合要求的。以下是一个JavaScript实现的例子:
```javascript
function game24(arr) {
if (arr.length == 1) {
return Math.abs(arr[0] - 24) < 0.00001; // 判断结果是否为24
}
// 枚举所有可能的情况
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (i == j) continue;
let newArr = [];
for (let k = 0; k < arr.length; k++) {
if (k != i && k != j) {
newArr.push(arr[k]);
}
}
// 加法
newArr.push(arr[i] + arr[j]);
if (game24(newArr)) return true;
newArr.pop();
// 减法
newArr.push(arr[i] - arr[j]);
if (game24(newArr)) return true;
newArr.pop();
// 乘法
newArr.push(arr[i] * arr[j]);
if (game24(newArr)) return true;
newArr.pop();
// 除法
if (arr[j] != 0) {
newArr.push(arr[i] / arr[j]);
if (game24(newArr)) return true;
newArr.pop();
}
}
}
return false;
}
console.log(game24([4, 6, 8, 9])); // true
console.log(game24([1, 2, 3, 4])); // false
```
该算法的时间复杂度为 $O(4^3 \times 3^3 \times 2^2 \times 1)$,即 $O(13824)$,在数字比较少的情况下还是很快的。但是随着数字数量的增加,时间复杂度会呈指数级增长,不适用于大规模数据的处理。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)