- 浏览: 41790 次
- 性别:
最新评论
问题描述
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
.......
很明显看出有很多是重复的,不知道哪位高手能优化一下。去除那些重复的。在这里谢谢了。
发表评论
-
2012-03-16 20:52 最大公约数;最小公倍数
2012-05-18 21:45 1373求最小公倍数方法如下: (1)、两数相乘法。 ... -
裴波那契算法
2012-05-18 21:40 893裴波那契算法,数组算法 #include<st ... -
一些的算法的格式
2012-05-17 12:15 1086做题目做久了之后就会发现,算法是有格式的。 一、深度优 ... -
第三届蓝桥杯预赛真题-C++本科组-10题(Java实现)
2012-05-15 11:11 976今盒子里有n个小球,A、B两人轮流从盒中取球,每个 ... -
第三届蓝桥杯预赛真题-C++高职组-10题(Java实现)
2012-05-15 10:57 12822x3=6个方格中放入ABCDE五个字母,右下角的那个 ... -
第三届蓝桥杯预赛真题-Java高职组-10题
2012-05-14 13:16 1993匪警请拨110,即使手机欠 ... -
第三届蓝桥杯预赛真题-Java本科组-10题
2012-05-14 12:41 1523泊松是法国数学家、物理学家和力学家。他一生致力科学事 ... -
八皇后-位运算版
2012-01-12 18:38 1248八皇后问题,是一 ... -
吸血鬼数字
2012-01-09 20:32 943题目: 吸血鬼数字是 ... -
字符串的排列(A(m,n)),可重复选
2012-01-09 13:28 1312题目:现有ABCDE 5个球 构成的排列组合 可重复抽取 最多 ... -
蛇形矩阵
2012-01-09 13:38 1060Problem蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上 ... -
寻找最短路径
2012-01-07 18:51 1177题目:给定一个起点和一个终点。在一个8*8的棋盘上找出一条最短 ... -
字符串的排列(A(m,n))
2012-01-07 18:18 990题目:有A,B,C,D,E 5个字母,从其中任选3个,要求列出 ... -
字符串的组合(C(m,n))
2012-01-07 17:46 1403题目:有A,B,C,D,E 5个字母,从其中任选3个,要求列出 ... -
汉诺塔
2012-01-07 17:32 974关于汉诺塔大家应该很熟悉吧。 河內之塔(Towers ... -
三角螺旋矩阵
2012-01-07 17:27 1121打印如下矩阵,如果 n=7 则输出: 1 18 2 ...
相关推荐
总结起来,计算二叉树最大宽度的关键在于理解层次遍历的工作原理,并利用队列和数组有效地存储和处理数据。通过这样的方法,我们可以在O(n)的时间复杂度内解决这个问题,其中n是二叉树中的节点数。
通过学习和理解扩展二叉树的原理以及如何利用其特性,选手能够更有效地设计算法,提高解题速度和准确性。 提供的源程序可能包含实现扩展二叉树的各种示例,包括如何构建树、进行插入和删除操作、进行区间查询和更新...
- **排列问题**:利用二叉树结构可以有效地生成集合的所有排列。 - **组合问题**:同样地,二叉树可以用来生成组合。 ### 实验小结 - **收获与体会**: - 通过本次实验,加深了对二叉树及其基本操作的理解。 -...
- 搜索算法:二分查找算法利用了二叉搜索树的特性。 - 表达式解析:二叉表达式树用于解析和计算数学表达式。 - 树形菜单:网页或软件中的层级菜单可以表示为二叉树。 6. **节点和路径**: - 节点操作:包括节点...
为了更好地利用二叉树,可以考虑以下扩展功能: - **遍历方法**:包括前序遍历、中序遍历和后序遍历。 - **查找方法**:实现基于节点值的查找功能。 - **插入与删除**:支持动态地插入新节点或删除现有节点。 通过...
本系统“数据结构(二叉树)家谱管理系统”深入探讨了如何利用二叉树这一特定的数据结构来有效地管理和操作家谱数据。下面我们将详细讨论二叉树的相关概念及其在家谱管理中的应用。 二叉树是一种特殊的图结构,每个...
在金融工程领域,期权定价是核心问题之一,而计算期权价格的方法多种多样,其中包括经典的Black-Scholes(BS)模型、二叉树模型、傅里叶变换法以及蒙特卡洛模拟。这些方法各有特点,适用于不同的场景。下面将详细...
二叉树则可以利用其内在的排序特性进行排序,比如在二叉搜索树中,中序遍历即可得到有序序列。此外,二叉树还可以用于实现高效的排序算法,例如堆排序,通过构造一个最大堆或最小堆来实现排序。 数组是另一个基础...
通过以上步骤,可以利用二叉树模型计算出不同情景下的期权理论价格,并与市场实际价格进行对比,以此评估模型的有效性和适用范围。 ### 结论 通过对二叉树模型的应用研究,可以看出这种模型在美式期权定价方面具有...
例如,二叉树的先序遍历可以用来解释计算表达式,因为它遵循运算符优先级规则,先处理括号内的内容,然后是乘除,最后是加减。 在实际操作中,理解和掌握二叉树的建立与遍历至关重要。在构建二叉树时,需要理解如何...
在本文中,我们将深入探讨二叉树遍历的原理及其在统计二叉树节点数量、叶子节点计数以及计算树深等方面的应用。 二叉树遍历通常包括三种基本方法:前序遍历(先根遍历)、中序遍历和后序遍历。这些方法的核心在于...
根据给定的信息,本文将详细解释“看涨期权定价的二叉树方法”的核心概念、原理及其在MATLAB中的实现。 ### 一、看涨期权定价的二叉树方法概述 #### 1.1 什么是期权 期权是一种金融衍生工具,它赋予持有人在未来某...
为了更好地理解这段代码及其背后的数学原理和技术背景,我们需要深入探讨完全二叉树的概念、种类以及与之相关的算法实现。 ### 完全二叉树的基本概念 在计算机科学中,二叉树是一种常用的数据结构,它由节点组成,...
在二叉树遍历中,我们利用函数调用自身来处理树的不同部分。 1. **前序遍历**(根-左-右): - 递归版本:首先访问根节点,然后递归遍历左子树,最后递归遍历右子树。 - 非递归版本:使用栈来模拟递归过程。首先...
在计算机科学中,树与二叉树是两种重要的数据结构,它们在算法设计、数据库管理、编译原理等领域有着广泛的应用。本节我们将深入探讨树与二叉树的相关习题和知识点。 首先,我们来看一个关于满二叉树的问题。一棵...
总结起来,这个项目涉及到的主要知识点包括:二叉树的概念、二叉树的顺序存储(二叉链表)、VC++编程、类和对象的使用、以及基本的算法实现,如遍历、插入和删除。通过这样的实践,可以加深对数据结构和算法的理解,...
在提供的"VC二叉排序树和平衡二叉树计算程序"中,可能包含了创建、插入、删除节点的函数,以及可能的可视化界面,帮助用户直观地理解操作过程。通过这个程序,你可以实际操作并理解这两种数据结构的工作原理和性能...
(1)用多时期二叉树模型来近似风险中性几何布朗运动,通过连续复利的原理计算出股票价格的上升因子和下降因子。 (2)构建二叉树,计算其t(k)时刻可能的期权价格。 (3)根据期权属性(美式、看跌)以及期权执行价格与最后...
#### 四、算法原理 1. **递归思想**:本问题的核心在于递归地构建二叉树和计算节点个数。利用递归可以简化问题,将构建大问题分解为构建小问题,直到问题变得足够简单可以直接解决。 2. **前序遍历的应用**:前序...