当前位置: 代码迷 >> 综合 >> 算24 递归
  详细解决方案

算24 递归

热度:52   发布时间:2024-01-15 07:30:52.0

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");}}
}

 

  相关解决方案