首页 > 代码库 > 八枚硬币
八枚硬币
理论：
现有八枚银币a b c d e f g h，已知其中一枚是假币，其重量不同於真币，但不知是较轻或较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较重
解法
单就求假币的问题是不难，但问题限制使用最少的比较次数，所以我们不能以单纯的迴圈比较来求解，我们可以使用决策树（decision tree），使用分析与树状图来协助求解。
一个简单的状况是这样的，我们比较a+b+c与d+e+f ，如果相等，则假币必是g或h，我们先比较g或h哪个较重，如果g较重，再与a比较（a是真币），如果g等於a，则g為真币，则h為假币，由於h比g轻而 g是真币，则h假币的重量比真币轻。
完整的比较决策树如下图所示：
java实现：
package 经典;import java.util.Random;public class Coins { public int[] coins=new int[8]; public Coins(){ for(int each:coins) each=10; } public void setFake(int weight) { coins[new Random().nextInt(8)] = weight; } public int findFake(){ if((coins[0]+coins[1]+coins[2])==(coins[3]+coins[4]+coins[5])) { if(coins[6]==coins[0]) return 7; else return 6; } else if((coins[0]+coins[3])==(coins[1]+coins[4])) { if(coins[2]==coins[0]) return 5; else return 2; } else if((coins[0]+coins[3])==(coins[2]+coins[5])) { if(coins[1]==coins[0]) return 4; else return 1; } else { if(coins[0]==coins[1]) return 3; else return 0; } } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Coins coins=new Coins(); coins.setFake(9); System.out.println((coins.findFake()+1));; }}
八枚硬币
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。