`

计算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

.......

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

分享到:
评论

相关推荐

    C++数据结构-计算二叉树最大的宽度

    总结起来,计算二叉树最大宽度的关键在于理解层次遍历的工作原理,并利用队列和数组有效地存储和处理数据。通过这样的方法,我们可以在O(n)的时间复杂度内解决这个问题,其中n是二叉树中的节点数。

    算法-扩展二叉树(信息学奥赛一本通-T1340)(包含源程序).rar

    通过学习和理解扩展二叉树的原理以及如何利用其特性,选手能够更有效地设计算法,提高解题速度和准确性。 提供的源程序可能包含实现扩展二叉树的各种示例,包括如何构建树、进行插入和删除操作、进行区间查询和更新...

    实验五-二叉树基本操作的编程实现实验报告.doc

    - **排列问题**:利用二叉树结构可以有效地生成集合的所有排列。 - **组合问题**:同样地,二叉树可以用来生成组合。 ### 实验小结 - **收获与体会**: - 通过本次实验,加深了对二叉树及其基本操作的理解。 -...

    二叉树_二叉树_

    - 搜索算法:二分查找算法利用了二叉搜索树的特性。 - 表达式解析:二叉表达式树用于解析和计算数学表达式。 - 树形菜单:网页或软件中的层级菜单可以表示为二叉树。 6. **节点和路径**: - 节点操作:包括节点...

    java简单实现二叉树

    为了更好地利用二叉树,可以考虑以下扩展功能: - **遍历方法**:包括前序遍历、中序遍历和后序遍历。 - **查找方法**:实现基于节点值的查找功能。 - **插入与删除**:支持动态地插入新节点或删除现有节点。 通过...

    数据结构(二叉树)家谱管理系统.zip

    本系统“数据结构(二叉树)家谱管理系统”深入探讨了如何利用二叉树这一特定的数据结构来有效地管理和操作家谱数据。下面我们将详细讨论二叉树的相关概念及其在家谱管理中的应用。 二叉树是一种特殊的图结构,每个...

    基于BS模型-二叉树模型-傅里叶变换-蒙特卡洛模拟实现期权定价.zip

    在金融工程领域,期权定价是核心问题之一,而计算期权价格的方法多种多样,其中包括经典的Black-Scholes(BS)模型、二叉树模型、傅里叶变换法以及蒙特卡洛模拟。这些方法各有特点,适用于不同的场景。下面将详细...

    计算机软件基础 静态链表、二叉树等

    二叉树则可以利用其内在的排序特性进行排序,比如在二叉搜索树中,中序遍历即可得到有序序列。此外,二叉树还可以用于实现高效的排序算法,例如堆排序,通过构造一个最大堆或最小堆来实现排序。 数组是另一个基础...

    _基于二叉树的美式期权定价研究_基于二叉树的美式期权定价研究

    通过以上步骤,可以利用二叉树模型计算出不同情景下的期权理论价格,并与市场实际价格进行对比,以此评估模型的有效性和适用范围。 ### 结论 通过对二叉树模型的应用研究,可以看出这种模型在美式期权定价方面具有...

    算法与数据结构-二叉树的建立与遍历.docx

    例如,二叉树的先序遍历可以用来解释计算表达式,因为它遵循运算符优先级规则,先处理括号内的内容,然后是乘除,最后是加减。 在实际操作中,理解和掌握二叉树的建立与遍历至关重要。在构建二叉树时,需要理解如何...

    二叉树遍历算法的应用

    在本文中,我们将深入探讨二叉树遍历的原理及其在统计二叉树节点数量、叶子节点计数以及计算树深等方面的应用。 二叉树遍历通常包括三种基本方法:前序遍历(先根遍历)、中序遍历和后序遍历。这些方法的核心在于...

    看涨期权定价的二叉树方法matlab程序

    根据给定的信息,本文将详细解释“看涨期权定价的二叉树方法”的核心概念、原理及其在MATLAB中的实现。 ### 一、看涨期权定价的二叉树方法概述 #### 1.1 什么是期权 期权是一种金融衍生工具,它赋予持有人在未来某...

    完全二叉树 的种类

    为了更好地理解这段代码及其背后的数学原理和技术背景,我们需要深入探讨完全二叉树的概念、种类以及与之相关的算法实现。 ### 完全二叉树的基本概念 在计算机科学中,二叉树是一种常用的数据结构,它由节点组成,...

    数据结构二叉树遍历递归,非递归

    在二叉树遍历中,我们利用函数调用自身来处理树的不同部分。 1. **前序遍历**(根-左-右): - 递归版本:首先访问根节点,然后递归遍历左子树,最后递归遍历右子树。 - 非递归版本:使用栈来模拟递归过程。首先...

    树与二叉树_习题

    在计算机科学中,树与二叉树是两种重要的数据结构,它们在算法设计、数据库管理、编译原理等领域有着广泛的应用。本节我们将深入探讨树与二叉树的相关习题和知识点。 首先,我们来看一个关于满二叉树的问题。一棵...

    二叉树的顺序存储,数据结构

    总结起来,这个项目涉及到的主要知识点包括:二叉树的概念、二叉树的顺序存储(二叉链表)、VC++编程、类和对象的使用、以及基本的算法实现,如遍历、插入和删除。通过这样的实践,可以加深对数据结构和算法的理解,...

    VC二叉排序树和平衡二叉树计算程序

    在提供的"VC二叉排序树和平衡二叉树计算程序"中,可能包含了创建、插入、删除节点的函数,以及可能的可视化界面,帮助用户直观地理解操作过程。通过这个程序,你可以实际操作并理解这两种数据结构的工作原理和性能...

    二叉树美式看跌期权的定价

    (1)用多时期二叉树模型来近似风险中性几何布朗运动,通过连续复利的原理计算出股票价格的上升因子和下降因子。 (2)构建二叉树,计算其t(k)时刻可能的期权价格。 (3)根据期权属性(美式、看跌)以及期权执行价格与最后...

    二叉树的节点个数

    #### 四、算法原理 1. **递归思想**:本问题的核心在于递归地构建二叉树和计算节点个数。利用递归可以简化问题,将构建大问题分解为构建小问题,直到问题变得足够简单可以直接解决。 2. **前序遍历的应用**:前序...

Global site tag (gtag.js) - Google Analytics