所謂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;
}