Description
这是一道简单的小学生算术题，问题是这样的：给你四个整型数A,B,C,D，问其中的某一个数字能 否通过其他三个数的加减乘除运算得到。每个数只能用一次。如果可以，则输出Yes，否则输出 No。比如四个数为1,2,3,6.而1 + 2 + 3 = 6。所以输出Yes。如果四个数为2,2,3,9，则任意的三个数的运算，都不可能让等式成立。所以输出No。 提示：在计算机的整型数相除中，5 / 2 = 2,而我们 问题中的算术，5 / 2 = 2.5。能帮你的只有这么多了。
Input
第一行输入一个整数t，表示有t组测试数据。 每组数据，输入四个整数，A,B,C,D。其中0 <= A,B,C,D <= 1000.
Output
对于每组测试数据，按题意输出Yes或者No。
Sample Input
2
1 2 3 6
2 2 3 9
Sample Output
Yes
No
思路清晰，但实现过程对我来说费劲。
自己的代码如下，提交了不下20次，最终还是机缘巧合之下凭借输错数据得出错误的答案而分析修改程序最终AC。
next_permutation()
函数学习地址：
http://blog.csdn.net/hoaresky1998/article/details/50041601
枚举代码如下：
#include
#include
#include
using namespace std;
int main(){
int t;cin>>t;
while(t--)
{
double q,b,c,d;
double tmp;
cin>>q>>b>>c>>d;
double a[50];
a[0]=q,a[1]=b,a[2]=c,a[3]=d;
int p=0,flag=1;
do // 枚举出3个数由+-*/的所有排列方式
{ // 然后由next_permutation函数改变四个数的位置。
tmp=(a[0]+a[1])+a[2];
if(a[3]==tmp) p=1;
if(p==1) {cout<<"Yes";flag=1;break;}
tmp=(a[0]+a[1])-a[2];
if(a[3]==tmp) p=1;
if(p==1) {cout<<"Yes";flag=1;break;}
tmp=(a[0]+a[1])*a[2];
if(a[3]==tmp) p=1;
if(p==1) {cout<<"Yes";flag=1;break;}
for(int i=0;i<1;i++)
{
if(a[2]==0) break;
tmp=(a[0]+a[1])/a[2];
if(a[3]==tmp) p=1;
}
if(p==1) {cout<<"Yes";flag=1;break;}
tmp=(a[0]-a[1])+a[2];
if(a[3]==tmp) p=1;
if(p==1) {cout<<"Yes";flag=1;break;}
tmp=(a[0]-a[1])-a[2];
if(a[3]==tmp) p=1;
if(p==1) {cout<<"Yes";flag=1;break;}
tmp=(a[0]-a[1])*a[2];
if(a[3]==tmp) p=1;
if(p==1) {cout<<"Yes";flag=1;break;}
for(int i=0;i<1;i++)
{
if(a[2]==0) break;
tmp=(a[0]-a[1])/a[2];
if(a[3]==tmp) p=1;
}
if(p==1) {cout<<"Yes";flag=1;break;}
tmp=(a[0]*a[1])+a[2];
if(a[3]==tmp) p=1;
if(p==1) {cout<<"Yes";flag=1;break;}
tmp=(a[0]*a[1])-a[2];
if(a[3]==tmp) p=1;
if(p==1) {cout<<"Yes";flag=1;break;}
tmp=(a[0]*a[1])*a[2];
if(a[3]==tmp) p=1;
if(p==1) {cout<<"Yes";flag=1;break;}
for(int i=0;i<1;i++)
{
if(a[2]==0) break;
tmp=(a[0]*a[1])/a[2];
if(a[3]==tmp) p=1;
}
if(p==1) {cout<<"Yes";flag=1;break;}
for(int i=0;i<1;i++)
{
if(a[1]==0) break;
tmp=(a[0]/a[1])+a[2];
if(a[3]==tmp) p=1;
}
if(p==1) {cout<<"Yes";flag=1;break;}
for(int i=0;i<1;i++)
{
if(a[1]==0) break;
tmp=(a[0]/a[1])-a[2];
if(a[3]==tmp) p=1;
}
if(p==1) {cout<<"Yes";flag=1;break;}
for(int i=0;i<1;i++)
{
if(a[1]==0) break;
tmp=(a[0]/a[1])*a[2];
if(a[3]==tmp) p=1;
}
if(p==1) {cout<<"Yes";flag=1;break;}
for(int i=0;i<1;i++)
{
if(a[2]==0||a[1]==0) break;
tmp=(a[0]/a[1])/a[2];
if(a[3]==tmp) p=1;
}
if(p==1) {cout<<"Yes";flag=1;break;}
flag=0;
}while(next_permutation(a,a+4));
if(flag==0) cout<<"No";
if(t>0) cout<
递归代码如下：
#include
#include
#include
#include
using namespace std;
double a[50];
int ok;
void dfs(int step,double ans){
if(ok) return ;
if(step>2){
if(ans==a[3]) ok=1;
return ;
}
for(int i=0;i<4;++i){ //递归思想。
if(i==0)
dfs(step+1,ans+a[step]);
if(i==1)
dfs(step+1,ans-a[step]);
if(i==2)
dfs(step+1,ans*a[step]);
if(i==3 && a[step])
dfs(step+1,ans/a[step]);
}
}
int main(){
int t;cin>>t;
while(t--){
for(int i=0;i<4;i++) scanf("%lf",&a[i]);
ok=0;
sort(a,a+4);
do{
dfs(1,a[0]);
if(ok) break;
}while(next_permutation(a,a+4)); //按字典序排列数组。
puts(ok?"Yes":"No");
}
return 0;
}