回溯法的24点问题.doc

#include#includeusing namespace std;#includeconst double PRECISION = 1E-6; /精度常量const int COUNT_OF_NUMBER = 4; /算24点的自然数个数const int NUMBER_TO_BE_CAL = 24;bool flag=false;class RationalNumber /定义有理数类（分子、分母） protected: int numerator,denominator; /numerator：分子，denominator：分母 bool inf;/整数假 protected: int gcd(int a,int b) /求a和b的最大公约数 int temp; if(anumerator=numerator; this-denominator=denominator; Simplify(); virtual RationalNumber() void Simplify() if(denominator=1) inf=false; else if(numerator=0) denominator=1; inf=false; else int k=gcd(abs(numerator),abs(denominator); numerator/=k; denominator/=k; if(denominator=1) inf=false; else inf=true; RationalNumber operator+(const RationalNumber& b) const RationalNumber result; result.denominator=this-denominator*b.denominator; result.numerator=this-numerator*b.denominator+this-denominator*b.numerator; result.Simplify(); return result; RationalNumber operator-(const RationalNumber& b) const / 。 RationalNumber result; result.denominator=this-denominator*b.denominator; result.numerator=this-numerator*b.denominator-this-denominator*b.numerator; result.Simplify(); return result; RationalNumber operator*(const RationalNumber& b) const / 。 RationalNumber result; result.denominator=this-denominator*b.denominator; result.numerator=this-numerator*b.numerator; result.Simplify(); return result; RationalNumber operator/(const RationalNumber& b) const RationalNumber result; result.denominator=this-denominator*b.numerator; result.numerator=this-numerator*b.denominator; result.Simplify(); return result; RationalNumber& operator=(const RationalNumber& b) denominator=b.denominator; numerator=b.numerator; return (*this); RationalNumber& operator=(int b) denominator=1; numerator=b; return (*this); int Numerator() const return numerator; int Denominator() const return denominator; string strshow() string str; char buffer20; itoa(numerator,buffer,10); str=buffer; if(denominator!=1) itoa(denominator,buffer,10); str=str+/+buffer; return str; ;RationalNumber numberCOUNT_OF_NUMBER;string expressionCOUNT_OF_NUMBER;bool Search(int n) /递归函数 if (n=1) if (fabs(number0.Numerator ()*1.0/number0.Denominator ()-NUMBER_TO_BE_CAL)PRECISION) coutexpression0endl; /输出表达式ue flag=true; return true; else / flag=false; return false; int i,j,k; RationalNumber temp; for ( i=0;in;i+) if(n=4) temp=numberi-numberi+1; if(temp.Numerator ()=0) continue; for (j=i+1;jn;j+) if(n=4) for(k=i+1;kj;k+) temp=numberj-numberk; if(temp.Numerator ()=0) break; if(k=0) / Search(n-1); if (Search(n-1)&n!=4) numberi=a; numberj=b; expressioni=expa; expressionj=expb; return true; expressioni=(+expb+-+expa+); numberi=b-a; if(numberi.Numerator() =0) / Search(n-1); if (Search(n-1)&n!=4) numberi=a; numberj=b; expressioni=expa; expressionj=expb; return true; /乘法 expressioni=(+expa+*+expb+); numberi=a*b; / Search(n-1); if (Search(n-1)&n!=4) numberi=a; numberj=b; expressioni=expa; expressionj=expb; return true; /除法也有两种情况a/b和b/a if (b.Numerator()!=0) expressioni=(+expa+/+expb+); numberi=a/b; / Search(n-1); if (Search(n-1)&n!=4) numberi=a; numberj=b; expressioni=expa; expressionj=expb; return true; if (a.Numerator()!=0) expressioni=(+expb+/+expa+); numberi=b/a; / Search(n-1); if (Search(n-1)&n!=4) numberi=a; numberj=b; expressioni=expa; expressionj=expb; return true; /本轮调用完毕后，用a,b,expa,expb将数组number和expression恢复原状 numberi=a; numberj=b; expressioni=expa; expressionj=expb; return false;int main() int i,x; char xx; do cout请输入四个整数:; flag=false; for (i=0;ix; numberi=x; itoa(x,buffer,10); /itoa():将一个10进制的integer数转换为string类型 /即：把输入的int型操作数x，转变成可以放在buffer中的string类型 expressioni=buffer; /用expressioni指针指向buffer数组空间的起始位置 Search(4); if(flag=false) cout无解n; coutxx; while(xx=Y|xx=y); return 0;#include#includeusing namespace std;#includeconst double PRECISION = 1E-6; const int COUNT_OF_NUMBER = 4; const int NUMBER_TO_BE_CAL = 24;bool flag=false;class RationalNumber protected: int numerator,denominator; bool inf; protected: int gcd(int a,int b) int temp; if(anumerator=numerator; this-denominator=denominator; Simplify(); virtual RationalNumber() void Simplify() if(denominator=1) inf=false; else if(numerator=0) denominator=1; inf=false; else int k=gcd(abs(numerator),abs(denominator); numerator/=k; denominator/=k; if(denominator=1) inf=false; else inf=true; RationalNumber operator+(const RationalNumber& b) const RationalNumber result; result.denominator=this-denominator*b.denominator; result.numerator=this-numerator*b.denominator+this-denominator*b.numerator; result.Simplify(); return result; RationalNumber operator-(const RationalNumber& b) const / 。 RationalNumber result; result.denominator=this-denominator*b.denominator; result.numerator=this-numerator*b.denominator-this-denominator*b.numerator; result.Simplify(); return result; RationalNumber operator*(const RationalNumber& b) const / 。 RationalNumber result; result.denominator=this-denominator*b.denominator; result.numerator=this-numerator*b.numerator; result.Simplify(); return result; RationalNumber operator/(const RationalNumber& b) const RationalNumber result; result.denominator=this-denominator*b.numerator; result.numerator=this-numerator*b.denominator; result.Simplify(); return result; RationalNumber& operator=(const RationalNumber& b) denominator=b.denominator; numerator=b.numerator; return (*this); RationalNumber& operator=(int b) denominator=1; numerator=b; return (*this); int Numerator() const return numerator; int Denominator() const return denominator; string strshow() string str; char buffer20; itoa(numerator,buffer,10); str=buffer; if(denominator!=1) itoa(denominator,buffer,10); str=str+/+buffer; return str; ;RationalNumber numberCOUNT_OF_NUMBER;string expressionCOUNT_OF_NUMBER;bool Search(int n) if (n=1) if (fabs(number0.Numerator ()*1.0/number0.Denominator ()-NUMBER_TO_BE_CAL)PRECISION) coutexpression0endl; flag=true; return true; else / flag=false; return false; int i,j,k; RationalNumber temp; for ( i=0;in;i+) if(n=4) temp=numberi-numberi+1; if(temp.Numerator ()=0) continue; for (j=i+1;jn;j+) if(n=4) for(k=i+1;kj;k+) temp=numberj-numberk; if(temp.Numerator ()=0) break; if(k=0) if (Search(n-1)&n!=4) numberi=a; numberj=b; expressioni=expa; expressionj=expb; return true; expressioni=(+expb+-+expa+); numberi=b-a; if(numberi.Numerator() =0) if (Search(n-1)&n!=4) numberi=a; numberj=b; expressioni=expa; expressionj=expb; return true; expression