- 浏览: 40134 次
- 性别:
最新评论
问题描述
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 1335求最小公倍数方法如下: (1)、两数相乘法。 ... -
裴波那契算法
2012-05-18 21:40 840裴波那契算法,数组算法 #include<st ... -
一些的算法的格式
2012-05-17 12:15 1043做题目做久了之后就会发现,算法是有格式的。 一、深度优 ... -
第三届蓝桥杯预赛真题-C++本科组-10题(Java实现)
2012-05-15 11:11 943今盒子里有n个小球,A、B两人轮流从盒中取球,每个 ... -
第三届蓝桥杯预赛真题-C++高职组-10题(Java实现)
2012-05-15 10:57 12562x3=6个方格中放入ABCDE五个字母,右下角的那个 ... -
第三届蓝桥杯预赛真题-Java高职组-10题
2012-05-14 13:16 1942匪警请拨110,即使手机欠 ... -
第三届蓝桥杯预赛真题-Java本科组-10题
2012-05-14 12:41 1481泊松是法国数学家、物理学家和力学家。他一生致力科学事 ... -
八皇后-位运算版
2012-01-12 18:38 1188八皇后问题,是一 ... -
吸血鬼数字
2012-01-09 20:32 909题目: 吸血鬼数字是 ... -
字符串的排列(A(m,n)),可重复选
2012-01-09 13:28 1269题目:现有ABCDE 5个球 构成的排列组合 可重复抽取 最多 ... -
蛇形矩阵
2012-01-09 13:38 1018Problem蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上 ... -
寻找最短路径
2012-01-07 18:51 1146题目:给定一个起点和一个终点。在一个8*8的棋盘上找出一条最短 ... -
字符串的排列(A(m,n))
2012-01-07 18:18 954题目:有A,B,C,D,E 5个字母,从其中任选3个,要求列出 ... -
字符串的组合(C(m,n))
2012-01-07 17:46 1335题目:有A,B,C,D,E 5个字母,从其中任选3个,要求列出 ... -
汉诺塔
2012-01-07 17:32 918关于汉诺塔大家应该很熟悉吧。 河內之塔(Towers ... -
三角螺旋矩阵
2012-01-07 17:27 1083打印如下矩阵,如果 n=7 则输出: 1 18 2 ...
相关推荐
(1)用多时期二叉树模型来近似风险中性几何布朗运动,通过连续复利的原理计算出股票价格的上升因子和下降因子。 (2)构建二叉树,计算其t(k)时刻可能的期权价格。 (3)根据期权属性(美式、看跌)以及期权执行价格与最后...
本次实验是利用二叉排序树和平衡二叉树达到以下目的:(1)以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T;(2)对二叉排序树T作中序遍历,输出结果;(3)计算二叉排序树T查找成功的平均查找长度,输出结果...
编译原理经典教材 目录 第一章引论 1.1什么叫编译程序 1.2编译过程概述 1.3编译程序的结构 1.3.1编译程序总框 1.3.2表格与表格管理 1.3.3出错处理 1.3.4遍 1.3.5编译前端与后端 1.4编译程序与程序设计...
摘 要:哈夫曼编码是一种数据编码方式,以哈夫曼树——...夫曼编码图像压缩技术的原理、算法、过程,并利用VB6.0作为编程开发工具,开发了一个对256色BMP图像进行压缩/解压缩的软件系统, 验证了算法的合理性和可行性。
例如,在一维数组[21,46,24,99,57,77,86]中,查找数据元素99,首先从第1个元素21开始进行比较,比较结果与要查找的数据不相等,接着与第2个元素46进行比较,以此类推,当进行到与第4个元素比较时,它们相等,...
c#四则混合运算算法,利用二叉树中序表达式和后序表达式原理,和编译原理的词法规则,栈数据结构完成的四则混合运算
第三,高效记忆:遵循认知科学原理,导图利用色彩、图形与层级关系,激发大脑联想记忆,使枯燥的知识点生动立体,大幅提升记忆效果。无论是短期突击还是长期巩固,都能助您轻松记忆,显著提高复习效率。 第四,灵活...
(13) 设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为(B) 注:利用公式n=n0+n1+n2、n0=n2+1和完全二叉数的特点可求出 A. 349 B. 350 C. 255 D. 351 (14) 结构化程序设计主要强调的是(B) A.程序的规模 ...
·对讨论单源最短路径的第24章做了重新组织,把对基本性质的证明移到了各自的节中。这种新的结构使我们可以更早地将注意力放在算法上。 ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路...
35、 编写计算二叉树最大宽度的算法(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。 回溯法 36、 (组合问题)求出从自然数1,2,…,n中任取r个数的所有组合。 37、 传教士与野人渡河问题。有M个传教士...
32.3 利用有限自动机进行字符串匹配 32.4 Knuth?Morris?Pratt算法 思考题 本章注记 第33章 计算几何学 33.1 线段的性质 33.2 确定任意一对线段是否相交 33.3 寻找凸包 33.4 寻找最近点对 ...
·对讨论单源最短路径的第24章做了重新组织,把对基本性质的证明移到了各自的节中。这种新的结构使我们可以更早地将注意力放在算法上。 ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路...
为了消除测距定位追踪活动目标的测量误差,通过利用四个移动传感器感知活动目标M,由任意三个传感器所得的信息计算出目标M的位置分别为M1、M2、M3、M4,由其四点所围成的凸区域的形心或其所围成的凹区域的主骨架线...
事务控制语言(Transactional Control Language,TCL),用于维护数据的一致性,包括COMMIT(提交事务)、ROLLBACK(回滚事务)和SAVEPOINT(设置保存点)3条语句 二、 Oracle的数据类型 类型 参数 描述 字符类型...
通常数据结构课程实验是由教师将问题描述和基本要求作为实验题目给出,但又绝不是让学生拿到实验题目就直接上机进行编程调试,而是要通过在实验中贯穿软件工程的方法和原理,严格按照分析、设计、实现、测试等软件...
请用java写二叉树算法,实现添加数据形成二叉树功能,并以先序的方式打印出来. 43.请写一个java程序实现线程连接池功能? 44.给定一个C语言函数,要求实现在java类中进行调用。 45.如何获得数组的长度? 46....
visual c# 2010新增了大量可圈可点的丰富特性,本书围绕着基础知识和这些新特性全面介绍了如何利用visual studio 2010和.net framework 4.0编写应用程序。书中沿袭深受读者欢迎的step by step风格,通过丰富的练习...