[数据结构与算法]算法-称硬币(枚举-java)

POJ1013原题：称硬币

提示：C语言版老师讲解视频
该文为java解法

前言

来自编者的话：或许这段日子会很苦，想停下去，但是咬牙坚持下去，一定会有所收获。

一、题目描述

有12枚硬币。其中有11枚真币和1枚假币。假币和真币重量不同， 但不知道假币比真币轻还是重。现在用一架天平称了这些币三次，告诉你称的结果，请你找出假币并且确定假币是轻是重（数据保证一能找出来）。

输入
第一行是测试数据组数。
每组数据有三行，每行表示一次称量的结果。银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币，天平右边放置的硬币平衡状态。其中平衡状态用"up",“down”,或"even"表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。

输出
输出哪一个标号的银币是假币，并说明它比真币轻还是重。

输入样例
1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even

输出样例
K is the counterfeit coin and it is light.

二、解题思路

1.简化并理解题意

这一点十分重要，要学会简化题意。
十二枚硬币(A-L)中有一枚假币，不知道轻还是重，现在告诉你三次测量的结果，找出假币并确定轻重。题上给了一组测量结果，并且平衡状态都是根据天平右边做出判断，所以要以右边为主对象，并且结果要用字符串表示，最终结果是输入题上案例，并获得正确答案，所有不要忘记写输入这一块的代码。

2.思考方向

借助数组来存输入的字符和显示的结果；使用枚举法，全部12枚硬币都试，对每一枚硬币先假设是假且轻，然后带入三次称量结果中，不符合的话，就假设硬币是假币且重，看看是否符合称量结果。

import java.util.Scanner;
//称硬币
public class class1 {
	static String content[][] = new String [3][3]; //创建一个用来存储输入字符的二位数组 行表示字符 列表示 结果 
	public static void main(String[]args) {
		Scanner s = new Scanner(System.in);
		int group = s.nextInt(); //group表示所测量的组数 例输入1  则表示代表第一组测量  需要输入三串字符 三个结果
		while(group-->0) {
			for(int i = 0;i<3;i++) 
				for(int j = 0;j<3;j++) 
					content[i][j]=s.next(); // 从键盘读取所输入的字符 行表示字母例ABCD 列表示结果例even
			//从A开始到L，开始假设目标硬币硬币是假
			for(char c ='A';c<='L';c++) { //大写字母编码是从65-90，即可以通过+1，来实现字母的变化
				String a = String.valueOf(c); //将字符型改成字符串类型
				if(isfake(content, a, true)) {
					System.out.println(a+" is the counterfeit coin and it is light");
					break;
				}else if(isfake(content, a, false)) {
					System.out.println(a+" is the counterfeit coin and it is heavy");
					break;
				}
			}
		}
	}
	//下面是主要判断方法 对于目标硬币 假设该硬币为假且轻
	static boolean isfake(String[][]content1,String c,boolean light) {
		//把假设带入三次称量结果 看是否矛盾
		for(int i =0 ;i<3;i++) {
			String l = null;
			String r = null;
			if(light==true) {
				l = content1[i][0];
				r = content1[i][1];
			}else {
				l = content1[i][1];
				r = content1[i][0];
			}
			switch (content1[i][2]) {
			case "up":
				if(r.contains(c)==false)
					return false;
				break;
			case "even":
				if(r.contains(c)==true || l.contains(c) == true)
					return false;
				break;
			case "down":
				if(l.contains(c)==false)
					return false;
				break;
			}
		}
		return true; //首先给light返回一个true值
	}
}
帮助理解：就拿当假币为A时举例，首先 进入isfake方法中，默认为true，将l=ABCD r=EFGH，结果为even，进入switch循环中，判断存在，return false终止函数，重新返回到主函数中，由于light没有返回值，矛盾，所以默认进行下一个字符。
当轮到假币K时，进入isfake中返回值为true，所以最终确定假币，假设成功，为轻。
 

目的

学会从题意着手，熟练使用枚举。

参考文章：C语言版解法