我的24点算法,希望大家执正
前边一个朋友要最优算法,我不敢现眼,后来又有朋友问我要24点的算法,我所性就贴出来,大家批判批判。指正者有分。
用了三个类
Get24.java
Combination.java
Prompt.java
//Get24.java
public class Get24
{
static String getOperator(int i){
switch(i){
case 0:
return "+";
case 1:
return "-";
case 2:
return "*";
default:
return "/";
}
}
static float cacu(float a,float b,int o){
switch(o){
case 0:
return a+b;
case 1:
return a-b;
case 2:
return a*b;
default:
return a/b;
}
}
static int getInt(String s){
int i=0;
try{
i=Integer.parseInt(s);
if(i<=0)
throw new NumberFormatException();
}catch(NumberFormatException nfe){
return getInt(Prompt.read("输入错误,重新输入: "));
}
return i;
}
static boolean equal(float a,float b){
if(Math.abs(a-b)<0.01f)
return true;
return false;
}
static int caculate(int[] arr,int x,int y,int z){
float a=(float)arr[0];
float b=(float)arr[1];
float c=(float)arr[2];
float d=(float)arr[3];
if(equal(cacu(cacu(cacu(a,b,x),c,y),d,z),24.0f))
return 1;
if(equal(cacu(cacu(a,b,x),cacu(c,d,z),y),24.0f))
return 2;
if(equal(cacu(cacu(a,cacu(b,c,y),x),d,z),24.0f))
return 3;
if(equal(cacu(a,cacu(cacu(b,c,y),d,z),x),24.0f))
return 4;
if(equal(cacu(a,cacu(b,cacu(c,d,z),y),x),24.0f))
return 5;
return -1;
}
static boolean cacu24(int[][] a){
int flag;
int[] op={0,1,2,3};
for(int i=0;i<a.length;i++){
for(int x=0;x<op.length;x++){
for(int y=0;y<op.length;y++){
for(int z=0;z<op.length;z++){
if((flag=caculate(a[i],x,y,z))>0){
printFormula(a[i],x,y,z,flag);
return true;
}
}
}
}
}
return false;
}
static void printFormula(int[] a,int x,int y,int z,int flag){
int xx=x>1?1:0;
int yy=y>1?1:0;
int zz=z>1?1:0;
StringBuffer sb=new StringBuffer();
if(flag==1){
if(yy>xx)
sb.append("(");
if(zz>xx||zz>yy)
sb.append("(");
sb.append(a[0]);
sb.append(getOperator(x));
sb.append(a[1]);
if(yy>xx)
sb.append(")");
sb.append(getOperator(y));
sb.append(a[2]);
if(zz>xx||zz>yy)
sb.append(")");
sb.append(getOperator(z));
sb.append(a[3]);
}
else if(flag==2){
if(yy>xx)
sb.append("(");
sb.append(a[0]);
sb.append(getOperator(x));
sb.append(a[1]);
if(yy>xx)
sb.append(")");
sb.append(getOperator(y));
if(yy>zz)
sb.append("(");
else if(yy==zz){
if((z==y&&y!=0&&y!=3)||(z!=y&&y!=0&&y!=2))
sb.append("(");
}
sb.append(a[2]);
sb.append(getOperator(z));
sb.append(a[3]);
if(yy>zz)
sb.append(")");
else if(yy==zz){
if((z==y&&y!=0&&y!=3)||(z!=y&&y!=0&&y!=2))
sb.append(")");
}
}
else if(flag==3){
if(zz>xx||zz>yy)
sb.append("(");
sb.append(a[0]);
sb.append(getOperator(x));
if(yy<xx)
sb.append("(");
else if(yy==xx){
if((x==y&&y!=0&&y!=3)||(x!=y&&x!=0&&x!=2))
sb.append("(");
}
sb.append(a[1]);
sb.append(getOperator(y));
sb.append(a[2]);
if(yy<xx)
sb.append(")");
else if(yy==xx){
if((x==y&&y!=0&&y!=3)||(x!=y&&x!=0&&x!=2))
sb.append(")");
}
if(zz>yy||zz>xx)
sb.append(")");
sb.append(getOperator(z));
sb.append(a[3]);
}
else if(flag==4){
sb.append(a[0]);
sb.append(getOperator(x));
if(xx>zz||xx>yy||x==1||x==3)
sb.append("(");
if(zz>yy)
sb.append("(");
sb.append(a[1]);
sb.append(getOperator(y));
sb.append(a[2]);
if(zz>yy)
sb.append(")");
sb.append(getOperator(z));
sb.append(a[3]);
if(xx>zz||xx>yy||x==1||x==3)
sb.append(")");
}
else if(flag==5){
sb.append(a[0]);
sb.append(getOperator(x));
if(xx>zz||xx>yy||x==1||x==3)
sb.append("(");
sb.append(a[1]);
sb.append(getOperator(y));
if(yy>zz||(yy==zz&&y!=0&&y!=2))
sb.append("(");
sb.append(a[2]);
sb.append(getOperator(z));
sb.append(a[3]);
if(xx>zz||xx>yy||x==1||x==3)
sb.append(")");
if(yy>zz||(yy==zz&&y!=0&&y!=2))
sb.append(")");
}
sb.append("=24");
System.out.println(sb);
}
public static void main(String[] args){
int numbers[]=new int[4];
System.out.println("请输入4个大于0的正整数");
for(int i=0;i<numbers.length;i++)
numbers[i]=getInt(Prompt.read("第 "+(i+1)+" 个整数为 :"));
int[][] a=Combination.getCombination(numbers);
System.out.println("====================================");
if(!cacu24(a))
System.out.println("无法用四则运算得到24。");
}
};