【算法】苹果一道“24点”类型的面试题详细解析，小班同学也直呼通俗易懂
本帖最后由 hans7 于 2023-12-14 00:58 编辑## 引言
今天看到一道24点类型的问题，题目来自(https://b23.tv/kEQpICc)。因为原题题意不清晰，所以我在此描述得更清晰一些：
对于`0 0 0`到`10 10 10`这11组数，请填入运算符凑出6。允许使用的二元运算符包括`** * / % + - << >> & | ^`，允许使用的一元运算符包括`!, sqrt, fac`（根号、阶乘），允许使用括号。每一次的二元运算结果都可以使用至多一次一元运算符，比如`((0! + 0!)! + 0!)! = 6`是合法的。其中除法需要除得尽才合法。
[本文GitHub传送门](https://github.com/Hans774882968/apple-interview-24point-similar)
## 表达式树介绍
24点的dfs比较好理解，但如果没有专门学习过很难自己想出来。首先我们要了解**表达式树**。以下面这棵表达式树为例：
```
*
/ \
1 +
/ \
2 3
```
它表示表达式`1 * (2 + 3)`。表达式树的叶子节点为数字，非叶子节点为二元运算符。我们dfs遍历这棵树，走到非叶子节点，需要先获取左右子树的运算结果，再根据该点的符号获取当前子树的运算结果。
表达式树也可以很轻松地表示一元运算符。比如：
```
*
/ \
1 +
/ \
2fac
|
3
```
表示表达式`1 * (2 + 3!)`。实际上，表达式树是**抽象语法树**（Abstract Syntax Tree，AST）的特殊情况，如果你有前端基础，可以进(https://astexplorer.net/)快速学习。
## 算法实现
然后我们就可以理解24点的dfs了。最初有`n`个数，相当于有`n`个单节点的树。我们每次选择两棵子树进行合并，合并`n - 1`次后就得到最终的表达式树。使用dfs枚举所有可能的合并方案即可。
接下来看下实现，以(https://acm.hdu.edu.cn/showproblem.php?pid=1427)为例：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int SZ = 4;
char s;
bool vis;
int a;
template<typename Type>inline void read (Type &xx) {
Type f = 1;
char ch;
xx = 0;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
xx *= f;
}
int getn (char s[]) {
if (strlen (s) == 2) return 10;
else if (s == 'A') return 1;
else if (s == 'J') return 11;
else if (s == 'Q') return 12;
else if (s == 'K') return 13;
return s - '0';
}
bool dfs (int dep) {
if (dep == SZ - 1) {
for (int i = 0; i < SZ; ++i) {
if (!vis) {
if (a == 24) return true;
}
}
return false;
}
bool fl = false;
for (int i = 0; i < SZ; ++i) {
if (vis) continue;
for (int j = i + 1; j < SZ; ++j) {
if (vis) continue;
vis = true;
int x = a, y = a;
if (y && x % y == 0) {
a = x / y;
if (dfs (dep + 1) ) fl = true;
}
if (x && y % x == 0) {
a = y / x;
if (dfs (dep + 1) ) fl = true;
}
a = x + y;
if (dfs (dep + 1) ) fl = true;
a = x - y;
if (dfs (dep + 1) ) fl = true;
a = y - x;
if (dfs (dep + 1) ) fl = true;
a = x * y;
if (dfs (dep + 1) ) fl = true;
a = x;
vis = false;
}
}
return fl;
}
int main (int argc, char **argv) {
while (~scanf ("%s%s%s%s", s, s, s, s) ) {
for (int i = 0; i < SZ; ++i)
a = getn (s);
memset (vis, 0, sizeof vis);
puts (dfs (0) ? "Yes" : "No");
}
return 0;
}
```
1. `vis = true`表示`i`号子树属于其他的树，`vis = false`表示`i`号树未被合并过。
2. `a`存`i`号子树的求值结果。
3. 这里是用`i`号来存合并后的树，你想改成`j`号也行。如果你想early return，需要记得**恢复现场**：`a = x; vis = false; return true;`。
4. 如果你想获取生成的表达式，那么你必须引入一个`string ans`。
接下来考虑一元运算符怎么实现。
1. 对于叶子，我们在dfs外部枚举4进制位，约定0表示不变，1表示变为阶乘，2表示变为根号，3表示取反。如果要支持其他一元运算符，比如`- ~`，就相应改成枚举5、6进制位即可。
2. 对于非叶子，在dfs内部进行变换即可。
现在我们已经理解了算法，接下来只需要讲下实现上的细节：
1. 每个运算符都需要考虑准入条件。比如`**, fac`需要防止结果过大（引入`powTooLarge`函数）、`/ %`需要保证除数不为0、`sqrt`需要保证原数是完全平方数（引入`isPerfectSquare`函数）。
2. 输出量较大，所以我们把输出重定向到文件了。
3. 为了方便地验证输出结果的正确性，我们拼接了一段js代码，结构：`let fac = (v) => v > 0 ? v * fac(v - 1) : 1, { sqrt } = Math;\n[].every((v) => v === 6);`。把代码直接复制到浏览器控制台，执行结果为true即符合预期。
下面我给出两版代码，`v2`相比于`v1`只多了上述一元运算符实现点的“2”，但代码量却达到了两倍。
执行结果：
1. `v1`执行时间可以接受，`v2`执行时间以分钟计。
2. `8 8 8`没有找到答案，其他的都找到了不少答案。不过如果允许构造一个集合的话，就有一个比较离谱的答案：`|{ 8, 8, 8 }|! = 6`。
`v1`
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = int64_t;
// Copyright 2023 hans7
const int N = 3, M = 11;
bool vis;
int p4;
LL fac, a;
string ans;
set<string> ansSet;
void dbg() { puts(""); }
template <typename T, typename... R>
void dbg(const T &f, const R &...r) {
cout << f << " ";
dbg(r...);
}
bool powTooLarge(LL x, LL y) {
if (y >= 63) return x >= 2;
return y * log(x) >= 43.66827237527655;
}
bool isPerfectSquare(LL v) {
LL root = sqrt(v);
return root * root == v;
}
bool dfs(int dep) {
if (dep + 1 == N) {
for (int i = 0; i < N; i++) {
if (!vis) {
if (a == 6) {
ansSet.insert(ans);
}
return a == 6;
}
}
return false;
}
bool fl = false;
for (int i = 0; i < N; i++) {
if (vis) continue;
for (int j = i + 1; j < N; j++) {
if (vis) continue;
vis = true;
LL x = a, y = a;
string tmpAnsI = ans, tmpAnsJ = ans;
if (!powTooLarge(x, y)) {
a = round(pow(x, y));
ans = "(" + tmpAnsI + ") ** (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
}
if (!powTooLarge(y, x)) {
a = round(pow(y, x));
ans = "(" + tmpAnsJ + ") ** (" + tmpAnsI + ")";
if (dfs(dep + 1)) fl = true;
}
if (y && x % y == 0) {
a = x / y;
ans = "(" + tmpAnsI + ") / (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
}
if (x && y % x == 0) {
a = y / x;
ans = "(" + tmpAnsJ + ") / (" + tmpAnsI + ")";
if (dfs(dep + 1)) fl = true;
}
a = x * y;
ans = "(" + tmpAnsI + ") * (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
if (y) {
a = x % y;
ans = "(" + tmpAnsI + ") % (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
}
if (x) {
a = y % x;
ans = "(" + tmpAnsJ + ") % (" + tmpAnsI + ")";
if (dfs(dep + 1)) fl = true;
}
a = x + y;
ans = "(" + tmpAnsI + ") + (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
a = x - y;
ans = "(" + tmpAnsI + ") - (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
a = y - x;
ans = "(" + tmpAnsJ + ") - (" + tmpAnsI + ")";
if (dfs(dep + 1)) fl = true;
a = x << y;
ans = "(" + tmpAnsI + ") << (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
a = y << x;
ans = "(" + tmpAnsJ + ") << (" + tmpAnsI + ")";
if (dfs(dep + 1)) fl = true;
a = x >> y;
ans = "(" + tmpAnsI + ") >> (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
a = y >> x;
ans = "(" + tmpAnsJ + ") >> (" + tmpAnsI + ")";
if (dfs(dep + 1)) fl = true;
a = x & y;
ans = "(" + tmpAnsI + ") & (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
a = x | y;
ans = "(" + tmpAnsI + ") | (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
a = x ^ y;
ans = "(" + tmpAnsI + ") ^ (" + tmpAnsJ + ")";
if (dfs(dep + 1)) fl = true;
a = x;
ans = tmpAnsI;
vis = false;
}
}
return fl;
}
int main(int, char **) {
fstream file;
file.open("apple_interview_24point_similar-v1.txt", ios::out);
streambuf *stream_buffer_out = cout.rdbuf();
cout.rdbuf(file.rdbuf());
for (int i = 0; i <= N; i++) p4 = i ? p4 * 4 : 1;
for (int i = 0; i < M; i++) fac = i ? fac * i : 1;
vector<size_t> ansSetSizes;
for (int i = 0; i < M; i++) {
ansSet.clear();
bool hasAns = false;
for (int S = 0; S < p4; S++) {
for (int j = 0; j < N; j++) {
int v = 0;
string strV;
int sVal = S / p4 % 4;
if (sVal == 1 && isPerfectSquare(i)) {
v = sqrt(i);
strV = "sqrt(" + to_string(i) + ")";
} else if (sVal == 2) {
v = fac;
strV = "fac(" + to_string(i) + ")";
} else if (sVal == 3) {
v = !i;
strV = "!" + to_string(i);
} else {
v = i;
strV = to_string(i);
}
a = v;
ans = strV;
}
hasAns |= dfs(0);
}
ansSetSizes.push_back(ansSet.size());
cout << i << " " << hasAns << endl;
cout << "ansSet.size() = " << ansSet.size() << endl;
string jsCode =
"let fac = (v) => v > 0 ? v * fac(v - 1) : 1, { sqrt } = Math;\n[";
for (auto v : ansSet) {
jsCode += v + ", ";
}
jsCode += "].every((v) => v === 6);";
cout << jsCode << endl;
}
cout << "ansSetSizes = [";
ostream_iterator<size_t> out_iter(cout, ", ");
copy(ansSetSizes.cbegin(), ansSetSizes.cend(), out_iter);
cout << "]" << endl;
cout.rdbuf(stream_buffer_out);
file.close();
return 0;
}
```
`v2`代码过长，在此不贴出，[传送门](https://github.com/Hans774882968/apple-interview-24point-similar/blob/main/apple_interview_24point_similar-v2.cpp) 天下客 发表于 2023-12-13 17:56
如果规定数字是short int或int，然后加入!运算符会不会好一些
已经添加，commit：
https://github.com/Hans774882968/apple-interview-24point-similar/commit/65d255cfc6e22530eb7e4add255639afe9524047 InWell 发表于 2024-4-1 21:10
代码上加点注释会可能会直观一点，思路都是深度遍历出所有可能找到正确结果。
对，整体思路就是dfs，只是因为运算符多代码才看上去很多。我当时的想法是，只要每种情况用一个空行隔开，就足够直观了，所以就没写注释了。 感谢楼主的分享 mark一下，明天心情好了再学 没学过，但是貌似对于大型数据处理很有用的样子 lookfeiji 发表于 2023-12-9 11:29
没学过，但是貌似对于大型数据处理很有用的样子
并木有:'(weeqw
mark一下 没看明白
很像天书。。。。。。。 值得学习一下