计算24点-利用二叉树原理

问题描述

80年代全世界流行一种数字游戏，在中国我们把这种游戏称为“24点”。现在我们
把这个有趣的游戏推广一下：您作为游戏者将得到4个不同的自然数作为操作数，
而您的任务是对这4个操作数进行适当的算术运算，您可以使用的运算只有：+，-，*，/，

您还可以使用（）来改变运算顺序。注意：
所有的中间结果必须是整数，所以一些除法运算是不允许的（例如，（2*2）/4是
合法的，2*（2/4）是不合法的）
下面我们给出一个游戏的具体例子：

3，4，5，7

计算:
Step 1:  3.0*4.0=12.0
Step 2:  5.0+7.0=12.0
Step 3:  12.0+12.0=24.0

请写出代码实现

 

import java.util.Scanner;

public class ErShiSi {
	 //输入的4个数字：
	  private float[] inputedNumbers = new float[4];
	  //算法需要把输入的4个数字按一定规则排序：
	  private float[] sortedNumbers = new float[4];
	//本算法中最重要的数据结构，模拟二叉树，result[0]是根结点，如果得到result[0]的值为24，就算出来了
	  private float result[] = new float[9];
	  //创建一棵二叉树
	  private void clearResult()
	  {
		   for (int i = 0; i < 9; i++)
		   {
		    result[i] = 0;
		   }
	}
	  
	  //给二叉树中指定结点赋值：
	  private void setResult(int index,float value){
	   result[index] = value;
	  }
	  //得到二叉树中指定结点的值：
	  private float getResult(int index){
	   return result[index];
	  }
	  //排序算法所需要的下标数组：
	  private int[][] indexs = {
			    {0,1,2,3},{0,1,3,2},{0,2,1,3}, {0,2,3,1},{0,3,1,2},{0,3,2,1},{1,0,2,3},
			    {1,0,3,2},{1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0},{2,0,1,3},{2,0,3,1},
			    {2,1,0,3},{2,1,3,0},{2,3,0,1},{2,3,1,0},{3,0,1,2},{3,0,2,1},{3,1,0,2},
			    {3,1,2,0},{3,2,0,1},{3,2,1,0}
			  };
	  
	  //排序方法：
	  private void sortNumbers(int rnd){
	   if(rnd < 0 || rnd > 23){
	    System.out.println("Error!");
	    return;
	   }
	   sortedNumbers[0] = inputedNumbers[indexs[rnd][0]];
	   sortedNumbers[1] = inputedNumbers[indexs[rnd][1]];
	   sortedNumbers[2] = inputedNumbers[indexs[rnd][2]];
	   sortedNumbers[3] = inputedNumbers[indexs[rnd][3]];
	  }
	  
	//生成算式：
	  private String getNumSentence(int intOptr,float opnd1,float opnd2,float rst){
	   String ret = "";
	   switch(intOptr){
	    case 0:
	     ret = opnd1 + "+" + opnd2 + "=" + rst;
	     break;
	    case 1:
	     ret = opnd1 + "-" + opnd2 + "=" + rst;
	     break;
	    case 2:
	     ret = opnd2 + "-" + opnd1 + "=" + rst;
	     break;
	    case 3:
	     ret = opnd1 + "*" + opnd2 + "=" + rst;
	     break;
	    case 4:
	     ret = opnd1 + "/" + opnd2 + "=" + rst;
	     break;
	    case 5:
	     ret = opnd2 + "/" + opnd1 + "=" + rst;
	     break;
	   
	   }
	   return ret;
	  }
	  //表示是第几回合（一共要经过24回合）
	  private int round = 0;
	  public int getRound() {
	   return this.round;
	  }
	  public void setRound(int round) {
	   this.round = round;
	  }
	  //打印计算出的结果：
	  //因为有两种结构的二叉树，故需要两个方法分别对应于它们
	  private void printResult(int optr1,int optr2,int optr3){
	  
	   String str="Round " + (this.getRound() + 1)  +":"+"\r\n"+
	   "Step 1:  "+this.getNumSentence(optr1,this.getResult(3),this.getResult(4),this.getResult(1))+"\r\n"+
	   "Step 2:  "+this.getNumSentence(optr2,this.getResult(5),this.getResult(6),this.getResult(2))+"\r\n"+
	   "Step 3:  "+this.getNumSentence(optr3,this.getResult(1),this.getResult(2),this.getResult(0));
	   System.out.println(str);
	  
	  }
	  
	  private void printResult_1(int optr1,int optr2,int optr3){
	
	   String str="Round " + (this.getRound() + 1) + ":"+"\r\n"+
	   "Step 1:  "+this.getNumSentence(optr1,this.getResult(7),this.getResult(8),this.getResult(3))+"\r\n"+
	   "Step 2:  "+this.getNumSentence(optr2,this.getResult(3),this.getResult(4),this.getResult(1))+"\r\n"+
	   "Step 3:  "+this.getNumSentence(optr3,this.getResult(1),this.getResult(2),this.getResult(0));
	   System.out.println(str);
	  

	  }
	   //根据运算符代码、2个操作数，得到中间结果：
	  private float getMidValue(int i,float m,float n){
	   float ret = 0f;
	   switch(i){
	    case 0:
	     ret = m + n;
	     break;
	     
	    case 1:
	     ret = m - n;
	     break;
	     
	    case 2:
	     ret = n - m;
	     break;
	     
	    case 3:
	     ret = m * n;
	     break;
	     
	    case 4:
	     try{
	      ret = m / n;
	     }catch(Exception ex1){
	      ret = Float.MAX_VALUE;
	     }
	     break;
	     
	    case 5:
	     try{
	      ret = n / m;
	     }catch(Exception ex2){
	      ret = Float.MAX_VALUE;
	     }
	     break;
	   
	   }
	   return ret;
	  }
	  //因为有两种结构的二叉树，计算24的算法也有两种：
	  private void calculate(){
	   clearResult();
	   setResult(3,sortedNumbers[0]);
	   setResult(4,sortedNumbers[1]);
	   setResult(5,sortedNumbers[2]);
	   setResult(6,sortedNumbers[3]);
	   for(int i = 0;i < 6;i++){
	    setResult(1,getMidValue(i,getResult(3),getResult(4)));
	    for(int j = 0;j < 6;j++){
	     setResult(2,getMidValue(j,getResult(5),getResult(6)));
	     for(int k = 0;k < 6;k++){
	      setResult(0,getMidValue(k,getResult(1),getResult(2)));
	      if(Math.abs(getResult(0) - 24) < 0.0000001){	 
	       printResult(i,j,k);
	       return;
	      }
	      if(i == 5 && j == 5 && k == 5){
	       calculate_1();
	      }
	     }
	    }
	   }
	  }
	  //第2种后备算法：
	  private void calculate_1(){
	   clearResult();
	   setResult(7,sortedNumbers[0]);
	   setResult(8,sortedNumbers[1]);
	   setResult(4,sortedNumbers[2]);
	   setResult(2,sortedNumbers[3]);
	   for(int i = 0;i < 6;i++){
	    setResult(3,getMidValue(i,getResult(7),getResult(8)));
	    for(int j = 0;j < 6;j++){
	     setResult(1,getMidValue(j,getResult(3),getResult(4)));
	     for(int k = 0;k < 6;k++){
	      setResult(0,getMidValue(k,getResult(1),getResult(2)));
	      if(Math.abs(getResult(0) - 24) < 0.0000001){	 
	       printResult_1(i,j,k);
	       return;
	      }else if(i == 5 && j == 5 && k == 5){
	       System.out.println("No solution at round "+(this.getRound()+1)+"!");
	       return;
	      }
	     }
	    }
	   }
	} 
	   //提取输入的4个数字，存入数组inputedNumbers
	  private boolean setNumbers(String[] str){
	   if(str.length != 4){
	    System.out.println("Please input 4 Integers!");
	    return false;
	   }
	   try{
	    inputedNumbers[0] = Integer.parseInt(str[0]);
	    inputedNumbers[1] = Integer.parseInt(str[1]);
	    inputedNumbers[2] = Integer.parseInt(str[2]);
	    inputedNumbers[3] = Integer.parseInt(str[3]);
	   }catch(Exception ex){
	    System.out.println("Please input 4 Integers!");
	    return false;
	   }
	   return true;
	  }
	  public static void main(String[] args){
		    ErShiSi er = new ErShiSi();
		    Scanner scan=new Scanner(System.in);
		    String str []={"3","4","5","7"};//测试数据
		    if(!er.setNumbers(str)){return;}
		    for(int i = 0; i < 24; i++){
			    er.setRound(i);
			    er.sortNumbers(i);
			    er.calculate();
		    }
	  }

}

 输出结果：
Round 1:
Step 1:  3.0*4.0=12.0
Step 2:  5.0+7.0=12.0
Step 3:  12.0+12.0=24.0
Round 2:
Step 1:  3.0*4.0=12.0
Step 2:  7.0+5.0=12.0
Step 3:  12.0+12.0=24.0
Round 3:
Step 1:  3.0+5.0=8.0
Step 2:  7.0-4.0=3.0
Step 3:  8.0*3.0=24.0
Round 4:
Step 1:  3.0+5.0=8.0
Step 2:  7.0-4.0=3.0
Step 3:  8.0*3.0=24.0
Round 5:
Step 1:  3.0-7.0=-4.0
Step 2:  4.0*5.0=20.0
Step 3:  20.0--4.0=24.0
Round 6:
Step 1:  3.0-7.0=-4.0
Step 2:  5.0*4.0=20.0
Step 3:  20.0--4.0=24.0

.......

很明显看出有很多是重复的，不知道哪位高手能优化一下。去除那些重复的。在这里谢谢了。