一个算法问题，重要的不是语言而是逻辑：有X个球，一个天秤，有一个球重量不一样，请问几次可以确切称出哪个是不一样重的球。

Question

这里有一个天秤，然后有X个颜色、外观、大小一样的球，但是有一个重量跟其它几个不一样，那么我用天秤怎样才能称出那一个不一样重的球呢？（X不一定能被2整出哦，而且X除以2后的数也不一定能继续被2整出，最巧的情况是X不能被2整除，取出一个然后将剩余的平分成两份用天秤一称，平衡，那么取出的这个球就是重量不一样的了，但是这只是一种情况，我要所有可能的情况，求大神），请回复：代码,code,代码,code,代码,code,代码,code,代码,code,代码,code,代码,code,代码,code,代码,code,代码,code,代码,code,代码,code,代码,code  思路就不要发了，呵呵。

Answer 1

A=B=X/2 
A/2==A/2 肯定在B里面 B 重复X的操作
A/2!=A/2 肯定在A里面 A重复X的操作直到剩下两个球 然后在拿一个球出来 
剩下 A B 
在拿 C
A==C  B重量不一样 
A!=C A重量不一样

Answer 2

分成 M ,M ,M ,m
where m<M ;m>=0第一个M分别和第二个M、第三个M比较，这样能确定M是在某个M中或m中
一直这样分下去

Answer 3

package aaa.bbb;import java.io.IOException;
import java.util.*;public class TTT { /**
 * t
 * 
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub List<Ball> balls = new LinkedList<Ball>();
Ball b = new Ball();
b.Weight = 100;
balls.add(b);
b = new Ball();
b.Weight = 100;
balls.add(b);
b = new Ball();
b.Weight = 100;
balls.add(b);
b = new Ball();
b.Weight = 100;
balls.add(b);
b = new Ball();
b.Weight = 100;
balls.add(b);
b = new Ball();
b.Weight = 100;
balls.add(b);
b = new Ball();
b.Weight = 50;
balls.add(b);
b = new Ball();
b.Weight = 100;
balls.add(b);
b = new Ball();
b.Weight = 100;
balls.add(b);
b = new Ball();
b.Weight = 100;
balls.add(b);
b = new Ball();
b.Weight = 100;
balls.add(b); List<Ball> tempBalls = balls; int size = balls.size(); int countOfEachSplit = size / 3;
while (countOfEachSplit != 0) {
int left = size % 3;
List<Ball> ms = null;
List<Ball> as = null;
List<Ball> bs = null;
List<Ball> cs = null;
Ball scallBall = null;
if (countOfEachSplit > 0) {
as = tempBalls.subList(0, countOfEachSplit);
bs = tempBalls.subList(countOfEachSplit, countOfEachSplit * 2);
cs = tempBalls.subList(countOfEachSplit * 2,
countOfEachSplit * 3);
}
if (left > 0) {
ms = tempBalls.subList(countOfEachSplit * 3, tempBalls.size());
} int aw = getTotalWeight(as);
int bw = getTotalWeight(bs);
int cw = getTotalWeight(cs);
if (aw == bw && aw == cw) {
scallBall = as.get(0);
tempBalls = ms; } else {
if (aw == bw) {
scallBall = as.get(0);
tempBalls = cs;
} else if (aw == cw) {
scallBall = as.get(0);
tempBalls = bs;
} else {
scallBall = bs.get(0);
tempBalls = as;
} } if (tempBalls.size() < 3) {
for (Ball bb : tempBalls) {
if (scallBall.Weight != bb.Weight) {
System.out.println(balls.indexOf(bb));
}
}
}
countOfEachSplit = tempBalls.size() / 3;
left = tempBalls.size() % 3; } try {
System.in.read();
} catch (IOException e) {
e.printStackTrace();
} } private static int getTotalWeight(List<Ball> bs) {
int w = 0;
for (Ball b : bs) {
w += b.Weight;
}
return w;
}}////
package aaa.bbb;public class Ball { public int Weight;
}

Answer 4

应该是这样子的，无论是分成几份，都是基于两份的，举个例子：61，那么分成六份：10,10,10,10,10,1就比分成四份：15,15,15,1强，因为10比15比较的少，以此类推，如果101那么分成11份就比分成6份强，但是很多第二次就分不到值了就是X,X，S，0,0,0.....最后都是依据两份产生的。