問題：
給玩家4張牌，每張牌的面值在1-13之間，允許其中有數值相同的牌，采用加、減、乘、除四則運算，允許中間運算存在小數，並且可以使用括號，但每張牌只能用一次。構造表達式，使其結果為24.
解法：
傳統的枚舉解法會產生大量重復的運算，主要有兩類重復：運算結果的重復和排列的重復。假設4張牌為3 3 8 8，我們對3 3進行一次操作（6種運算）得到6 0 0 1 1 9，其中重復的數據就是我們所說的運算結果重復，使用集合不重復性來解決。枚舉算法在枚舉時要對牌的順序進行排列，由於牌可以重復，所以產生的排列會有大量的重復(3 3) 8 8, (3 8) 3 8, (3 8) 3 8, (3 8) 3 8,(3 8) 3 8, (8 8) 3 3，這屬於排列重復，使用分治法加memo來解決。采用二進制數來表達集合和子集的概念，我們可以用一個數來表示子集中擁有哪些元素，再用這個數作為索引來找出該集合運算後產生的結果集。
[cpp]
#include <iostream>
#include <set>
#include <string>
using namespace std;
#define N 4 // 4張牌，可變
#define RES 24 // 運算結果為24，可變
#define EPS 1e-6
struct Elem
{
Elem(double r, string& i):res(r),info(i){}
Elem(double r, char* i):res(r),info(i){}
double res; // 運算出的數據
string info; // 運算的過程
bool operator<(const Elem& e) const
{
return res < e.res; // 在set的紅黑樹插入操作中需要用到比較操作
}
};
int A[N]; // 記錄N個數據
// 用二進制數來表示集合和子集的概念，0110表示集合包含第2,3個數
set<Elem> vset[1<<N]; // 包含4個元素的集合共有16個子集0-15
set<Elem>& Fork(int m)
{
// memo遞歸
if (vset[m].size())
{
return vset[m];
}
for (int i=1; i<=m/2; i++)
if ((i&m) == i)
{
set<Elem>& s1 = Fork(i);
set<Elem>& s2 = Fork(m-i);
set<Elem>::iterator cit1;
set<Elem>::iterator cit2;
// 得到兩個子集合的笛卡爾積，並對結果集合的元素對進行6種運算
for (cit1=s1.begin(); cit1!=s1.end(); cit1++)
for (cit2=s2.begin(); cit2!=s2.end(); cit2++)
{
string str;
str = "("+cit1->info+"+"+cit2->info+")";
vset[m].insert(Elem(cit1->res+cit2->res,str));
str = "("+cit1->info+"-"+cit2->info+")";
vset[m].insert(Elem(cit1->res-cit2->res,str));
str = "("+cit2->info+"-"+cit1->info+")";;
vset[m].insert(Elem(cit2->res-cit1->res,str));
str = "("+cit1->info+"*"+cit2->info+")";
vset[m].insert(Elem(cit1->res*cit2->res,str));
if (abs(cit2->res)>EPS)
{
str = "("+cit1->info+"/"+cit2->info+")";
vset[m].insert(Elem(cit1->res/cit2->res,str));
}
if (abs(cit1->res)>EPS)
{
str = "("+cit2->info+"/"+cit1->info+")";
vset[m].insert(Elem(cit2->res/cit1->res,str));
}
}
}
return vset[m];
}
int main()
{
int i;
for (i=0; i<N; i++)
cin >> A[i];
// 遞歸的結束條件
for (i=0; i<N; i++)
{
char str[10];
sprintf(str,"%d",A[i]);
vset[1<<i].insert(Elem(A[i],str));
}
Fork((1<<N)-1);
// 顯示算出24點的運算過程
set<Elem>::iterator it;
for (it=vset[(1<<N)-1].begin();
it!=vset[(1<<N)-1].end(); it++)
{
if (abs(it->res-RES) < EPS)
cout << it->info << endl;
}
}
雖然以上算法在時間復雜度上要小於窮舉法，但由於24點游戲的牌數只有4張，計算規模非常小，且上面算法由於引入了set數據結構，該數據結構的底層是一個紅黑樹，構造的耗時比較高，且訪問的復雜度O(h)要大於枚舉的O(1)，所以實際運行下，它的速度要比枚舉法更慢。下面是書中寫的枚舉算法，實際運行發現它的速度更快：
[cpp]
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
const double EPS = 1e-6;
const int NUM = 4;
const int RES = 24;
double A[NUM];
string res_str[NUM];
int times = 0;
bool process(int n)
{
// 退出條件
if (n==1)
{
if (abs(A[0]-RES)<EPS)
{
cout << res_str[0] << endl;
return true;
}
else
return false;
}
double a, b;
string expa, expb;
for (int i=0; i<n; i++)
for (int j=i+1; j<n; j++)
{
times++;
// 保存狀態（操作數i,j）
a = A[i];
b = A[j];
expa = res_str[i];
expb = res_str[j];
// 改變狀態
A[j] = A[n-1];
res_str[j] = res_str[n-1];
A[i] = a+b;
res_str[i] = '(' + expa + '+' + expb + ')';
if (process(n-1))
return true;
A[i] = a-b;
res_str[i] = '(' + expa + '-' + expb + ')';
if (process(n-1))
return true;
A[i] = b-a;
res_str[i] = '(' + expb + '-' + expa + ')';
if (process(n-1))
return true;
A[i] = a*b;
res_str[i] = '(' + expa + '*' + expb + ')';
if (process(n-1))
return true;
if (b!=0)
{
A[i] = a/b;
res_str[i] = '(' + expa + '/' + expb + ')';
if (process(n-1))
return true;
}
if (a!=0)
{
A[i] = b/a;
res_str[i] = '(' + expb + '/' + expa + ')';
if (process(n-1))
return true;
}
// 恢復狀態
A[i] = a;
A[j] = b;
res_str[i] = expa;
res_str[j] = expb;
}
return false;
}
int main()
{
for (int i=0; i<NUM; i++)
{
cin >> A[i];
char c[10];
sprintf(c,"%.0f",A[i]);
res_str[i] = c;
}
clock_t start = clock();
if (process(NUM))
cout << res_str[0] << endl;
else
cout << "failed" << endl;
clock_t duration = clock() - start;
cout << duration << endl;
}
[cpp]
