所謂24點(diǎn)，就是甩出幾個整數(shù)，整數(shù)之間沒有固定的前后順序，給它們添加上加減乘除括號等，形成一條式子，最后運(yùn)算結(jié)果等于24。很自然的想法，就是祭出表達(dá)式樹。但24點(diǎn)只是一個小程序，用表達(dá)式樹來解決，實(shí)在有點(diǎn)大材小用了，太委屈表達(dá)式樹了，所以堅決抵制。
瀏覽各網(wǎng)友們的24點(diǎn)文章,發(fā)現(xiàn)大多數(shù)都在用最笨拙的窮舉法寫程序，或者是先搞成字符串，然后再對字符串求值，毫無新意，代碼風(fēng)格也差，都是四五重循環(huán)，難以擴(kuò)充。用窮舉法也沒什么不好，但是，就算是窮舉，也要窮舉得漂漂亮亮，雖不能遺漏，但也不要重復(fù)，然后代碼中也不能寫死了，要保持一定的擴(kuò)充性。不過得承認(rèn)，不管怎么樣，他們終究還是寫出了24點(diǎn)的代碼。
24點(diǎn)粗看起來似乎有點(diǎn)棘手。但很容易就可以發(fā)現(xiàn)一種很自然的方法，假如4個整數(shù)參與24點(diǎn)了，那么就從中取出兩個數(shù)，進(jìn)行加減乘除之后合成一個數(shù)，放回去，于是4個數(shù)變成3個數(shù)，再用同樣的辦法使這每一排3個數(shù)的組合變成兩個數(shù)，最后就只剩下兩個數(shù)，稍一運(yùn)算，很容易就可以判斷兩個數(shù)能否湊成24。很容易就看得出來，這屬回溯法，最適合寫成遞歸的形式。但是，這一次的遞歸，要用代碼表達(dá)出來，卻著實(shí)有點(diǎn)不容易。不過，只要有了算法，總是有辦法寫成代碼。為了加深難度，也為效率，我也不打算在代碼中用到遞歸。
一般來說，回溯法屬深度優(yōu)先搜索法，它從問題領(lǐng)域中選取一個狀態(tài)作為當(dāng)前節(jié)點(diǎn)，進(jìn)行某一種運(yùn)算之后，形成下一級的狀態(tài)，作為節(jié)點(diǎn)，再進(jìn)行某種運(yùn)算，再形成下下級的狀態(tài)，作為根據(jù)地，再嘗試新的節(jié)點(diǎn)，直到?jīng)]有可用的節(jié)點(diǎn)了，稱為葉子，就判斷此時的狀態(tài)是否滿足問題的解。不滿足，退回父節(jié)點(diǎn)，進(jìn)行運(yùn)算，進(jìn)入下一級的狀態(tài)，繼續(xù)深度搜索。如果父節(jié)點(diǎn)無法進(jìn)入新的狀態(tài)，那么只好退回祖父節(jié)點(diǎn)，進(jìn)行同樣的操作。所以回溯算法的關(guān)鍵，在于新狀態(tài)的運(yùn)算代碼，和各級節(jié)點(diǎn)的保存恢復(fù)代碼。
再看看24點(diǎn)的問題，為便于行文，假設(shè)只有4個數(shù)參與運(yùn)算。先來考察第一級狀態(tài)的節(jié)點(diǎn)數(shù)量。首先，從4個數(shù)中任意取出兩個數(shù)，共有C(4，2) = 6 種組合，兩個數(shù)a和b，利用加減乘除和交換位置，可以湊出6個結(jié)果，分別為a+b，a*b，b-a，a/b，a-b，b/a。于是，第一級狀態(tài)就有36節(jié)點(diǎn)。同理類推，第二級狀態(tài)有C(3，2)*6，第三級狀態(tài)有C(2，2)*6，沒有第四級了，第三級的節(jié)點(diǎn)，全部都是葉子，都要判斷。這意味著，24點(diǎn)算法中，存在36*18*6片葉子需要判斷。此外，24點(diǎn)中，4個數(shù)的狀態(tài)級數(shù)為3，可以預(yù)料到24點(diǎn)中狀態(tài)的級數(shù)比輸入?yún)?shù)的數(shù)目少1，你應(yīng)該知道WHY的。
由以上分析可知，每一級的狀態(tài)，由3個參數(shù)決定，分別是第1個數(shù)a、第2個數(shù)b和運(yùn)算符號。運(yùn)算符號取值范圍為0-5，分別表示a+b，a-b，a*b，a/b，b-a，b/a這6種運(yùn)算。這3個參數(shù)是一個整體，代碼中用Step來表示，分別為nFst，nSnd，nOper。
……
忽略了思考過程，下面簡單說明代碼結(jié)構(gòu)。CGame24是主類，用以玩出24點(diǎn)游戲的解。其成員函數(shù)CalcNextResult()在內(nèi)部狀態(tài)中用輸入的數(shù)構(gòu)造出一個最終的表達(dá)式，這個表達(dá)式可能是正確的解，也可能不是。而Play()則通過調(diào)用不停地調(diào)用CalcNextResult()以嘗試得到一個正確的解。Express()則將表達(dá)式表示成字符串的形式。m_Nums用以儲存原始的輸入數(shù)據(jù)和中間運(yùn)算結(jié)果，其中最后的一個數(shù)為表達(dá)式的最終運(yùn)算結(jié)果。m_Flags用以指示m_Nums中的數(shù)是否已參與表達(dá)式中，以阻止同一個數(shù)多次進(jìn)入表達(dá)式中。
于是Step中的nFst，nSnd為m_Nums中的數(shù)的索引，很明顯，由于是組合關(guān)系，所以nSnd必將大于nFst。Step中還有一個nNext的變量，指向的是nSnd的下一個可用的索引，當(dāng)nOper為最后一種運(yùn)算時，nSnd就要進(jìn)入到下一個位置了，也就是被賦予nNext的值。如果nNext沒有可用的值時，就表示要改變nFst的下標(biāo)了。本來nNext的出現(xiàn)是為了將代碼寫得好看一點(diǎn)而硬造出來的一個變量，但不料在后面，卻發(fā)揮了很重要的作用，簡直是假如沒有它，代碼就沒法編了。
整片程序的壓力全在Step::ToNext()上，它所做的事情，不過是為了使?fàn)顟B(tài)進(jìn)入下一個狀態(tài)中。但是其實(shí)現(xiàn)，卻異常復(fù)雜，要考慮組合的各種可能的情況，甚至還要考慮除數(shù)是否為0。承擔(dān)了太多的職責(zé)，但是我也想不出更好的方式，也不打算再思考了。
好吧，我也承認(rèn)代碼寫得異常糟糕，不過，這只是玩具代碼，原本就不愿精雕細(xì)刻，它還存在好多不足之處，比如輸出結(jié)果中，有時會加入多余的括號，這個問題還能解決。然后，它還不夠智能，遍歷出來的一些解，其本質(zhì)上看還是相同，這個的解決就很有點(diǎn)難度了。此外，按抽象的觀點(diǎn)來看，回溯算法其實(shí)相當(dāng)于一個容器，它的循環(huán)遍歷葉子節(jié)點(diǎn)或者解，可看成迭代器，這種思路，完全可以表達(dá)成C++的代碼等等。如果讀者愿意優(yōu)化，請將優(yōu)化后的結(jié)果發(fā)給在下，在下也很想瞅瞅。其實(shí)，我想說的是，就算老夫親自操刀，也不見得就勝過一眾宵小了，慚愧。
算法這東西，現(xiàn)實(shí)中用得很少，高效復(fù)雜的算法自然有人在研究，我們只要注意將代碼寫得清晰一點(diǎn)就好了。不過，話又說回來，經(jīng)過各種算法狂轟濫炸后的大腦，編出來的代碼，貌似比沒有經(jīng)過算法折磨過的人，似乎總是要強(qiáng)一點(diǎn)。
#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); // 加法的運(yùn)算級別最低
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;
}