所谓24点，就是甩出几个整数，整数之间没有固定的前后顺序，给它们添加上加减乘除括号等，形成一条式子，最后运算结果等于24。很自然的想法，就是祭出表达式树。但24点只是一个小程序，用表达式树来解决，实在有点大材小用了，太委屈表达式树了，所以坚决抵制。
浏览各网友们的24点文章,发现大多数都在用最笨拙的穷举法写程序，或者是先搞成字符串，然后再对字符串求值，毫无新意，代码风格也差，都是四五重循环，难以扩充。用穷举法也没什么不好，但是，就算是穷举，也要穷举得漂漂亮亮，虽不能遗漏，但也不要重复，然后代码中也不能写死了，要保持一定的扩充性。不过得承认，不管怎么样，他们终究还是写出了24点的代码。
24点粗看起来似乎有点棘手。但很容易就可以发现一种很自然的方法，假如4个整数参与24点了，那么就从中取出两个数，进行加减乘除之后合成一个数，放回去，于是4个数变成3个数，再用同样的办法使这每一排3个数的组合变成两个数，最后就只剩下两个数，稍一运算，很容易就可以判断两个数能否凑成24。很容易就看得出来，这属回溯法，最适合写成递归的形式。但是，这一次的递归，要用代码表达出来，却着实有点不容易。不过，只要有了算法，总是有办法写成代码。为了加深难度，也为效率，我也不打算在代码中用到递归。
一般来说，回溯法属深度优先搜索法，它从问题领域中选取一个状态作为当前节点，进行某一种运算之后，形成下一级的状态，作为节点，再进行某种运算，再形成下下级的状态，作为根据地，再尝试新的节点，直到没有可用的节点了，称为叶子，就判断此时的状态是否满足问题的解。不满足，退回父节点，进行运算，进入下一级的状态，继续深度搜索。如果父节点无法进入新的状态，那么只好退回祖父节点，进行同样的操作。所以回溯算法的关键，在于新状态的运算代码，和各级节点的保存恢复代码。
再看看24点的问题，为便于行文，假设只有4个数参与运算。先来考察第一级状态的节点数量。首先，从4个数中任意取出两个数，共有C(4，2) = 6 种组合，两个数a和b，利用加减乘除和交换位置，可以凑出6个结果，分别为a+b，a*b，b-a，a/b，a-b，b/a。于是，第一级状态就有36节点。同理类推，第二级状态有C(3，2)*6，第三级状态有C(2，2)*6，没有第四级了，第三级的节点，全部都是叶子，都要判断。这意味着，24点算法中，存在36*18*6片叶子需要判断。此外，24点中，4个数的状态级数为3，可以预料到24点中状态的级数比输入参数的数目少1，你应该知道WHY的。
由以上分析可知，每一级的状态，由3个参数决定，分别是第1个数a、第2个数b和运算符号。运算符号取值范围为0-5，分别表示a+b，a-b，a*b，a/b，b-a，b/a这6种运算。这3个参数是一个整体，代码中用Step来表示，分别为nFst，nSnd，nOper。
……
忽略了思考过程，下面简单说明代码结构。CGame24是主类，用以玩出24点游戏的解。其成员函数CalcNextResult()在内部状态中用输入的数构造出一个最终的表达式，这个表达式可能是正确的解，也可能不是。而Play()则通过调用不停地调用CalcNextResult()以尝试得到一个正确的解。Express()则将表达式表示成字符串的形式。m_Nums用以储存原始的输入数据和中间运算结果，其中最后的一个数为表达式的最终运算结果。m_Flags用以指示m_Nums中的数是否已参与表达式中，以阻止同一个数多次进入表达式中。
于是Step中的nFst，nSnd为m_Nums中的数的索引，很明显，由于是组合关系，所以nSnd必将大于nFst。Step中还有一个nNext的变量，指向的是nSnd的下一个可用的索引，当nOper为最后一种运算时，nSnd就要进入到下一个位置了，也就是被赋予nNext的值。如果nNext没有可用的值时，就表示要改变nFst的下标了。本来nNext的出现是为了将代码写得好看一点而硬造出来的一个变量，但不料在后面，却发挥了很重要的作用，简直是假如没有它，代码就没法编了。
整片程序的压力全在Step::ToNext()上，它所做的事情，不过是为了使状态进入下一个状态中。但是其实现，却异常复杂，要考虑组合的各种可能的情况，甚至还要考虑除数是否为0。承担了太多的职责，但是我也想不出更好的方式，也不打算再思考了。
好吧，我也承认代码写得异常糟糕，不过，这只是玩具代码，原本就不愿精雕细刻，它还存在好多不足之处，比如输出结果中，有时会加入多余的括号，这个问题还能解决。然后，它还不够智能，遍历出来的一些解，其本质上看还是相同，这个的解决就很有点难度了。此外，按抽象的观点来看，回溯算法其实相当于一个容器，它的循环遍历叶子节点或者解，可看成迭代器，这种思路，完全可以表达成C++的代码等等。如果读者愿意优化，请将优化后的结果发给在下，在下也很想瞅瞅。其实，我想说的是，就算老夫亲自操刀，也不见得就胜过一众宵小了，惭愧。
算法这东西，现实中用得很少，高效复杂的算法自然有人在研究，我们只要注意将代码写得清晰一点就好了。不过，话又说回来，经过各种算法狂轰滥炸后的大脑，编出来的代码，貌似比没有经过算法折磨过的人，似乎总是要强一点。
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <utility>
#include <iostream>
using namespace std;
unsigned int gcd(unsigned int x, unsigned int y)
{
unsigned int nTimes=0;
for (; 0 == (x&1) && 0 == (y&1); x>>=1, y>>=1)
++nTimes;
if (x < y)
swap(x, y);
while (y > 0)
{
for (; 0 == (x & 1 );x >>= 1 )
;
if (x < y)
swap(x, y);
x -= y;
if (x < y)
swap(x, y);
}
return x << nTimes;
}
class CRational
{
public:
CRational(int nNumberator=0, int nDenominator=1)
: m_nNum(nNumberator), m_nDe(nDenominator)
{
assert(nDenominator != 0);
standarlize();
}
int Numberator()const { return m_nNum;}
int Denominator()const { return m_nDe;}
CRational& operator+=(const CRational& _Right)
{
m_nNum = m_nNum*_Right.m_nDe + _Right.m_nNum*m_nDe;
m_nDe *= _Right.m_nDe;
standarlize();
return *this;
}
CRational& operator-=(const CRational& _Right)
{
m_nNum = m_nNum*_Right.m_nDe - _Right.m_nNum*m_nDe;
m_nDe *= _Right.m_nDe;
standarlize();
return *this;
}
CRational& operator*=(const CRational& _Right)
{
m_nNum *= _Right.m_nNum;
m_nDe *= _Right.m_nDe;
standarlize();
return *this;
}
CRational& operator/=(const CRational& _Right)
{
assert(_Right.Denominator() != 0);
m_nNum *= _Right.m_nDe;
m_nDe *= _Right.m_nNum;
standarlize();
return *this;
}
private:
void standarlize()
{
if (m_nDe < 0)
{
m_nDe = -m_nDe;
m_nNum = -m_nNum;
}
int nGcd = gcd(abs(m_nNum), m_nDe);
m_nNum /= nGcd;
m_nDe /= nGcd;
}
int m_nNum;
int m_nDe;
};
ostream& operator << (ostream& out, const CRational& rat)
{
cout << rat.Numberator();
if (rat.Denominator() != 1)
cout << "/" << rat.Denominator();
return out;
}
CRational operator-(const CRational& _Left, const CRational& _Right)
{
CRational _Tmp(_Left);
return _Tmp -= _Right;
}
CRational operator+(const CRational& _Left, const CRational& _Right)
{
CRational _Tmp(_Left);
return _Tmp += _Right;
}
CRational operator*(const CRational& _Left, const CRational& _Right)
{
CRational _Tmp(_Left);
return _Tmp *= _Right;
}
CRational operator/(const CRational& _Left, const CRational& _Right)
{
CRational _Tmp(_Left);
return _Tmp /= _Right;
}
bool operator==(const CRational& _Left, const CRational& _Right)
{
return _Left.Numberator()==_Right.Numberator() && _Left.Denominator()==_Right.Denominator();
}
enum OperType{ OPER_ADD, OPER_SUB1, OPER_MUL, OPER_DIV1, OPER_SUB2, OPER_DIV2};
const char* g_sOPER_SYMBOL = "+-*/-/";
class CGame24
{
public:
CGame24(int nRes, int* pNums, int nLen);
bool Play();
bool CalcNextResult();
size_t Express(char* pExp);
private:
struct Step
{
char nOper;
char nFst;
char nSnd;
char nNext;
void ToNext(bool* pFlags, const CRational* pNums, int nMax);
bool HasNext(const bool* pFlags, int nMax)
{
if (nNext >= nMax)
{
int nCount = 0;
for (char i = nFst+1; i < nSnd && nCount<2; i++)
{
if (!pFlags[i])
nCount++;
}
return nCount == 2;
}
return true;
}
void Discard(bool* pFlags)
{
pFlags[nFst] = false;
pFlags[nSnd] = false;
nFst = 0;
nSnd = 0;
nNext = 0;
}
};
size_t buildExpress(char* pExp, char nStep, char nSuperOper);
enum {_nSIZE = 100};
CRational m_Nums[_nSIZE*2];
bool m_Flags[_nSIZE*2];
Step m_Steps[_nSIZE];
int m_nRes;
char m_nLen;
char m_nCur;
};
void CGame24::Step::ToNext(bool* pFlags, const CRational* pNums, int nMax)
{
assert(HasNext(pFlags, nMax));
if (nNext == nMax)
{
pFlags[nFst] = false;
pFlags[nSnd] = false;
nOper = 0;
nNext = 0;
nFst++;
nSnd = nFst;
}
if (nFst >= nSnd)
{
for (; nFst<nMax-1 && pFlags[nFst]; nFst++)
;
nOper = 0;
pFlags[nFst] = true;
nSnd = nFst;
for (nNext = nFst+1; nNext<nMax && pFlags[nNext]; nNext++)
;
assert (nNext != nMax);
}
if (nNext > nSnd)
{
assert(!pFlags[nNext]);
if (nSnd != nFst)
pFlags[nSnd] = false;
nSnd = nNext;
pFlags[nSnd] = true;
nOper = 0;
return;
}
nOper++;
if (nOper==OPER_DIV1 && pNums[nSnd].Numberator()==0)
nOper++;
char nNextOper = nOper+1;
if (nNextOper>OPER_MUL)
{
if (nNextOper == OPER_DIV1 && pNums[nSnd].Numberator()==0)
nNextOper++;
if (nNextOper == OPER_DIV2 && pNums[nFst].Numberator()==0)
nNextOper++;
}
if (nNextOper > OPER_DIV2)
{
for (nNext=nSnd+1; nNext<nMax && pFlags[nNext]; nNext++)
;
}
}
CRational OperateRationals(const CRational& fst, const CRational& snd, char nOper)
{
switch (nOper)
{
case OPER_ADD: return fst + snd;
case OPER_SUB1: return fst - snd;
case OPER_SUB2: return snd - fst;
case OPER_MUL: return fst * snd;
case OPER_DIV1:
assert (snd.Numberator() != 0);
return fst/snd;
case OPER_DIV2:
assert (fst.Numberator() != 0);
return snd/fst;
}
assert (false);
return 0;
}
CGame24::CGame24(int nRes, int* pNums, int nLen)
{
assert(nLen > 0 && nLen < _nSIZE);
m_nRes = nRes;
for (int i=0; i<nLen; i++)
m_Nums[i] = pNums[i];
memset(m_Flags, 0, sizeof(m_Flags));
memset(m_Steps, 0, sizeof(m_Steps));
m_nLen = static_cast<char>(nLen);
m_nCur = 0;
}
bool CGame24::CalcNextResult()
{
while (m_nCur >= 0 && !m_Steps[m_nCur].HasNext(m_Flags, m_nLen+m_nCur))
m_Steps[m_nCur--].Discard(m_Flags);
if (m_nCur < 0)
return false;
while (m_nCur < m_nLen-1)
{
m_Steps[m_nCur].ToNext(m_Flags, m_Nums, m_nLen+m_nCur);
const Step& step = m_Steps[m_nCur];
m_Nums[m_nLen+m_nCur] = OperateRationals(m_Nums[step.nFst], m_Nums[step.nSnd], step.nOper);
m_nCur++;
}
m_nCur--;
return true;
}
bool CGame24::Play()
{
while (CalcNextResult())
{
if (m_Nums[m_nLen+m_nCur] == m_nRes)
return true;
}
return false;
}
size_t CGame24::Express(char* pExp)
{
size_t len = buildExpress(pExp, m_nCur, OPER_ADD); // 加法的运算级别最低
pExp[len] = 0;
return len;
}
bool NeedParentheses(char nSuperOper, char nSubOper)
{
assert(nSuperOper <= OPER_DIV2);
assert(nSubOper <= OPER_DIV2);
static const char g_ACTUAL_OPER[] = {OPER_ADD, OPER_SUB1, OPER_MUL, OPER_DIV1, OPER_SUB1, OPER_DIV1};
nSuperOper = g_ACTUAL_OPER[nSuperOper];
nSubOper = g_ACTUAL_OPER[nSubOper];
return (nSuperOper>nSubOper) || (nSuperOper==nSubOper && (nSubOper==OPER_SUB1 || nSuperOper==OPER_DIV1));
}
size_t CGame24::buildExpress(char* pExp, char nStep, char nSuperOper)
{
assert(nStep <= m_nCur);
char* sPos = pExp;
const Step& step = m_Steps[nStep];
char nFst = step.nFst;
char nSnd = step.nSnd;
char nOper = step.nOper;
if(step.nOper==OPER_SUB2 || step.nOper==OPER_DIV2)
swap(nFst, nSnd);
bool bParentheses = NeedParentheses(nSuperOper, nOper);
if (bParentheses)
*sPos++ = '(';
if (nFst >= m_nLen)
sPos += buildExpress(sPos, nFst-m_nLen, nOper);
else
sPos += sprintf(sPos, ("%d"), m_Nums[nFst].Numberator());
*sPos++ = g_sOPER_SYMBOL[nOper];
if (nSnd >= m_nLen)
sPos += buildExpress(sPos, nSnd-m_nLen, nOper);
else
sPos += sprintf(sPos, ("%d"), m_Nums[nSnd].Numberator());
if (bParentheses)
*sPos++ = ')';
return sPos-pExp;
}
int main()
{
char sExpress[256] = { 0 };
int Nums[] = {1, 2, 3, 4, 5};
CGame24 game(24, Nums, 5);
while (game.Play())
{
game.Express(sExpress);
cout << sExpress << endl;
}
return 0;
}