算24点 解题报告

/*********************利用回溯法**********************/

#include<iostream>

#include<string>//字符串的头文件
#include<cmath>

usingnamespacestd;

constdoublePRECISION(1E-6);//判断是否相等
constintCOUNT_OF_NUMBER(4);
constintCAL_TWENTY_FOUR(24);

doublenumber[COUNT_OF_NUMBER];//存放数据
stringexpression[COUNT_OF_NUMBER];//用来存放表达式

boolSearch(intn)
{
intstate=0;//标记是否有符合条件的表达式
if(n==1)
{
if(fabs(number[0]-CAL_TWENTY_FOUR)<PRECISION)
{
cout<<expression[0]<<endl;
returntrue;
}
else
{
returnfalse;
}
}
for(inti=0;i<n;i++)
{
for(intj=i+1;j<n;j++)
{
doublea,b;
stringexpa,expb;
a=number[i];
b=number[j];
number[j]=number[n-1];
expa=expression[i];
expb=expression[j];
expression[j]=expression[n-1];

expression[i]='('+expa+'+'+expb+')';//加法处理
number[i]=a+b;
if(Search(n-1))
state=1;

expression[i]='('+expa+'-'+expb+')';//减法处理
number[i]=a-b;
if(Search(n-1))
state=1;

expression[i]='('+expb+'-'+expa+')';//减法处理
number[i]=b-a;
if(Search(n-1))
state=1;

expression[i]=expa+'*'+expb;//乘法处理
number[i]=a*b;
if(Search(n-1))
state=1;

if(b!=0)
{
expression[i]=expa+'/'+expb;//除法处理
number[i]=a/b;
if(Search(n-1))
state=1;
}

if(a!=0)
{
expression[i]=expb+'/'+expa;//除法处理
number[i]=b/a;
if(Search(n-1))
state=1;
}
//数据的赋值
number[i]=a;
number[j]=b;
expression[i]=expa;
expression[j]=expb;
}
}
if(state==1)
returntrue;
else
returnfalse;
}
intmain()
{
for(inti=0;i<COUNT_OF_NUMBER;i++)
{
charbuffer[20];
intx;
cin>>x;
number[i]=x;
itoa(x,buffer,10);//按十进制将数字转化成字符串
expression[i]=buffer;
}
if(!Search(COUNT_OF_NUMBER))
cout<<"Fail."<<endl;
return0;
}