8948: 流行游戏
内存限制：128 MB
时间限制：1.000 S
提交：1
解决：0
评测方式：文本比较
命题人：
题目描述
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算 点”。您作为游戏者将得到 个 之间的自然数作为操作数，而您的任务是对这 个操作数进行适当的算术运算，要求运算结果等于 。
您可以使用的运算只有：，您还可以使用 来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如， 是合法的， 是不合法的）。下面我们给出一个游戏的具体例子：
若给出的 个操作数是： 、 、 、 ，则一种可能的解答是 。
输入
只有一行，四个1到9之间的自然数
输出
如果有解的话，只要输出一个解。输出的是三行数据，分别表示运算的步骤。
- 其中第一行是输入的两个数和一个运算符和运算后的结果；
- 第二行是第一行的结果和一个输入的数据、运算符、运算后的结果，或者是另外两个数的输出结果；
- 第三行是前面的结果第二行的结果或者剩下的一个数字、运算符和 。如果两个操作数有大小的话则先输出大的。
如果没有解则输出 No answer!。
如果有多重合法解，输出任意一种即可。
注：所有运算结果均为正整数。
样例输入 复制
1 2 3 7样例输出 复制
2+1=3
7*3=21
21+3=24提示
#include<bits/stdc++.h> using namespace std; int a,b,c,d; int x[5]; int s[5][5]; bool flag=0; void print(int x)//输出答案 { cout << s[x][2]; if(s[x][1]==0) cout << "+"; if(s[x][1]==1) cout << "-"; if(s[x][1]==2) cout << "-"; if(s[x][1]==3) cout << "*"; if(s[x][1]==4) cout << "/"; cout << s[x][3]; cout << "="; if(s[x][1]==0) cout << s[x][2]+s[x][3]; if(s[x][1]==1) cout << s[x][2]-s[x][3]; if(s[x][1]==2) cout << s[x][2]-s[x][3]; if(s[x][1]==3) cout << s[x][2]*s[x][3]; if(s[x][1]==4) cout << s[x][2]/s[x][3]; cout << endl;
} void dfs(int step) { if(flag==1) return; if(step==3)//找到符合题意但不一定可行的解 { int sum,cnt=0; for(int i=1;i<=4;i++)//找24 { if(x[i]!=0)
{
sum=x[i];
cnt++;
}
} if(sum==24&&cnt==1)
{ //输出 print(1);
print(2);
print(3);
flag=1;
} return;
} int t[5]; for(int i=1;i<=4;i++) t[i]=x[i]; for(int i=1;i<=4;i++)
{ for(int j=1;j<=4;j++)
{ if(i==j) continue;//不能一样 if(x[i]==0||x[j]==0) continue;//不能为0 int xx=x[i],yy=x[j]; //加法 x[i]=xx,x[j]=yy;
s[step+1][1]=0,s[step+1][2]=max(x[i],x[j]),s[step+1][3]=min(x[i],x[j]);
x[i]=x[i]+x[j],x[j]=0;
dfs(step+1); if(xx>yy)//减法1（保证大值在前） {
x[i]=xx,x[j]=yy;
s[step+1][1]=1,s[step+1][2]=x[i],s[step+1][3]=x[j];
x[i]=x[i]-x[j],x[j]=0;
dfs(step+1);
} if(yy>xx)//减法2 {
x[i]=xx,x[j]=yy;
s[step+1][1]=2,s[step+1][2]=x[j],s[step+1][3]=x[i];
x[i]=x[j]-x[i],x[j]=0;
dfs(step+1);
} //乘法 x[i]=xx,x[j]=yy;
s[step+1][1]=3,s[step+1][2]=max(x[i],x[j]),s[step+1][3]=min(x[i],x[j]);
x[i]=x[i]*x[j],x[j]=0;
dfs(step+1); if(xx%yy==0&&yy!=0)
{
x[i]=xx,x[j]=yy;
s[step+1][1]=4,s[step+1][2]=x[i],s[step+1][3]=x[j];
x[i]=x[i]/x[j],x[j]=0;
dfs(step+1);
} if(yy%xx==0&&xx!=0)//如果除以操作合法 {
x[i]=xx,x[j]=yy;
s[step+1][1]=4,s[step+1][2]=x[j],s[step+1][3]=x[i];
x[i]=x[j]/x[i],x[j]=0;
dfs(step+1);
} for(int i=1;i<=4;i++)
x[i]=t[i];//改回原数组 }
}
} int main() { scanf("%d%d%d%d",&a,&b,&c,&d);//输入 x[1]=a,x[2]=b,x[3]=c,x[4]=d;
sort(x+1,x+5);//排个序 dfs(0);//找答案 if(flag==0) cout << "No answer!" << endl;//输出无解 return 0;
}
测试用（周伟专用）