简答题
偏难
#7208
算24 给出4个小于10个正整数,你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是,是否存在一种方式使得得到的表达式的结果等于2…
算24
给出4个小于10个正整数,你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是,是否存在一种方式使得得到的表达式的结果等于24。 这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致(这里的除法定义是实数除法)。 比如,对于5,5,5,1,我们知道5 * (5 – 1 / 5) = 24,因此可以得到24。又比如,对于1,1,4,2,我们怎么都不能得到24。
时间限制:6000
内存限制:65536
输入
输入数据包括多行,每行给出一组测试数据,包括4个小于10个正整数。最后一组测试数据中包括4个0,表示输入的结束,这组数据不用处理。
输出
对于每一组测试数据,输出一行,如果可以得到24,输出“YES”;否则,输出“NO”。
样例输入
5 5 5 1 1 1 4 2 0 0 0 0
样例输出
YES NO
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
#include <cmath>
#include <iostream>
#define EPS 1e-6
using namespace std;
bool iszero(double c) {
if (fabs(c) <= EPS)
return 1;
else
return 0;
}
bool suan24(double *a, int k) {
if (k == 1 && iszero(a[0] - 24))
return 1;
double b[5];
for (int i = 0; i < k - 1; i++)
for (int j = i + 1; j < k; j++) {
int z = 0;
for (int xx = 0; xx < k; xx++)
if (xx != i && xx != j)
b[z++] = a[xx];
b[z] = a[i] + a[j];
if (suan24(b, k - 1))
return 1;
b[z] = a[i] - a[j];
if (suan24(b, k - 1))
return 1;
b[z] = a[j] - a[i];
if (suan24(b, k - 1))
return 1;
b[z] = a[i] * a[j];
if (suan24(b, k - 1))
return 1;
if (a[j] != 0) {
b[z] = a[i] / a[j];
if (suan24(b, k - 1))
return 1;
}
if (!iszero(a[i])) {
b[z] = a[j] / a[i];
if (suan24(b, k - 1))
return 1;
}
}
return 0;
}
int main() {
while (1) {
double a[6];
int sum = 0;
for (int i = 0; i < 4; ++i) {
cin >> a[i];
sum += a[i];
}
if (sum == 0)
break;
bool flag = suan24(a, 4);
if (flag == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
// cout<<flag<<endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法2 深搜
#include <bits/stdc++.h>
using namespace std;
double a[5];
bool fig(double a[],int n){
double b[5];
int i,j,k,m;
if(fabs(a[0]-24)<1e-6 && n==1) return 1;
if(n==1) return 0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++){
m=0;
for(k=0;k<n;k++)
if(k!=i&&k!=j) b[++m]=a[k];
b[0]=a[i]+a[j];if(fig(b,n-1)) return 1;
b[0]=a[i]-a[j];if(fig(b,n-1)) return 1;
b[0]=a[j]-a[i];if(fig(b,n-1)) return 1;
b[0]=a[i]*a[j];if(fig(b,n-1)) return 1;
b[0]=a[i]/a[j];if(fig(b,n-1)) return 1;
b[0]=a[j]/a[i];if(fig(b,n-1)) return 1;
}
return 0;
}
int main() {
while(1){
for(int i=0;i<4;i++) cin>>a[i];
if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0) break;
if(fig(a,4)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}</pre>
这道题暂未补解析。