《24点游戏》

　《编程之美》1.16节《24点游戏》&＃xff0c;这个不多说了&＃xff0c;大家从小玩到大的。书中解法一用了枚举的方法&＃xff0c;依次求解出所有7680种表达式的值&＃xff1b;解法二用了分治的思想来优化算法&＃xff0c;我写的算法就是根据解法二来的&＃xff0c;书中的伪代码只能判断N个数能否求出24&＃xff0c;而我改进之后就可以输出满足题意的表达式了。

　　算法中我用到C&＃43;&＃43; STL中的set容器&＃xff0c;因为set中的元素都是非重的。

//实现N个数通过简单的运算得到结果24.

CODE

//24Game
//2010-01-17
//by roovent

#include
#include
#include
#include
#define N 4
#define M (1<#define TARGET 24

using namespace std;

struct Element
{
    double num;
    string expression;

    friend bool operator<(const Element& a, const Element& b)
    {
        return a.num     }
};

//--全局变量
set result[M];
//--全局变量结束

set Process(const int x, int* nums)
{
    set s;
    for(int i &＃61; 1; i     {  
        if((i|x) &＃61;&＃61; x && x-i>i) //i是x的子集&＃xff0c;x-i是其补集&＃xff0c;确保子集与其补集不重复运算
        {
            for(set::iterator p &＃61; result[i].begin(); p !&＃61; result[i].end(); &＃43;&＃43;p)
            {
                for(set::iterator q &＃61; result[x-i].begin(); q !&＃61; result[x-i].end(); &＃43;&＃43;q)
                {
                    Element e;
                    double dbA &＃61; (*p).num;
                    double dbB &＃61; (*q).num;
                    string strA &＃61; (*p).expression;
                    string strB &＃61; (*q).expression;

                    e.num &＃61; dbA &＃43; dbB;
                    e.expression &＃61; "(" &＃43; strA &＃43; " &＃43; " &＃43; strB &＃43; ")";
                    s.insert(e);

                    e.num &＃61; dbA - dbB;
                    e.expression &＃61; "(" &＃43; strA &＃43; " - " &＃43; strB &＃43; ")";
                    s.insert(e);

                    e.num &＃61; dbB - dbA;
                    e.expression &＃61; "(" &＃43; strB &＃43; " - " &＃43; strA &＃43; ")";
                    s.insert(e);

                    e.num &＃61; dbA * dbB;
                    e.expression &＃61; "(" &＃43; strA &＃43; " * " &＃43; strB &＃43; ")";
                    s.insert(e);
                   
                    if(dbB !&＃61; 0)
                    {
                        e.num &＃61; dbA / dbB;
                        e.expression &＃61; "(" &＃43; strA &＃43; " / " &＃43; strB &＃43; ")";
                        s.insert(e);
                    }
                   
                    if(dbA !&＃61; 0)
                    {
                        e.num &＃61; dbB / dbA;
                        e.expression &＃61; "(" &＃43; strB &＃43; " / " &＃43; strA &＃43; ")";
                        s.insert(e);
                    }
                }
            }
        }
    }
    return s;
}

bool Solve(int* nums)
{
    for(int i &＃61; 0; i     {
        result[i].clear();
    }

    for(int i &＃61; 0; i     {
        stringstream ss;
        ss<        Element e &＃61; {nums[i], ss.str()};
        result[1<    }

    for(int i &＃61; 1; i     {
        if(result[i].empty())
            result[i] &＃61; Process(i, nums);
    }

    Element e &＃61; {TARGET, ""};
    return result[M-1].find(e) !&＃61; result[M-1].end();
}

int main()
{
    int nums[N] &＃61;
        {5,5,5,1};
        //{3,3,7,7};
        //{3,3,8,8};
        //{1,4,5,6};
        //{3,8,8,10};
        //{4,4,10,10};
        //{9,9,6,2};
   
    cout<<"Problem: ";
    for(int i &＃61; 0; i     {
        cout<    }
    cout<

    if(Solve(nums))
    {
        Element e &＃61; {TARGET, ""};
        cout<<"Solution: "<<(*(result[M-1].find(e))).expression <    }
    else
    {
        cout<<"No Solution"<    }
    return 0;
}