我觉得有几个分享的方法不对。
1.没有考虑到用括号的情况。比如:5 9 7 1,这个是能够计算出24的,9-5=4,7-1=6,4*6=24。用他们分享的代码运行是false。
2.对于拿到的第一个数值,有存在0/n的情况,比如:7 8 9 24(虽然24不符合传入要求),他们的代码会存在0/7/8/9=0,再0+24=24,因此返回true,事实上7 8 9 24四个数字无论怎么处理都计算不出24。
所以我自己写了以下代码,还是用的递归,做了一些修改
1.获取第一个数字时,直接将其当成临时结果
2.当已经使用两个数字计算出临时结果传入参数时,对另两个数字进行所有可能值的运算,再与临时结果进行所有可能值比较。
3.对于除法进行判断,确保不会除以0
import java.util.*; public class Main{ private static int[] arr;//用于接收传入的4个整数 private static int[] visited;//用于判断对应序号的整数有没有被使用。 public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ arr=new int[4];visited=new int[4]; for(int i=0;i<4;i++){ arr[i]=sc.nextInt(); } System.out.println(canGet24(0,0)); } } //使用递归,第一个参数表示已使用的数字数,第二个参数表示对已使用的数字进行运算后得到的临时结果 private static boolean canGet24(int cnt,double tmpres){ if(cnt==4 && tmpres==24){//如果用了4个了,且结果已经是24了,那就说明24运算成功。 return true; } if(cnt==0){//对于还没开始运算的情况,接收的第一个数值直接作为tmpres for(int i=0;i<4;i++){ visited[i]=1; if(canGet24(1,arr[i])){ return true; } visited[i]=0;//每一轮循环都要把访问记录恢复 } return false;//所有数字都试过了还没有得到24,说明不可能再得到。 } if(cnt==2){ //对于已经在两个数值参加运算的情况,要考虑两种可能 //1.另两个数字参加运算后再和当前结果运算。 int a=0,b=0;//剩下两个数值取到a,b中 for(int i=0;i<4;i++){ if(visited[i]==0){ if(a==0){ a=arr[i]; }else{ b=arr[i]; } } } for(double n:getAnyRes(a,b)){//对所有可能的ab运算结果进行判断 for(double m:getAnyRes(tmpres,n)){//对所有可能的tmpres和n的运算结果进行判断 if(m==24){ return true; } } } //2.当前结果与第三个数值参加运算。 for(int i=0;i<4;i++){ if(visited[i]==0){ visited[i]=1; if(canGet24(3,tmpres+arr[i])||canGet24(3,tmpres*arr[i])||//加和乘计算 canGet24(3,tmpres-arr[i])||canGet24(3,arr[i]-tmpres)){//减法计算 return true; } if(tmpres!=0 && canGet24(3,arr[i]/tmpres) ||arr[i]!=0 && canGet24(3,tmpres/arr[i])){//除法计算 return true; } visited[i]=0; } } return false;//所有情况都试过了,还是没有24出现,返回false } if(cnt==1||cnt==3){ for(int i=0;i<4;i++){ if(visited[i]==0){ visited[i]=1; if(canGet24(cnt+1,tmpres+arr[i])||canGet24(cnt+1,tmpres*arr[i])||//加和乘计算 canGet24(cnt+1,tmpres-arr[i])||canGet24(cnt+1,arr[i]-tmpres)){//减法计算 return true; } if(tmpres!=0 && canGet24(cnt+1,arr[i]/tmpres)|| arr[i]!=0 && canGet24(cnt+1,tmpres/arr[i])){//除法计算 return true; } visited[i]=0; } } }//不是1~4的返回false return false; } //以下函数用于返回两个数进行任何运算后可能的值,以列表形式返回。 private static List<Double> getAnyRes(double a,double b){ List<Double> res = new ArrayList<Double>(); res.add(a+b); res.add(a*b); res.add(a-b); res.add(b-a); if(a!=0){ res.add(b/a); } if(b!=0){ res.add(a/b); } return res; } }