Question

[C语言问题][高手请进] 12345 怎样通过+ - × ÷得 22 ？

有这么一个问题：
"怎样用12345这五个数字和加减乘除（每个必须用且只能用一次），使其值等于22,可以用括号,五个数字的顺序可以调换."

现在已经有两个答案：
(3/2-1+5)*4=22
(3/2+4)*(5-1)=22

我的问题是：
怎样用C语言编程求出所有符合条件的答案？
//sxt19840210，你好，你的答案我试了，很不错的程序。只是题目要求“每种运算必须用且只能用一次”，我修改之后运行发现只有
(3/2-1+5)*4=22
(3/2+5-1)*4=22
这两个结果，没有得到
(3/2+4)*(5-1)=22
这个结果。

我想这可能是因为你的程序没有考虑到运算符号出现在两个括号之间这种情况，而我还没想出怎么修改。希望你能再帮我修改一下，谢谢！

//kqk4080 你好！
请注意题目要求：“每种运算必须用且只能用一次”
希望你能做进一步的修改，谢谢！

Answer 1

我把它写出来了：
#include "iostream.h"
#include "math.h"
#include <string>

using namespace std;

double num[5];
string exps[5];

double round(double d,int p)
{
double *dp,d1;
dp=new double;
d=d*pow(10,p);
d1=modf(d,dp);
d1>=0.5?d=(*dp+1)/pow(10,p):d=*dp/pow(10,p);
delete dp;
return d;
}
is22(int n)
{
int i,j;double a,b;string as,bs;
if(n==1)
{
if(round(num[0],4)==22)
{
cout<<exps[0].c_str()<<endl;
return false;
}
return false;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(i==j)continue;
a=num[i];
b=num[j];
num[j]=num[n-1];
as=exps[i];
bs=exps[j];
exps[j]=exps[n-1];
if(i!=n-1){num[i]=a+b;exps[i]=string("(")+as+(string)"+"+bs+(string)")";}else {num[j]=a+b;exps[j]=string("(")+as+(string)"+"+bs+string(")");}
if(is22(n-1))return true;
if(i!=n-1){num[i]=a-b;exps[i]=string("(")+as+(string)"-"+bs+string(")");}else {num[j]=b-a;exps[j]=string("(")+as+(string)"-"+bs+string(")");}
if(is22(n-1))return true;
if(i!=n-1){num[i]=a*b;exps[i]=as+(string)"*"+bs;}else {num[j]=a*b;exps[j]=as+(string)"*"+bs;}
if(is22(n-1))return true;
if(i!=n-1){num[i]=a/b;exps[i]=as+(string)"/"+bs;}else {num[j]=a/b;exps[j]=as+(string)"/"+bs;}
if(is22(n-1))return true;
num[i]=a;
num[j]=b;
exps[i]=as;
exps[j]=bs;
}
}
return false;
}

void main()
{
num[0]=1,num[1]=2,num[2]=3,num[3]=4,num[4]=5;
exps[0]="1",exps[1]="2",exps[2]="3",exps[3]="4",exps[4]="5";
is22(5);
}
生成的表达式多达40多KB,我随便贴点出来
(((1+2)*5+4)+3)
(3+((1+2)*5+4))
(((1+2)*5+3)+4)
(4+((1+2)*5+3))
(3+(4+(1+2)*5))
((4+(1+2)*5)+3)
((1+2)*5+(4+3))
((4+3)+(1+2)*5)
((3+(1+2)*5)+4)
(4+(3+(1+2)*5))
((1+2)*5+(3+4))
((3+4)+(1+2)*5)
(((1+2)+4)+5*3)
(5*3+((1+2)+4))
(((1+2)+4)+3*5)
(3*5+((1+2)+4))
((4+5*(1+2))+3)
(3+(4+5*(1+2)))
((4+3)+5*(1+2))
(5*(1+2)+(4+3))
(3+(5*(1+2)+4))
((5*(1+2)+4)+3)
(4+(5*(1+2)+3))
((5*(1+2)+3)+4)
((3+4)+5*(1+2))
(5*(1+2)+(3+4))
(4+(3+5*(1+2)))
((3+5*(1+2))+4)
(((1+2)+5*3)+4)
(4+((1+2)+5*3))
(((1+2)+4)+5*3)
(5*3+((1+2)+4))
(4+(5*3+(1+2)))
((5*3+(1+2))+4)
((1+2)+(5*3+4))
((5*3+4)+(1+2))
((4+(1+2))+5*3)
(5*3+(4+(1+2)))
((1+2)+(4+5*3))
((4+5*3)+(1+2))
(((1+2)+4)+3*5)
(3*5+((1+2)+4))
(((1+2)+3*5)+4)
(4+((1+2)+3*5))
(3*5+(4+(1+2)))
((4+(1+2))+3*5)
((1+2)+(4+3*5))
((4+3*5)+(1+2))
((3*5+(1+2))+4)
(4+(3*5+(1+2)))
((1+2)+(3*5+4))
((3*5+4)+(1+2))
((1+2)*5+(3+4))
((3+4)+(1+2)*5)
((3+4)+5*(1+2))
(5*(1+2)+(3+4))
((4+(1+2))+5*3)
(5*3+(4+(1+2)))
((4+(1+2))+3*5)
(3*5+(4+(1+2)))
((1+2)*5+(4+3))
((4+3)+(1+2)*5)
((4+3)+5*(1+2))
(5*(1+2)+(4+3))
(((1-2)+3)+5*4)
(5*4+((1-2)+3))
(((1-2)+3)+4*5)
(4*5+((1-2)+3))
(4+(5-(1-2))*3)
((5-(1-2))*3+4)
(4+3*(5-(1-2)))
(3*(5-(1-2))+4)
(((1-2)+5*4)+3)
(3+((1-2)+5*4))
(((1-2)+3)+5*4)
(5*4+((1-2)+3))
(3+(5*4+(1-2)))
((5*4+(1-2))+3)
((1-2)+(5*4+3))
((5*4+3)+(1-2))
((3+(1-2))+5*4)
(5*4+(3+(1-2)))
((1-2)+(3+5*4))
((3+5*4)+(1-2))
(4*5+(3+(1-2)))
((3+(1-2))+4*5)
((3+(1-2))+5*4)
(5*4+(3+(1-2)))
(((1-2)+4*5)+3)
(3+((1-2)+4*5))
(((1-2)+3)+4*5)
(4*5+((1-2)+3))
(3+(4*5+(1-2)))
((4*5+(1-2))+3)
((1-2)+(4*5+3))
((4*5+3)+(1-2))
((3+(1-2))+4*5)
(4*5+(3+(1-2)))
((1-2)+(3+4*5))
((3+4*5)+(1-2))
(1*2*5+4*3)
(4*3+1*2*5)
(1*2*5+3*4)
(3*4+1*2*5)
(4*3+5*1*2)
(5*1*2+4*3)
(3*4+5*1*2)
(5*1*2+3*4)
4*(5/1*2+3)
(5/1*2+3)*4
4*(3+5/1*2)
(3+5/1*2)*4
1*2*(5*3-4)
(5*3-4)*1*2
1*2*(4-5*3)
(4-5*3)*1*2
(1*2*5+3*4)
(3*4+1*2*5)
(3*4+5*1*2)
(5*1*2+3*4)
(1*2*5+4*3)
(4*3+1*2*5)
(4*3+5*1*2)
(5*1*2+4*3)
(1/2*5+3)*4
4*(1/2*5+3)
(3+1/2*5)*4
4*(3+1/2*5)
4*(5*1/2+3)
(5*1/2+3)*4
4*(3+5*1/2)
(3+5*1/2)*4
(4*3+5/1/2)
(5/1/2+4*3)
(3*4+5/1/2)
(5/1/2+3*4)
(5*3-4)/1/2
(4-5*3)/1/2
(3*4+5/1/2)
(5/1/2+3*4)
(4*3+5/1/2)
(5/1/2+4*3)
(((1+3)-2)+4*5)
(4*5+((1+3)-2))
(((1+3)-2)+5*4)
(5*4+((1+3)-2))
((1+3)/2+4*5)
(4*5+(1+3)/2)
((1+3)/2+5*4)
(5*4+(1+3)/2)
(((1+3)+5)*2+4)
(4+((1+3)+5)*2)
(4+2*((1+3)+5))

要过滤也十分简单
只要在语句cout<<exps[0].c_str()<<endl;
上加一句就行了：
if(exps[0].find("+")!=string::npos && exps[0].find("-")!=string::npos && exps[0].find("*")!=string::npos && exps[0].find("/")!=string::npos)
得到的结果如下：
(4+3/2)*(5-1)
(5-1)*(4+3/2)
4*((5-1)+3/2)
((5-1)+3/2)*4
(3/2+4)*(5-1)
(5-1)*(3/2+4)
4*(3/2+(5-1))
(3/2+(5-1))*4
4*((5+3/2)-1)
((5+3/2)-1)*4
4*(5+(3/2-1))
(5+(3/2-1))*4
4*((3/2-1)+5)
((3/2-1)+5)*4
(3/2+4)*(5-1)
(5-1)*(3/2+4)
(4+3/2)*(5-1)
(5-1)*(4+3/2)

Answer 2

#include<stdio.h>

char CurrentRes[16];
FILE *stream;

void Remember(int *a,int *ct,int *sq)
{
int i,j,n,left,right,cs[4],s[4],tleft[3],tright[3],tsure[3];
char ch[16],c[6]={'+','-','*','/','(',')'};

for(i=0;i<5;i++)
{
ch[2*i]=a[i]+48;
}
for(i=0;i<4;i++)
{
ch[2*i+1]=c[ct[i]];
s[i]=2*sq[i]+1;
cs[i]=ct[sq[i]];
}
n=8;
for(i=0;i<4;i++)
{
for(j=0;j<5;j++)
{
;
}
}
for(i=0;i<3;i++)
{
tsure[i]=1;
tleft[i]=s[i]-1;
tright[i]=s[i]+2;
for(j=0;j<i;j++)
{
if((tleft[i]<tright[j])&&(tright[i]>tright[j]))
tleft[i]=tleft[j];
if((tleft[i]<tleft[j])&&(tright[i]>tleft[j]))
tright[i]=tright[j];
}
}
for(i=2;i>=0;i--)
{
for(j=2;j>=0;j--)
if(s[i+1]==tright[j])
{
if(ct[sq[j]]<2)
{
if(ct[sq[i+1]]<2)
tsure[j]=0;
}
else
tsure[j]=0;
break;
}
for(j=2;j>=0;j--)
if(s[i+1]+1==tleft[j])
{
if(ct[sq[j]]<2)
{
if(ct[sq[i+1]]==0)
tsure[j]=0;
}
else
if(ct[sq[i+1]]<2)
tsure[j]=0;
else
if(ct[sq[i+1]]==2)
tsure[j]=0;
break;
}
}
for(i=2;i>=0;i--)
{
if(tsure[i]==1)
{
if(tright[i]==n)
{
n++;
ch[n]=c[5];
}
else
{
n++;
for(j=n;j>tright[i];j--)
ch[j]=ch[j-1];
ch[j]=c[5];
right=tright[i];
for(j=0;j<3;j++)
{
if(tright[j]>=right)
tright[j]++;
if(tleft[j]>right)
tleft[j]++;
}
for(j=0;j<4;j++)
if(s[j]>=right)
s[j]++;
}
n++;
for(j=n;j>tleft[i];j--)
ch[j]=ch[j-1];
ch[j]=c[4];
left=tleft[i];
for(j=0;j<3;j++)
{
if(tright[j]>left)
tright[j]++;
if(tleft[j]>=left)
tleft[j]++;
}
for(j=0;j<4;j++)
if(s[j]>left)
s[j]++;
}
}
n++;
ch[n]='\0';
for(i=0;i<16;i++)
{
if(ch[i]!=CurrentRes[i])
break;
if(ch[i]=='\0')
break;
if(CurrentRes[i]=='\0')
break;
}
if((ch[i]!='\0')||(CurrentRes[i]!='\0'))
{
for(i=0;i<16;i++)
CurrentRes[i]=ch[i];
fprintf(stream,"%s\n",ch);
}
}

void CheckResult(int *a,int *ct,int *sq)
{
double data[5];
int i,j,c[4],s[4];

for(i=0;i<5;i++)
data[i]=a[i]*1.0;
for(i=0;i<4;i++)
{
c[i]=ct[i];
s[i]=sq[i];
}
for(i=0;i<4;i++)
{
switch(c[s[i]])
{
case 0:
data[s[i]]+=data[s[i]+1];
for(j=s[i]+1;j<4-i;j++)
data[j]=data[j+1];
for(j=s[i];j<3-i;j++)
c[j]=c[j+1];
for(j=i;j<4;j++)
if(s[j]>s[i])
s[j]--;
break;
case 1:
data[s[i]]-=data[s[i]+1];
for(j=s[i]+1;j<4-i;j++)
data[j]=data[j+1];
for(j=s[i];j<3-i;j++)
c[j]=c[j+1];
for(j=i;j<4;j++)
if(s[j]>s[i])
s[j]--;
break;
case 2:
data[s[i]]*=data[s[i]+1];
for(j=s[i]+1;j<4-i;j++)
data[j]=data[j+1];
for(j=s[i];j<3-i;j++)
c[j]=c[j+1];
for(j=i;j<4;j++)
if(s[j]>s[i])
s[j]--;
break;
default :
data[s[i]]/=data[s[i]+1];
for(j=s[i]+1;j<4-i;j++)
data[j]=data[j+1];
for(j=s[i];j<3-i;j++)
c[j]=c[j+1];
for(j=i;j<4;j++)
if(s[j]>s[i])
s[j]--;
break;
}
}
if(data[0]==22.0)
Remember(a,ct,sq);
}

void CaculateSequence(int *a,int *ct,int *sq,int n)
{
int i,temp,sqc[4];

for(i=0;i<4;i++)
sqc[i]=sq[i];
if(n>2)
{
CaculateSequence(a,ct,sqc,n-1);
for(i=4-n+1;i<4;i++)
{
if(ct[sq[i]]!=ct[sq[4-n]])
{
temp=sqc[4-n];
sqc[4-n]=sqc[i];
sqc[i]=temp;
CaculateSequence(a,ct,sqc,n-1);
}
}
}
else
{
CheckResult(a,ct,sqc);
if(ct[sq[4-n]]!=ct[sq[4-n+1]])
{
temp=sqc[4-n];
sqc[4-n]=sqc[4-n+1];
sqc[4-n+1]=temp;
CheckResult(a,ct,sqc);
}
}
}

void AllOperateQueue(int *a)
{
int i,j,k,l,count[4],sequence[4];

for(i=0;i<4;i++)
sequence[i]=i;
for(i=0;i<4;i++)
{
count[0]=i;
for(j=0;j<4;j++)
{
count[1]=j;
for(k=0;k<4;k++)
{
count[2]=k;
for(l=0;l<4;l++)
{
count[3]=l;
CaculateSequence(a,count,sequence,4);
}
}
}
}
}

void AllQueue(int *a,int n,int m)
{
int i,temp,b[5];

for(i=0;i<5;i++)
b[i]=a[i];
if(m>2)
{
for(i=n-m;i<n;i++)
{
temp=b[n-m];
b[n-m]=b[i];
b[i]=temp;
AllQueue(b,n,m-1);
}
}
else
{
AllOperateQueue(b);
temp=b[n-m];
b[n-m]=b[n-m+1];
b[n-m+1]=temp;
AllOperateQueue(b);
}
}

void main()
{
int i,a[5];

CurrentRes[0]='\0';
stream=fopen("result.txt","w");
for(i=0;i<5;i++)
a[i]=i+1;
AllQueue(a,5,5);
fclose(stream);
}
//想了很多办法，现在包含了所有结果，并且结果已经很简化了！你看看还有没有要改进的！

Answer 3

可以参考我的百度空间里的24点程序：
http://hi.baidu.com/zmjdx/blog/item/65fe6882dc2ac2a30df4d20d.html

#include <iostream>
#include <time.h>

using namespace std;
typedef unsigned char byte;
bool compute(byte op[]);
bool GetNextArrange(byte flag[]);

void main(){
srand((long)time(NULL));
byte points[4],oper[4];

cout<<"随机产生四个1-13的数:"<<endl;
for(int i=0;i<4;i++){
points[i] = (byte)(1 + rand() % 13);
cout<<(int)points[i]<<" ";
}
cout<<endl<<"---------------------------------------"<<endl;
//oper数组存放加减乘除 为了与数区分 编号成大于16的数
for (i=0;i<4;i++)
oper[i] = 1 << (i+4);
//分三步走:
//1从数字中抽两个
//2从运算符中抽三个
//3剩下的两个数和三个运算符做全排列 加上1步中的两个数(放最前),这0七个因子构成逆波兰式,计算即可

//逆波兰数组 rpn(Reverse Polish Notation)
byte rpn[7];

for(i=0;i<4;i++){
rpn[0] = points[i];
for(int j=i+1;j<4;j++){//取两个数points[i],points[j]
rpn[1] = points[j];

for(int k=0;k<4;k++){//取一个运算符(即取了剩下的三个)
int m = 2; //逆波兰数组里已经保存有两个数,下一个数下标从2开始
for(int l=0;l<4;l++){
if(l != i && l != j)
rpn[m++] = points[l];
if(l != k)
rpn[m++] = oper[l];
}
//逆波兰中的七个数(包含运算符)都已经填完,但后面的五个可以换序
compute(rpn);

byte array[5];
for(int n=0;n<5;n++)
array[n] = rpn[n+2];

byte flag[5] = {1,2,3,4,5};
while(GetNextArrange(flag)){
for(int i=0;i<5;i++)
rpn[i+2] = array[flag[i] - 1];
compute(rpn);
}
}
}
}
}

bool compute(byte op[]){
double result = 0;
double copy[4] = {0,0,0,0};
int pos = -1;
for(int i=0;i<7;i++){
if(op[i] < 16){
pos++;
copy[pos] = op[i];
if(pos > 3) //太多操作数
return false;
}
else{//是运算符
if(pos < 1){//不足两个数,不能运算!
return false;
}
switch(op[i]){
case 1<<4: // +
result = copy[pos-1] + copy[pos];
break;
case 1<<5: // -
result = copy[pos-1] - copy[pos];
break;
case 1<<6: // *
result = copy[pos-1] * copy[pos];
break;
case 1<<7: // /
if(copy[pos] == 0)
return false;
result = (double)copy[pos-1] / copy[pos];
break;
default:
break;
}
pos--;
copy[pos] = result;
}
}
if(pos == 0 && result == 24){
for(int k=0;k<7;k++){
if(op[k]<15)
cout<<(int)op[k]<<" ";
else
switch(op[k]) {
case 1<<4:
cout<<"+ ";
break;
case 1<<5:
cout<<"- ";
break;
case 1<<6:
cout<<"* ";
break;
case 1<<7:
cout<<"/ ";
break;
default:
break;
}
}
cout<<endl;
return true;
}
else
return false;
}

void wrap(byte *a,byte *b){
byte temp = *a;
*a = *b;
*b = temp;
}

void sort(byte *p,int n){
for(int i=n-1;i>=0;i--)
for(int j=0;j<i;j++){
if(p[j] > p[j+1])
wrap(&p[j],&p[j+1]);
}
}
//求下一个全排列,所有排列完成后返回false
bool GetNextArrange(byte flag[]){
bool ret = false;
byte *min;
int deta = 5;
for(int i=4;i>0;i--){
if(flag[i] > flag[i-1]){
for(int j=i;j<5;j++){
if(flag[j] > flag[i-1]){
if((flag[j] - flag[i-1]) < deta){
deta = flag[j] - flag[i-1];
min = &flag[j];
}
}
}
wrap(min,&flag[i-1]);
sort(&flag[i],5-i);
ret = true;
break;
}
}
return ret;
}

Answer 4

把4个结点的各种树都构造出来，把各种运算符的排列组合都列出来，答案就出来了，然后把树写成表达式就可以了。

Answer 5

这个题目有点挑战性，我有空会练练