昨天又从某处看到了12球称重的问题，虽然之前有过解题的过程，但这次仍然费了不少时间才又找到解题方法。然后我又思考，从我看到问题，到得到解决方法，这是怎样的一个过程，怎样的思维想到了怎样一个方法，从而得到了怎样的一个结果。假如我能够把这个过程描述下来，那可谓对自己的思维过程有了一个很好的梳理，并且可以记录入自己的SOP；同时，也就更加真实地了解自己。而更为重要的是，可以将这种思维的过程，传播出去；从而不仅仅是知识得到延续，而更为重要的思维过程，也可以得到延续。
题目：12个球，外观（大小、色泽等）完全一致，其中，有十一个球的重量是一样的，另一个球的重量与其他球是不一致的。怎样用天平最多仅称重三次，找出那个重量不一致的球，并且还能确认这个球是较重还是较轻。
这个题的重点是不知道那个不一致的球是重了还是轻了。那假如是这个球是重的呢？
很多人的思路是，平分成两组，每组6个，进行称重。然后将重的一组再分组，每组3个，进行称重。最后，将重的一组（3个球）其中两个称重，若有一个重，则这个球是要找的球；若相等，则没有称重的这个球是要找的球。
但是这个过程是无法直接应用到要解决的问题上的。所以，只能换一个方向——简化。
两个球的情况：无法得知哪个球是要找的球。
三个球的情况：标记ABC，取AB进行称重，会有两种情况：
1，它们相等，那么C就是要找的球，称A和C
1.1 C>A，C较重。
1.2 C<A，C较轻
1.3 C=A，A=B=C，与前提矛盾，因此不可能出现。
2，它们不等，我们假设A>B，那么C是一颗正常的球。将A与C称重，
2.1相等，B球较轻，为要找的球。
2.2A>C，A球较重，为要找的球。
2.3A<C，那么C>A>B，与前提矛盾，因此不可能出现。
然后再回过头来，看上面的过程。你会发现什么，先想一想吧……
这其实是一个信息获取的过程，根据已知信息，通过操作，得到未知信息。如果我们一直测AB的话，即使测100遍也无法找到重量较轻或者较重的那个球。
可以通过一种标记来记录信息，这里球有正常，较轻和较重三种情况，可以用(+1,0,-1)来表示。当通过一次次的测量，为各个球标上(+1,0,-1)三种状态，并最终有且仅有一个球的状态为+1或者-1，就可以确定，这个状态为+1或者-1的球为要找的较重或者较轻的球。为上述操作过程分别标记信息含量值
1，它们相等，那么C就是要找的球[A0,B0,C]
称A和C
1.1 A<C，C重[A0,B0,C+]
1.2 A>C，C轻[A0,B0,C-]
1.3 C=A，A=B=C，与前提矛盾，因此不可能出现。
2，它们不等，我们假设A>B，那么C是一颗正常的球。[A+,B-,C0]
将A和C
2.1 A=C，B轻[A0,B-,C0]
2.2 A>C，A重。可由A>C和前提得知B=C，因此[A+,B0,C0]
2.3 A<C，那么C>A>B，与前提矛盾，因此不可能出现。
那么，总结一下整个过程，就是将球分为较重、较轻（标记+-），并通过和标准球（标记0）的比较，来得知是否为重球（不是重球，则与之相比较的球是轻球）或者轻球。
再来分析一下标记的信息值，0表示为标准球，含有确切含义，而+和-在不唯一的情况下，只能表示可能较重，但其实并不重，按其信息值排序的话：0>(+或-)>没有标记，我们的目的是在每次称重的过程中，使获得的信息值最大化。
12球的过程
6:6称重，只能将6个球标记为+，另6个球标记为-，无法得到0的标记
而4:4称重，至少可以将4个球标记为0（其实，有两种可能，一是8个0，另一种是4个+，4个-，4个0）
（未完待续）
4:4称重
1. 两边相平
1~8标记为0
将9,10放左边，11和1放右边，称重
1.1 左边重
9,10:+
11:-
12:0
对9,10进行称重，便可得到结果
1.1.1 9=10，则9,10:0,11为较轻的球
1.1.2 9>10，则9为较重的球
1.1.3 9<10，则10为较重的球
1.2 右边重
9,10:-
11:+
12:0
同1.1剩余部分
1.3 同样重
则9,10,11标记为0，取1和12称重，因为1是标准球，根据天平状态，可以得出12球是轻还是重
2. 左边重
1~4:+
5~8:-
9~12:0
选择1,2,5,6和3,7,9,10称重
2.1 1,2,5,6=3,7,9,10
1,2,3,5,6,7:0
4:+
8:-
随便用4或者8跟其他球称一些就可得到结果
2.2 1,2,5,6>3,7,9,10
1,2:+
7:-
3,4,5,6,8:0
1和2再称一次就可得到结果
2.3 1,2,5,6<3,7,9,10
5,6:-
3:+
1,2,4,7,8:0
5和6再称一次就可得到结果
3. 右边重，同2
这个游戏如果用程序来实现的话，有两种实现方法：
一种是不考虑过程的，让玩家选出的球和初始化时随机选中的球比较，这个实现非常简单，但是会存在运气的成分，让玩家有几率蒙对。
另一种是考虑过程的，根据玩家的选球称重状态来判断最后的结果，这样避免了运气成分。
平衡情况：
游戏开始：
游戏示例，第二个球比较重请输入：Y;2;1
游戏示例，第十个球比较轻请输入：Y;10;-1
游戏示例，左右两边分别称1,2,3,4和5,6,7,8请输入：N;1,2,3,4;5,6,7,8
N;1,2,3,4;5,6,7,8
左边轻，右边重
1:-1; 2:-1; 3:-1; 4:-1; 5:1; 6:1; 7:1; 8:1; 9:0; 10:0; 11:0; 12:0;
N;1,2,5,6;3,7,9,10
左边重，右边轻
1:0; 2:0; 3:-1; 4:0; 5:1; 6:1; 7:0; 8:0; 9:0; 10:0; 11:0; 12:0;
N;5;6
左边重，右边轻
1:0; 2:0; 3:0; 4:0; 5:1; 6:0; 7:0; 8:0; 9:0; 10:0; 11:0; 12:0;
Y;5;1
你真厉害，你答对了！
1:0; 2:0; 3:0; 4:0; 5:1; 6:0; 7:0; 8:0; 9:0; 10:0; 11:0; 12:0;
不平衡情况：
游戏开始：
游戏示例，第二个球比较重请输入：Y;2;1
游戏示例，第十个球比较轻请输入：Y;10;-1
游戏示例，左右两边分别称1,2,3,4和5,6,7,8请输入：N;1,2,3,4;5,6,7,8
N;1,2,3,4;5,6,7,8
两边平衡
1:0; 2:0; 3:0; 4:0; 5:10; 6:10; 7:10; 8:10; 9:10; 10:10; 11:10; 12:10;
N;9,10;11,1
左边轻，右边重
1:0; 2:0; 3:0; 4:0; 5:0; 6:0; 7:0; 8:0; 9:-1; 10:-1; 11:1; 12:0;
N;9;10
左边重，右边轻
1:0; 2:0; 3:0; 4:0; 5:0; 6:0; 7:0; 8:0; 9:0; 10:-1; 11:0; 12:0;
Y;10;-1
你真厉害，你答对了！
1:0; 2:0; 3:0; 4:0; 5:0; 6:0; 7:0; 8:0; 9:0; 10:-1; 11:0; 12:0;
运气情况：
游戏开始：
游戏示例，第二个球比较重请输入：Y;2;1
游戏示例，第十个球比较轻请输入：Y;10;-1
游戏示例，左右两边分别称1,2,3,4和5,6,7,8请输入：N;1,2,3,4;5,6,7,8
Y;1;1
哈哈，你开始猜了。
你运气太好了,竟然猜对了！
1:10; 2:10; 3:10; 4:10; 5:10; 6:10; 7:10; 8:10; 9:10; 10:10; 11:10; 12:10;
简单实现代码如下：
package com.liubuhu.twevel;
import java.util.Scanner;
public class TwevelBalls {
private static final int LIGHT = -1;
private static final int NORMAL = 0;
private static final int HEAVY = 1;
private Integer[] balls = null;
public Integer[] getBalls() {
if (balls == null) {
balls = new Integer[12];
for (int i = 0; i < balls.length; i++) {
balls[i] = 10;
}
}
return balls;
}
public TwevelBalls() {
}
private class InputBean {
private Boolean bfind;
private Integer ball;
private Integer heavy;
private Integer[] left;
private Integer[] right;
public Boolean getBfind() {
return bfind;
}
public void setBfind(Boolean bfind) {
this.bfind = bfind;
}
public Integer getBall() {
return ball;
}
public void setBall(Integer ball) {
this.ball = ball;
}
public Integer[] getLeft() {
return left;
}
public void setLeft(Integer[] left) {
this.left = left;
}
public Integer[] getRight() {
return right;
}
public void setRight(Integer[] right) {
this.right = right;
}
public void setHeavy(Integer heavy) {
this.heavy = heavy;
}
public Integer getHeavy() {
return heavy;
}
}
/**
* @param args
*/
public static void main(String[] args) {
TwevelBalls t = new TwevelBalls();
t.run();
}
private void run() {
Integer theBall = (int) Math.floor(Math.random() * 12);
// 1 for heavy, -1 for light
Integer heavy;
if (Math.random() > 0.5) {
heavy = HEAVY;
} else {
heavy = LIGHT;
}
Integer[] myBalls = getBalls();
System.out.println("游戏开始：");
System.out.println("游戏示例，第二个球比较重请输入：Y;2;1");
System.out.println("游戏示例，第十个球比较轻请输入：Y;10;-1");
System.out.println("游戏示例，左右两边分别称1,2,3,4和5,6,7,8请输入：N;1,2,3,4;5,6,7,8");
InputBean bean = null;
Scanner scan = new Scanner(System.in);
// 1
bean = getInput(scan);
myBalls = processData(myBalls, bean, theBall, heavy);
// 2
bean = getInput(scan);
myBalls = processData(myBalls, bean, theBall, heavy);
// 3
bean = getInput(scan);
myBalls = processData(myBalls, bean, theBall, heavy);
// 4 结果
bean = getInput(scan);
myBalls = processData(myBalls, bean, theBall, heavy);
// 结束
scan.close();
// System.out.println("游戏结束，开始颁奖");
}
private Integer[] processData(Integer[] myBalls, InputBean bean,
Integer theBall, Integer heavy) {
if (bean.getBfind()) {
if (check(myBalls)) {
if (theBall.equals(bean.getBall())
&& heavy.equals(bean.getHeavy())) {
System.out.println("你真厉害，你答对了！");
} else {
System.out.println("差了一点点，你是不是敲错键盘了");
}
} else {
if (theBall.equals(bean.getBall())
&& heavy.equals(bean.getHeavy())) {
System.out.println("你运气太好了,竟然猜对了！");
} else {
System.out.println("Sorry,你猜错了！");
}
}
} else {
myBalls = processBalls(myBalls, bean, theBall, heavy);
}
outputBalls(myBalls);
return myBalls;
}
private void outputBalls(Integer[] myBalls) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < myBalls.length; i++) {
sb.append(Integer.valueOf(i + 1).toString()).append(":").append(
Integer.valueOf(myBalls[i]).toString()).append("; ");
}
System.out.println(sb.toString());
}
private Integer[] processBalls(Integer[] myBalls, InputBean bean,
Integer theBall, Integer heavy) {
// 左边有特殊球
if (inTheArray(bean.getLeft(), theBall)) {
if (heavy.equals(Integer.valueOf(0))) {
// 左边重，右边轻
myBalls = labelBalls(myBalls, bean, HEAVY);
System.out.println("左边重，右边轻");
} else {
// 左边轻，右边重
myBalls = labelBalls(myBalls, bean, LIGHT);
System.out.println("左边轻，右边重");
}
// 右边有特殊球
} else if (inTheArray(bean.getRight(), theBall)) {
if (heavy.equals(Integer.valueOf(0))) {
// 左边轻，右边重
myBalls = labelBalls(myBalls, bean, LIGHT);
System.out.println("左边轻，右边重");
} else {
myBalls = labelBalls(myBalls, bean, HEAVY);
// 左边重，右边轻
System.out.println("左边重，右边轻");
}
}
// 没有特殊球
else {
myBalls = labelBalls(myBalls, bean, 0);
System.out.println("两边平衡");
}
return myBalls;
}
private Integer[] labelBalls(Integer[] myBalls, InputBean bean, int l) {
boolean[] labeled = new boolean[myBalls.length];
for (int i = 0; i < myBalls.length; i++) {
labeled[i] = false;
}
switch (l) {
case NORMAL:
for (int i = 0; i < bean.getLeft().length; i++) {
myBalls[bean.getLeft()[i]] = NORMAL;
}
for (int i = 0; i < bean.getRight().length; i++) {
myBalls[bean.getLeft()[i]] = NORMAL;
}
break;
case HEAVY:// 左边重，右边轻
for (int i = 0; i < bean.getLeft().length; i++) {
if (myBalls[bean.getLeft()[i]] == LIGHT
|| myBalls[bean.getLeft()[i]] == NORMAL) {
myBalls[bean.getLeft()[i]] = 0;
} else {
myBalls[bean.getLeft()[i]] = HEAVY;
}
labeled[bean.getLeft()[i]] = true;
}
for (int i = 0; i < bean.getRight().length; i++) {
if (myBalls[bean.getRight()[i]] == HEAVY
|| myBalls[bean.getRight()[i]] == NORMAL) {
myBalls[bean.getRight()[i]] = NORMAL;
} else {
myBalls[bean.getRight()[i]] = LIGHT;
}
labeled[bean.getRight()[i]] = true;
}
for (int i = 0; i < myBalls.length; i++) {
if (labeled[i]) {
} else {
myBalls[i] = 0;
}
}
break;
case LIGHT:// 左边轻，右边重
for (int i = 0; i < bean.getLeft().length; i++) {
if (myBalls[bean.getLeft()[i]] == HEAVY
|| myBalls[bean.getLeft()[i]] == NORMAL) {
myBalls[bean.getLeft()[i]] = NORMAL;
} else {
myBalls[bean.getLeft()[i]] = LIGHT;
}
labeled[bean.getLeft()[i]] = true;
}
for (int i = 0; i < bean.getRight().length; i++) {
if (myBalls[bean.getRight()[i]] == LIGHT
|| myBalls[bean.getRight()[i]] == NORMAL) {
myBalls[bean.getRight()[i]] = NORMAL;
} else {
myBalls[bean.getRight()[i]] = HEAVY;
}
labeled[bean.getRight()[i]] = true;
}
for (int i = 0; i < myBalls.length; i++) {
if (labeled[i]) {
} else {
myBalls[i] = NORMAL;
}
}
break;
}
return myBalls;
}
private boolean inTheArray(Integer[] array, Integer theBall) {
for (int i = 0; i < array.length; i++) {
if (theBall.equals(array[i])) {
return true;
}
}
return false;
}
private boolean check(Integer[] myBalls) {
boolean retVal = true;
int count = 0;
for (int i = 0; i < myBalls.length; i++) {
if (!Integer.valueOf(0).equals(myBalls[i])) {
count++;
}
}
if (count > 1) {
retVal = false;
System.out.println("哈哈，你开始猜了。");
}
return retVal;
}
private InputBean getInput(Scanner scan) {
InputBean bean = new InputBean();
String input = scan.nextLine();
String[] splitedStr = input.split(";");
if ("Y".equals(splitedStr[0])) {
bean.setBfind(Boolean.TRUE);
} else {
bean.setBfind(Boolean.FALSE);
}
if (bean.getBfind()) {
// 进行-1处理，使符合数组
bean.setBall(Integer.valueOf(splitedStr[1]) - 1);
bean.setHeavy(Integer.valueOf(splitedStr[2]));
} else {
bean.setLeft(gnrtBallNumbs(splitedStr[1]));
bean.setRight(gnrtBallNumbs(splitedStr[2]));
}
return bean;
}
/**
* @param str
* @return
* @author liuhao
* @description : 进行-1处理，使符合数组
*/
private Integer[] gnrtBallNumbs(String str) {
String[] splitedStr = str.split(",");
Integer[] ballNumbs = new Integer[splitedStr.length];
for (int i = 0; i < splitedStr.length; i++) {
ballNumbs[i] = Integer.valueOf(splitedStr[i]) - 1;
}
return ballNumbs;
}
}