計(jì)算24點(diǎn)有不同版本，這里規(guī)定：運(yùn)用加減乘除計(jì)算四個(gè)整數(shù)使它的結(jié)果為24。當(dāng)然這個(gè)算法經(jīng)過適當(dāng)?shù)男薷倪m合所有的二元運(yùn)算符，也能計(jì)算超過四個(gè)整數(shù)。
計(jì)算24點(diǎn)的算法較簡(jiǎn)單，就是窮舉法。由于一般計(jì)算表達(dá)式含有括號(hào)，這使得窮舉無從下手。所以本文使用另一種表達(dá)式——后綴表達(dá)式。
后綴表達(dá)式就是數(shù)字放前運(yùn)算符放后的表達(dá)式。如：a+b表示為a b+，(a+b)*c-d表示為a b + c * d -。用這樣表達(dá)式可以去掉括號(hào)，這對(duì)本文的算法很關(guān)鍵。
任何一個(gè)計(jì)算24點(diǎn)的算式都可以化成7位的后綴表達(dá)式。假設(shè)給定的四個(gè)整數(shù)：a b c d。給定的運(yùn)算符號(hào)集{+,-,*,/}。首先從符號(hào)集中取出三個(gè)運(yùn)算符,然后加上a b c d。這七個(gè)單位的每一個(gè)排列都可以當(dāng)成一個(gè)后綴表達(dá)式：或者是不合法的，或者是合法的。窮舉并計(jì)算這樣的排列，就可找出答案。
上面的方法是先取定7個(gè)單位，然后判斷這7個(gè)單位組成的表達(dá)式是否合法。換一種思路，先取定一個(gè)合法的表達(dá)式，即確定數(shù)字和符號(hào)的位置，然后確定7個(gè)單位，對(duì)應(yīng)數(shù)字和符號(hào)的位置。
這兩種枚舉方法都可行，第二種會(huì)快一些，它把判斷后綴表達(dá)式合法性放在最外層循環(huán)，從而省去了不少的判斷。
注：這個(gè)里用的枚舉集合的方法參見另一篇文章《從集合中枚舉子集》。
具體實(shí)現(xiàn)見代碼。
編譯方式：
g++ Calc24.cpp SetIter.cpp 得到第一種方法。
g++ Calc24.cpp SetIter.cpp -DCALC24_ADV 得到第二種方法。