算24游戏的C++实现

//--------------------------------------------------------
// “算24”游戏：若干个数，通过 + - * / 四则运算，求出等于目标数值的表达式。
//
// 算法： (引用 chai2010@linuxsir.org)
// 把输入的数据看做一个集合，集合中有n个元素。
// 从集合中任取2个元素分别进行+-*/运算，
// 把运算的结果替换n集合中取出的2个元素
// 现在集合中有(n-1)个元素
// 对含有(n-1)个元素的新集合递归进行上述判断
// 如果集合只剩下1个元素且该，则就是最终结果
//
// 实现： C++， vector， 递归
//
//--------------------------------------------------------
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

#define GET_EXPR(des,src) do{    \
    if(src.expr.str().empty())      \
        des.expr<<src.data;      \
    else des.expr<<src.expr.str();\
}while(0)


float  TARGET=24;

template<typename T> class element;

template<typename T>
element<T> operator+(element<T> & rhs1, element<T> & rhs2)
{
    element<T> ret(rhs1.data+rhs2.data);
   
    ret.expr<<"(";
    GET_EXPR(ret,rhs1);
    ret.expr<<"+";
    GET_EXPR(ret,rhs2);
    ret.expr<<")";
    return ret;
}

template<typename T>
element<T> operator-(element<T> & rhs1, element<T> & rhs2)
{
    element<T> ret(rhs1.data-rhs2.data);
  
   
    ret.expr<<"(";
    GET_EXPR(ret,rhs1);
    ret.expr<<"-";
    GET_EXPR(ret,rhs2);
    ret.expr<<")";
    return ret;
}

template<typename T>
element<T> operator*(element<T> & rhs1, element<T> & rhs2)
{
    element<T> ret(rhs1.data*rhs2.data);
  
   
    ret.expr<<"(";
    GET_EXPR(ret,rhs1);  
    ret.expr<<"*";
    GET_EXPR(ret,rhs2);
    ret.expr<<")";
    return ret;
}

template<typename T>
element<T> operator/(element<T> & rhs1, element<T> & rhs2)
{
    if(rhs2.data){
        element<T> ret(rhs1.data/rhs2.data);
     
       
        ret.expr<<"(";
        GET_EXPR(ret,rhs1);
        ret.expr<<"/";
        GET_EXPR(ret,rhs2);
        ret.expr<<")";
        return ret;
    }else{
        cerr<<"divide by 0 error!"<<endl;
        abort();
    }
}

template<typename T>
vector< element<T> >& cal_target( vector< element<T> >  vt )
{
    typename vector< element<T> >::iterator it,it1,it2;
    static vector< element<T> > result;
   
    if(vt.empty())return result;
    else if(vt.size()==1){
        element<T> e=vt.back();
        if(e.data==TARGET)result.push_back(e);
    }else{
        for(it1=vt.begin(); it1<vt.end()-1; it1++){
            for(it2=it1+1; it2<vt.end(); it2++){
                element<T> e1=*it1;
                element<T> e2=*it2;
                it2=vt.erase(it2); // remove 2 elements
                it1=vt.erase(it1); // CAUTION: e2 should erase first !
               
                vt.push_back(e1+e2);
                cal_target(vt);
                vt.pop_back();
               
                vt.push_back(e1-e2);
                cal_target(vt);
                vt.pop_back();
               
                vt.push_back(e2-e1);
                cal_target(vt);
                vt.pop_back();
               
                vt.push_back(e1*e2);
                cal_target(vt);
                vt.pop_back();
               
                if(e2.data){
                    vt.push_back(e1/e2);
                    cal_target(vt);
                    vt.pop_back();
                }
               
                if(e1.data){
                    vt.push_back(e2/e1);
                    cal_target(vt);
                    vt.pop_back();
                }
               
                it1=vt.insert(it1,e1);  // recover vector              
                it2=vt.insert(it2,e2);  // CAUTION: e1 should insert first !
            }
        }
    }
    return result;
}

template<typename T>
class element{
    friend element<T> operator+<>(element<T> &, element<T> &);
    friend element<T> operator-<>(element<T> &, element<T> &);
    friend element<T> operator*<>(element<T> &, element<T> &);
    friend element<T> operator/<>(element<T> &, element<T> &);
    friend vector< element<T> >& cal_target<T>(vector< element<T> > );
private:
    T data;
    ostringstream expr;
public:
    element(T const& x):data(x){ }
    element(element const& rhs):data(rhs.data){ expr<<rhs.expr.str(); }
    element& operator=(element const&);
    void show_expr() { cout<<expr.str(); }
};

template<typename T>
element<T>& element<T>::operator=(element<T> const& rhs)
{
    if(this!=&rhs){
        data=rhs.data;
        expr.str("");
        expr<<rhs.expr.str();
    }
    return *this;
}

int main()
{
    element<float> arr[]={1,2,3,4};
    TARGET=10;
    vector< element<float> > vt(arr, arr+sizeof(arr)/sizeof(arr[0]));
    vector< element<float> > result=cal_target(vt);

    vector< element<float> >::iterator it;
    if(result.empty())cout<<"impossible!"<<endl;
    else{
        for(it=result.begin();it!=result.end();it++){
            it->show_expr();
            cout<<" = "<<TARGET<<endl;
        }
        cout<<"-------------------------"<<endl;
        cout<<"solutions found: "<<result.size()<<endl;
    }
}
 

用Valgrind查找内存泄漏和无效内存访问：【上一篇】
session简介：【下一篇】