题解 | #24点游戏算法#
24点游戏算法
http://www.nowcoder.com/practice/fbc417f314f745b1978fc751a54ac8cb
我觉得有几个分享的方法不对。
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;
}
}
