编程之美1.16——24点游戏

问题：
给玩家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++)
    {

补充：软件开发 , C++ ,