计算24点与运算符重载

十几年前写过一个算24点的程序。记得当时有点费劲，不过最后总算捣鼓出来了。前几天突然想再写一次，结果轻松地写出来了。C++，总行数不多，带命令行界面和注释共200行不到；利用了面向对象和运算符重载来简化代码。

首先谈算法。算法想清楚了，实现起来就很快；否则，一边写一边想，往往会陷入复杂。
算法就是：

• 从4个数字中取2个数字进行计算，将计算结果和剩下的2个数字列在一起，这样就将原来的4个数字缩减为3个数字了；
• 重复这个过程，从3个数字中取2个进行计算，就将原来的3个数字变成了2个数字；
• 最后检测这2个数字的计算结果是否是24.

从数学上探讨一下计算机遍历的可能性：

• 4个数字取任意2个，共6种可能；
• 2个数字进行加减乘除的计算，共有6个结果（加乘各1个，减除各2个）；
• 所以，从4个数字，变成3个数字，共有 6x6=36 种可能（这其中可能会有重复，先不管，但在源码最后会有去重的技巧）；
• 同样的算法，从3个数字变成2个数字，共有 3*6=18 种可能；
• 从2个数字变成1个数字，共有6种可能；
• 所以，从4个数字变成1个数字，计算机最多遍历 36 * 18 * 6 = 3888 种可能
• 通用的计算公式是: C(4,2) * 6 * C(3,2) * 6 * C(2,2) * 6 = 3888
• 如果输入5个数字，就要多乘以 C(5,2)*6, 即多乘以 60 种可能

知道了算法，程序也就差不多确定了。
首先，需要写一段代码，列出所有“从N个数字中取2个数字”的可能性，即：既要列出取出的2个数字，也要保留剩下的数字；

其次，要写一段代码，算出2个数字的6种计算结果，还要把这6个计算过程保留下来；怎么保留计算过程呢？
每一个数字都有其来源，这个来源就是其计算过程，可以用string将其保留下来。
于是，很自然地就想到自定义一个 Number 类，既包含值，又用string类型保留了该数字的来源过程。
进一步又想到，如果重载了运算符，那么对Number的加减乘除操作的代码可能就非常简单了。

最后，要实现4变3、3变2、2变1的过程； 很自然想到，这个过程其实是递归的，所以只要实现一个“从N个数字的数组变为N-1个数字的数组”的函数即可，之后再将其略作改变，成为递归。

具体代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;const double TARGET_NUMBER = 24;
vector<string> Solutions;class Number {
private:double val; string exp; public:Number(double v=0, string e="") : val(v), exp(e) {}Number(double v) : val(v) {stringstream ss;ss << val;exp = ss.str();}Number(int v) : val(v) {stringstream ss;ss << val;exp = ss.str();}Number(const Number& other) {val = other.val;exp = other.exp;}void operator = (const Number& other) {if (this == &other) return;this->val = other.val;this->exp = other.exp;}friend Number operator + (Number& a, Number& b) {Number res;res.val = a.getVal() + b.getVal();stringstream ss;ss << "(" << a.getExp() << "+" << b.getExp() << ")";res.exp = ss.str();return res;}friend Number operator - (Number& a, Number& b) {Number res;res.val = a.getVal() - b.getVal();stringstream ss;ss << "(" << a.getExp() << "-" << b.getExp() << ")";res.exp = ss.str();return res;}friend Number operator * (Number& a, Number& b) {Number res;res.val = a.getVal() * b.getVal();stringstream ss;ss << "(" << a.getExp() << "*" << b.getExp() << ")";res.exp = ss.str();return res;}friend Number operator / (Number& a, Number& b) {Number res;res.val = a.getVal() / b.getVal();stringstream ss;ss << "(" << a.getExp() << "/" << b.getExp() << ")";res.exp = ss.str();return res;}double getVal() { return val; }string getExp() { return exp; }
};// original array = [a, b, restArray]
struct DataSet {Number a; Number b; vector<Number> restArray; DataSet(Number a=0, Number b=0) : a(a), b(b) {}
};vector<Number> genTwoNumResult(Number a, Number b) {vector<Number> result;result.push_back(a+b);result.push_back(a*b);result.push_back(a-b);result.push_back(b-a);result.push_back(a/b);result.push_back(b/a);return result;
}// Get 2 numbers out of one array 
// Save all the possibilities to one vector 
vector<DataSet> getTwoOutofArray(const vector<Number>& vec) {int vecSize = vec.size();vector<DataSet> result = {};if (vecSize < 2) return result;vector<pair<int, int>> indexPairs; for (int i=0; i<vecSize-1; i++) {for (int j=i+1; j<vecSize; j++) {indexPairs.push_back({i, j});}}for (pair<int,int>& p : indexPairs) {DataSet tmp(vec[p.first], vec[p.second]);for (int i=0; i<vecSize; i++) {if (i != p.first && i != p.second) {tmp.restArray.push_back(vec[i]);}}result.push_back(tmp);}return result; 
}// Recusive Function: reduce the size of array by one for one time 
void resolve(vector<Number>& array) {if (array.size() <= 0) return;if (array.size() == 1) {if (array[0].getVal() - TARGET_NUMBER < 1e-6 && TARGET_NUMBER - array[0].getVal() < 1e-6) {Solutions.push_back(array[0].getExp()); }return; }vector<vector<Number>> newArrays; vector<DataSet> middleSets = getTwoOutofArray(array);for (auto& dataSet : middleSets) {// Get 2 numbers out of one array, then the 2 numbers can generate 6 different numbers vector<Number> newNumbers = genTwoNumResult(dataSet.a, dataSet.b);for (auto& newNumber : newNumbers) {vector<Number> newArray = dataSet.restArray;newArray.push_back(newNumber);newArrays.push_back(newArray);}}for (auto& vecNum : newArrays) resolve(vecNum);
}void resolve_puzzle()
{int a=0, b=0, c=0, d=0;cout << "请输入4个数字(以空格间隔)：";cin >> a >> b >> c >> d; vector<Number> vec{Number(a), Number(b), Number(c), Number(d)};Solutions = {};resolve(vec);sort(Solutions.begin(), Solutions.end());Solutions.erase(unique(Solutions.begin(), Solutions.end()), Solutions.end());for (auto& s : Solutions) cout << s << " = " << TARGET_NUMBER << endl;cout << "总共有 " << Solutions.size() << " 种方法：" << endl;
}int main()
{while (true) {resolve_puzzle();char answer = 'N';cout << "要继续吗？[Y|N]:";cin >> answer; if (answer == 'Y' || answer == 'y') continue;else break;}return 0;
}

运行效果如下：

请输入4个数字(以空格间隔)：4 4 3 3
((4*3)+(4*3)) = 24
(3*((4*3)-4)) = 24
总共有 2 种方法：
要继续吗？[Y|N]:y
请输入4个数字(以空格间隔)：5 5 5 1
(5*(5-(1/5))) = 24
总共有 1 种方法：
要继续吗？[Y|N]:n

不知道程序是否还有效率提高的地方。再想想。
有兴趣的读者可以试着把程序改成任意多个数字计算任意数字。

(END)