0075:算24
- 查看
- 提交
- 统计
- 提问
总时间限制:
3000ms
内存限制:
65536kB
描述
给出4个小于10个正整数,你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是,是否存在一种方式使得得到的表达式的结果等于24。
这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致(这里的除法定义是实数除法)。
比如,对于5,5,5,1,我们知道5 * (5 – 1 / 5) = 24,因此可以得到24。又比如,对于1,1,4,2,我们怎么都不能得到24。
输入
输入数据包括多行,每行给出一组测试数据,包括4个小于10个正整数。最后一组测试数据中包括4个0,表示输入的结束,这组数据不用处理。
输出
对于每一组测试数据,输出一行,如果可以得到24,输出“YES”;否则,输出“NO”。
样例输入
5 5 5 1 1 1 4 2 0 0 0 0
样例输出
YES NO
分析:
无论加减乘除还是括号,都需要算合并两个数,数减少一个,还剩n-1,重复上述过程,递归
易错点:double中等于需要控制精度
代码:
import java.util.Arrays;
import java.util.Scanner;
public class Main
{static int cal(double a[],int n){if(n==1){if(Math.abs(a[0]-24)<=1e-6)return 1;elsereturn 0;}double [] b=new double[4];for(int i=0;i<n-1;i++)//注意到i-1{for(int j=i+1;j<n;j++){int m=0;for(int k=0;k<n;k++)if(k!=i&&k!=j){b[m]=a[k];m++;}b[m]=a[i]+a[j];if(cal(b,m+1)==1)return 1;b[m]=a[i]-a[j];if(cal(b,m+1)==1)return 1;b[m]=a[j]-a[i];if(cal(b,m+1)==1)return 1;b[m]=a[i]*a[j];if(cal(b,m+1)==1)return 1;if(a[j]!=0){b[m]=a[i]/a[j];if(cal(b,m+1)==1)return 1;}if(a[i]!=0){b[m]=a[j]/a[i];if(cal(b,m+1)==1)return 1;}}}return 0;}public static void main(String args[]){Scanner cin=new Scanner(System.in);double [] a=new double[4];while(cin.hasNext()){for(int i=0;i<4;i++)a[i]=cin.nextDouble();if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0)break;if(cal(a,4)==1)System.out.println("YES");elseSystem.out.println("NO");}}
}