华为OJ机试题 绝对值

#include<iostream> using namespace std; #include<string> #include<stdlib.h> const double PRECISION = 1E-6; //精度常量 const int COUNT_OF_NUMBER = 4; //算24点的自然数个数 const int NUMBER_TO_BE_CAL = 24; void Swap(int &m,int &n) { int x; x=m; m=n; n=x; } class RationalNumber //定义有理数类（分子、分母） { protected: int numerator,denominator; //numerator：分子，denominator：分母 bool inf; protected: int gcd(int a,int b) //求a和b的最大公约数 { if(a==0)return b;if(b==0) return a; if(a>b) Swap(a,b); while(a>0){ int c=b%a;b=a;a=c; } return b; } public: RationalNumber() { inf=false; } RationalNumber(int n) { numerator=n; denominator=1; inf=false; } RationalNumber(int numerator,int denominator) { this->numerator=numerator; this->denominator=denominator; Simplify(); } virtual ~RationalNumber() {} void Simplify() { if(denominator==0) { inf=true; } else if(numerator==0) { denominator=1; inf=false; } else { int k=gcd(abs(numerator),abs(denominator)); numerator/=k; denominator/=k; inf=false; } } 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); } bool operator==(const RationalNumber& b) const { if((b.denominator==this->denominator)&&(b.numerator==this->numerator)) return true; return false; } bool operator==(int b) const { if((1==this->denominator)&&(b==this->numerator)) return true; return false; } bool operator!=(const RationalNumber& b) const { if(b.denominator!=this->denominator||b.numerator!=this->numerator) return true; return false; } bool operator!=(int b) const { if(1!=this->denominator||b!=this->numerator) return true; return false; } int Numerator() const { return numerator; } int Denominator() const { return denominator; } }; RationalNumber number[COUNT_OF_NUMBER]; //用数组number[]保存操作数 string expression[COUNT_OF_NUMBER]; //用数组expression[]保存算式 bool Search(int n) //递归函数 { if (n==1) { if (number[0]==NUMBER_TO_BE_CAL) //成功搜索得到24 //若number[]是double型 //也可用if (fabs(number[0]-NUMBER_TO_BE_CAL)<PRECISION) { //expression[0].erase("(") // int cot=3; // while(cot--){ // string::iterator it; // for (it =expression[0].begin(); it != expression[0].end(); ++it) // { // if ( *it == '(') // { // expression[0].erase(it); // } // } // } // int count1=3; // while(count1--){ // string::iterator it1; // for (it1 =expression[0].begin(); it1 != expression[0].end(); ++it1) // { // if ( *it1== ')') // { // expression[0].erase(it1); // } // } // } int num1=0,num2=0; char strtemp[100]; strcpy(strtemp,expression[0].c_str()); for(num1=0;num1<strlen(strtemp);num1++) { if(strtemp[num1]!='('&&strtemp[num1]!=')') { strtemp[num2++]=strtemp[num1]; } } strtemp[num2]='\0'; cout<<strtemp<<endl; /*cout<<expression[0]<<endl; //输出表达式*/ return true; } else { return false; } } for (int i=0;i<n;i++) { for (int j=i+1;j<n;j++) { RationalNumber a, b; string expa, expb; a=number[i]; //用a保存number[i] b=number[j]; //用b保存number[j] number[j]=number[n-1]; //将number[n-1]向前填入到原来number[j]的位置 expa=expression[i]; //用expa保存expression[i] expb=expression[j]; //用expb保存expression[j] expression[j]=expression[n-1]; //将expression[n-1]向前填入到原来expression[j]的位置 //因为下一层递归调用search(n-1)将仅对下标为0~n-2的数进行操作了 //加法 expression[i]='('+expa+'+'+expb+')'; //将a和b计算的算式填入到原来expression[i]的位置 number[i]=a+b; //将a和b计算的结果填入到原来number[i]的位置 if (Search(n-1)) return true; //一旦得到一个可行解，即层层向上返回，从而确保只输出一个可行解 //减法有两种情况a-b和b-a expression[i]='('+expa+'-'+expb+')'; number[i]=a-b; if (Search(n-1)) return true; expression[i]='('+expb+'-'+expa+')'; number[i]=b-a; if (Search(n-1)) return true; //乘法 expression[i]='('+expa+'*'+expb+')'; number[i]=a*b; if (Search(n-1)) return true; //除法也有两种情况a/b和b/a if (b!=0) { expression[i]='('+expa+'/'+expb+')'; number[i]=a/b; if (Search(n-1)) return true; } if (a!=0) { expression[i]='('+expb+'/'+expa+')'; number[i]=b/a; if (Search(n-1)) return true; } //本轮调用完毕后，用a,b,expa,expb将数组number[]和expression[]恢复原状 number[i]=a; number[j]=b; expression[i]=expa; expression[j]=expb; } } return false; } int main() { int num; for (int i=0;i<4;i++) { char buffer[20]; //分配长度为20的字符数组buffer[] char x,c; int flag1=0; cin>>x; if (x=='0') {cin>>x; } if (x>='2'&&x<='9') {num=x-'0';flag1=1; } if (x=='1') {num=10;flag1=1; } if (x=='J') {num=11;flag1=1; if(i==3) {if(cin.get() != '\n') {cout<<"ERROR"; return 0;} } } if (x=='Q') {num=12;flag1=1; } if (x=='K') {num=13;flag1=1; } if (x=='A') {num=1;flag1=1; } if(flag1==0&&x!='0') { cout<<"ERROR"<<endl; return 0; } number[i]=num; itoa(num,buffer,10); //itoa():将一个10进制的integer数转换为string类型 //即：把输入的int型操作数x，转变成可以放在buffer[]中的string类型 expression[i]=buffer; //用expression[i]指针指向buffer[]数组空间的起始位置 } bool dex=Search(4); if(!dex) cout<<"NONE"<<endl; return 0; }