java编程实现求解八枚银币代码分享
1、引言
笔者在大学的算法竞赛中，遇到过这样的一个题目，现在拿出来与大家分享一下：现在有现有八枚银币abcdefgh，已知其中一枚是假币，其重量不同于真币，但不知是较轻或较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较重。
2、分析
如果本题目只是很单纯的求解假币是哪一个，问题倒并不是很复杂，只需要回溯递归便可求得结果。问题的难点在意，我们需要用最少的步骤！！！
比之以前的数据结构问题，有递归，回溯，我们今天可能要接触一个新的概念，叫做树。顾名思义，数结构就是说我们的分析图示像树一样，有分支节点等各种信息。树结构是数据结构中的一个较大的章节，不在我们的讨论之中，在本题目当中，我们会介绍树的一个小小的分子，决策树。
我们先建立一下，八个银币求解的数学模型。一个简单的状况是这样的，我们将银币依次命名为abcdefg等，我们比较a+b+c与d+e+f，如果相等，则假币必是g或h，我们先比较g或h哪个较重，如果g较重，再与a比较（a是真币），如果g等于a，则g为真币，则h为假币，由于h比g轻而g是真币，则h假币的重量比真币轻。
如果不相等呢？又是何种情况，我们将依次分支回溯比较，直到得到最终的答案！
3、示例图
根据上面的分析，我们可以有一个完整的决策树图示：
4、代码
public class Coins {
private int[] coins;
public Coins() {
coins = new int[8];
for(int i = 0; i < 8; i++)
coins[i] = 10;
}
public void setFake(int weight) {
coins[(int) (Math.random() * 7)] = weight;
}
public void fake() {
if(coins[0]+coins[1]+coins[2] ==
coins[3]+coins[4]+coins[5]) {
if(coins[6] > coins[7])
compare(6, 7, 0);
else
compare(7, 6, 0);
}
else if(coins[0]+coins[1]+coins[2] >
coins[3]+coins[4]+coins[5]) {
if(coins[0]+coins[3] == coins[1]+coins[4])
compare(2, 5, 0);
else if(coins[0]+coins[3] > coins[1]+coins[4])
compare(0, 4, 1);
if(coins[0]+coins[3] < coins[1]+coins[4])
compare(1, 3, 0);
}
else if(coins[0]+coins[1]+coins[2] <
coins[3]+coins[4]+coins[5]) {
if(coins[0]+coins[3] == coins[1]+coins[4])
compare(5, 2, 0);
else if(coins[0]+coins[3] > coins[1]+coins[4])
compare(3, 1, 0);
if(coins[0]+coins[3] < coins[1]+coins[4])
compare(4, 0, 1);
}
}
protected void compare(int i, int j, int k) {
if(coins[i] > coins[k])
System.out.print("\n假币 " + (i+1) + " 较重");
else
System.out.print("\n假币 " + (j+1) + " 较轻");
}
public static void main(String[] args) {
if(args.length == 0) {
System.out.println("输入假币重量（比10大或小）");
System.out.println("ex. java Coins 5");
return;
}
Coins eightCoins = new Coins();
eightCoins.setFake(Integer.parseInt(args[0]));
eightCoins.fake();
}
}
结果：
输入假币重量（比10大或小）
ex. java Coins 5
这里是一段通用的解题方法，大家可以仔细琢磨代码，对于本段代码，上面的分析已经足够，剩下的就要大家自己琢磨学习了，这样才能深刻理解。
总结
以上就是本文关于java编程实现求解八枚银币代码分享的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
相关推荐
-
Java数据结构之简单链表的定义与实现方法示例
本文实例讲述了Java数据结构之简单链表的定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 只有一个数据项(链接点Link),每个数据插入时都是对第一个数据的引用. 2.插入数据说明: 当链表没有数据时,插入的值就是第一个数据,如果链表里有数据,就把当前的数据的next指针指向第一个数据. 3.插入数据图: 4.特点:先进后出 5.实现功能: 数据插入,指定位置插入,显示,查询,删除等 6.删除原理 7.插入头节点原理 二.实现: 1.创建节点 /** * @描述 节点
-
Java数据结构之双端链表原理与实现方法
本文实例讲述了Java数据结构之双端链表原理与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.什么时双端链表: 链表中保持这对最后一个连点引用的链表 2.从头部插入 要对链表进行判断,如果为空则设置尾节点为新添加的节点 3.从尾部进行插入 如果链表为空,则直接设置头节点为新添加的节点,否则设置尾节点的后一个节点为新添加的节点 4.从头部删除 判断节点是否有下个节点,如果没有则设置节点为null 二.具体实现 /** * @描述 头尾相接的链表 * @项目名称 Java_DataStr
-
java数据结构之二分查找法 binarySearch的实例
java数据结构之二分查找法 binarySearch的实例 折半查找法,前提是已经排好序的数组才可查找 实例代码: public class BinarySearch { int[] bArr; public void setArr(int[] bArr){ this.bArr=bArr; } public static void main(String[] args) { int arrLength=16; int[] bArr=new int[arrLength]; System.out.
-
Java数据结构之简单的连接点(link)实现方法示例
本文实例讲述了Java数据结构之简单的连接点(link)实现方法.分享给大家供大家参考,具体如下: 一.概述: 链接点由:数据和指向下个数据的指针构成 如图: 二.简单实现: package com.java.link; /** * @描述 TODO * @项目名称 Java_DataStruct * @包名 com.java.link * @类名 Link * @author chenlin */ public class Link { private long data; private L
-
Java数据结构之栈的基本定义与实现方法示例
本文实例讲述了Java数据结构之栈的基本定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.基本概念: 栈是一种数据结构,是只能在某一端插入和删除的特殊线性表.它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来). 栈是允许在同一端进行插入和删除操作的特殊线性表.允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom):栈底固定,而栈顶 浮动:栈中元素个数为零时称为空栈.插入一般
-
详解Java数据结构和算法（有序数组和二分查找）
一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默
-
Java数据结构之红黑树的真正理解
真正的帮助大家理解红黑树: 一.红黑树所处数据结构的位置: 在JDK源码中, 有treeMap和JDK8的HashMap都用到了红黑树去存储 红黑树可以看成B树的一种: 从二叉树看,红黑树是一颗相对平衡的二叉树 二叉树-->搜索二叉树-->平衡搜索二叉树--> 红黑树 从N阶树看,红黑树就是一颗 2-3-4树 N阶树-->B(B-)树 故我提取出了红黑树部分的源码,去说明红黑树的理解 看之前,理解红黑树的几个特性,后面的操作都是为了让树符合红黑树的这几个特性,从而满足对查找效率的O
-
java 数据结构中栈和队列的实例详解
java 数据结构中栈和队列的实例详解 栈和队列是两种重要的线性数据结构,都是在一个特定的范围的存储单元中的存储数据.与线性表相比,它们的插入和删除操作收到更多的约束和限定,又被称为限定性的线性表结构.栈是先进后出FILO,队列是先进先出FIFO,但是有的数据结构按照一定的条件排队数据的队列,这时候的队列属于特殊队列,不一定按照上面的原则. 实现栈:采用数组和链表两种方法来实现栈 链表方法: package com.cl.content01; /* * 使用链表来实现栈 */ public cl
-
java编程实现求解八枚银币代码分享
1.引言 笔者在大学的算法竞赛中,遇到过这样的一个题目,现在拿出来与大家分享一下:现在有现有八枚银币abcdefgh,已知其中一枚是假币,其重量不同于真币,但不知是较轻或较重,如何使用天平以最少的比较次数,决定出哪枚是假币,并得知假币比真币较轻或较重. 2.分析 如果本题目只是很单纯的求解假币是哪一个,问题倒并不是很复杂,只需要回溯递归便可求得结果.问题的难点在意,我们需要用最少的步骤!!! 比之以前的数据结构问题,有递归,回溯,我们今天可能要接触一个新的概念,叫做树.顾名思义,数结构就是说我们
-
Java编程几个循环实例代码分享
有关Java循环的内容,编程中还是比较常用的,下面分享给大家几个循环的示例代码,练习一下. 1.循环输出1到100之间所有能被3或能被4整除的数. package com.hz.loop02; /** * 1.循环输出1到100之间所有能被3或能被4整除的数. * @author ztw * */ public class Practice01 { public static void main(String[] args) { for (int i=1;i<=100;i++){ //判断下是否
-
Java编程一个随机数产生模块代码分享
java随机数的产生比较简单,可以通过 Random rand = new Random(47); System.out.println(rand.nextInt()); 产生,也可以通过以下产生: double d = Math.random(); 当然代码中前者由于使用了固定的种子47,所以每次的值都是一样的,也可以使用 Random rand = new Random(); System.out.println(rand.nextInt()); 而对于代码2则产生的是double的随机数.
-
Java编程实现swing圆形按钮实例代码
Swing是一个为Java设计的GUI工具包. Swing是JAVA基础类的一部分. Swing包括了图形用户界面(GUI)器件如:文本框,按钮,分隔窗格和表. Swing提供许多比AWT更好的屏幕显示元素.它们用纯Java写成,所以同Java本身一样可以跨平台运行,这一点不像AWT.它们是JFC的一部分.它们支持可更换的面板和主题(各种操作系统默认的特有主题),然而不是真的使用原生平台提供的设备,而是仅仅在表面上模仿它们.这意味着你可以在任意平台上使用JAVA支持的任意面板.轻量级组件的缺点则
-
Java解压zip文件完整代码分享
关于Java解压zip文件,我觉得也没啥好多说的,就是干呗..代码如下: package com.lanyuan.assembly.util; import java.io.BufferedOutputStream; import java.io.File; import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStream; import java.util.Enumeration; i
-
Java编程redisson实现分布式锁代码示例
最近由于工作很忙,很长时间没有更新博客了,今天为大家带来一篇有关Redisson实现分布式锁的文章,好了,不多说了,直接进入主题. 1. 可重入锁(Reentrant Lock) Redisson的分布式可重入锁RLock Java对象实现了java.util.concurrent.locks.Lock接口,同时还支持自动过期解锁. public void testReentrantLock(RedissonClient redisson){ RLock lock = redisson.getL
-
Java编程实现逆波兰表达式代码示例
逆波兰表达式 定义:传统的四则运算被称作是中缀表达式,即运算符实在两个运算对象之间的.逆波兰表达式被称作是后缀表达式,表达式实在运算对象的后面. 逆波兰表达式: a+b ---> a,b,+ a+(b-c) ---> a,b,c,-,+ a+(b-c)*d ---> a,b,c,-,d,*,+ a+d*(b-c)--->a,d,b,c,-,*,+ a=1+3 ---> a=1,3 + http=(smtp+http+telnet)/1024 写成什么呢? http=smtp,
-
Java编程Webservice指定超时时间代码详解
WebService是一种跨编程语言和跨操作系统平台的远程调用技术 所谓远程调用,就是一台计算机a上的一个程序可以调用到另外一台计算机b上的一个对象的方法,譬如,银联提供给商场的pos刷卡系统(采用交互提问的方式来加深大家对此技术的理解). 远程调用技术有什么用呢?商场的POS机转账调用的转账方法的代码是在银行服务器上,还是在商场的pos机上呢?什么情况下可能用到远程调用技术呢?例如,amazon,天气预报系统,淘宝网,校内网,百度等把自己的系统服务以webservice服务的形式暴露出来,让第
-
Java编程实现打地鼠文字游戏实例代码
控制台输入数字,与随机数匹配,匹配正确则返回"打中了!" 匹配错误则返回"太遗憾!没打中!" package hitmouse; import java.util.Random; import java.util.Scanner; public class HitMouse { public static void main(String[] args) { // TODO Auto-generated method stub int[] map = new int
-
Java编程实现A*算法完整代码
前言 A*搜寻算法俗称A星算法.这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法.常用于游戏中 通过二维数组构建的一个迷宫,"%"表示墙壁,A为起点,B为终点,"#"代表障碍物,"*"代表算法计算后的路径 本文实例代码结构: % % % % % % % % o o o o o % % o o # o o % % A o # o B % % o o # o o % % o o o o o % % % % % % % % =======