一道笔试题,汗,没有搞定

parol2910(树上的青蛙）
如果第一次不平衡，选哪一组？
并不知道重量特殊的球是轻是重

将12球编号ABCDEFGHIJKL，分组为ABCD,EFGH,IJKL。ABCD和EFGH相称：
1.  若ABCD=EFGH，则IJKL中有异常球，ABC和IJK相称：
     1.1  若AB=IJ，则KL中有一异常。
     1.2  若AB>IJ，则IJ中有偏重球，反之则有偏轻球。
2.  若ABCD>EFGH，AIJK和EBCD相称：
     2.1  若AIJK=EBCD，则FGH中有一偏轻球。
     2.2  若AIJK>EBCD，AE中有一异常球。
     2.3  若AIJK<EBCD，BCD中有一偏重球。
3.  若ABCD<EFGH，同2法，可得结果

Google!上挺多的！soso看。呵呵^^

zhangqingqi82(上下而求索……) 的方法不通啊..

12个球分为 A、B、C 三组，每组四个4A vs 4B
    相等：目标在4C中，AB为标准球
        A + C1  vs  C2 + C3
            相等：C4 为非标
                C4 与任一球比较，可知轻重
            左重：C1重或 C2，C3轻
                C2 vs C3
                相等：C1重
                不等：重的一个为非标，且轻
            右重：C1轻或 C2，C3重
                判断方法类左重
    左重：目标在AB组中，C为标准球
        A1+B2+B3+B4 vs B1+C1+C2+C3
        相等：目标在A2，A3，A4 中，且重
              A2 vs A3
                  相等：A4重
                  不等：重的一个为目标，且重
        左重：A1重或 B1 轻
              A1 与标准C比较可知结果
        右重：目标在 B2，B3，B4 中，且轻
              B2 vs B3
                  相等：B4轻
                  不等：轻的一个为目标，且轻
    右重：目标在AB组中，C为标准球
        与左重判断方法类似

你说我的方法哪出毛病了
回复人： nimifeng(现在只想学点东西) ( ) 信誉：100 2005-04-24 14:12:00 得分: 0

zhangqingqi82(上下而求索……) 的方法不通啊..

写了个程序测试我前面的方法，很简单，一大堆的 ifimport java.util.*; public class Ball{
    public static void main(String[] args)    {
        boolean flag = true; // true 重，false 轻

        // 12 个标准球
        int a[] = new int[] {5,5,5,5,5,5,5,5,5,5,5,5};        // 随机选定一个球并给一个非标准的随机重量
        Random randnum = new Random();
        int index=randnum.nextInt(12);
        while(a[index] == 5) {
            a[index] = randnum.nextInt(10);
        }


        // 8,9,10,11 为标准球
        if(a[0]+a[1]+a[2]+a[3] == a[4]+a[5]+a[6]+a[7]) {
            if(a[0]+a[8] == a[9]+a[10]){ // 11
                index = 11;
                flag = a[11] > a[0] ? true : false;
            }
            else if(a[0]+a[8] > a[9]+a[10]){ // 8重或9,10轻
                if(a[9] == a[10]){
                    index = 8;
                    flag = true;
                }
                else {
                    index = a[9] < a[10] ? 9 : 10;
                    flag = false;
                }
            }
            else { // 8轻或9,10重
                if(a[9] == a[10]){
                    index = 8;
                    flag = false;
                }
                else {  // 8轻或9,10重
                    index = a[9] > a[10] ? 9 : 10;
                    flag = true;
                }
            }
        }
        // 目标在0-7，8-11为标准球
        else if(a[0]+a[1]+a[2]+a[3] > a[4]+a[5]+a[6]+a[7]){
            // 目标在1,2,3中，且重
            if(a[0]+a[5]+a[6]+a[7] == a[4]+a[8]+a[9]+a[10]) {
                flag = true;
                if(a[1] == a[2])
                    index = 3;
                else
                    index = a[1] > a[2] ? 1 : 2;
            }
            // 0重或4轻
            else if(a[0]+a[5]+a[6]+a[7] > a[4]+a[8]+a[9]+a[10]) {
                index = (flag = a[0] > a[11]) ? 0 : 4;
            }
            // 目标在5,6,7中，且轻
            else {
                flag = false;
                if(a[5] == a[6])
                    index = 7;
                else
                    index = a[5] < a[6] ? 5 : 6;
            }
        }
        // 目标在0-7,8-11为标准球
        else{
            // 目标在1,2,3中，且轻
            if(a[0]+a[5]+a[6]+a[7] == a[4]+a[8]+a[9]+a[10]) {
                flag = false;

                if(a[1] == a[2])
                    index = 3;
                else
                    index = a[1] < a[2] ? 1 : 2;
            }
            // 0轻或4重
            else if(a[0]+a[5]+a[6]+a[7] < a[4]+a[8]+a[9]+a[10]) {
                index = (flag = a[0] < a[11]) ? 0 : 4;
            }
            // 目标在5,6,7中，且重
            else {
                flag = true;
                if(a[5] == a[6])
                    index = 7;
                else
                    index = a[5] > a[6] ? 5 : 6;
            }
        }
        ++index; // 0-11 to 1-12

        for(int i = 0; i < 12; ++i) {
            System.out.print(a[i] + " ");
        }
        System.out.println();

        System.out.println("target is " + index + (flag ? ", weitht" : ", light"));
    }
}

细看了zhangqingqi82(上下而求索……) 的方法
是可以得到结果的，我的方法与之类似并将后面的称法细化了，只是在 ABCD=EFGH 时的称法略有不同，但结果是一样的

前面的程序多测试了几篇，0轻或4重的地方写得不对
应该是这样的// 0轻或4重
else if(a[0]+a[5]+a[6]+a[7] < a[4]+a[8]+a[9]+a[10]) {
index = (flag = a[4] > a[11]) ? 4 : 0;
}

xybstone(小胖) ，
按照你的方法，如果1，2称平，然后1，3称又平，然后怎么办呢？
只剩一次了，只知道异常球在4组里面！

if(3==3){//任意找6个球
  if(2==2){//把剩下的5个球,任意找4个
System.out.println("还有一个球,他最重");
} else{//2!=2时,称一下就知道那个重啦}
}
if(3!=3){//称重的一边,任意找2个称
  if(1=1){
    System.out.println("剩下的一个");
} else{System.out.println("重的那个就是啦");}
}
//就这么简单,看思维能力的一个题,呵呵,脑子清晰的时候一下就知道怎么判断了!!

看成11个球了,sorry!!不过方法同样可行,呵呵

将12球编号ABCDEFGHIJKL，分组为ABCD,EFGH,IJKL。ABCD和EFGH相称：
1. 若ABCD=EFGH，则IJKL中有异常球，ABC和IJK相称：
1.1 若AB=IJ，则KL中有一异常。
1.2 若AB>IJ，则IJ中有偏重球，反之则有偏轻球。
2. 若ABCD>EFGH，AIJK和EBCD相称：
2.1 若AIJK=EBCD，则FGH中有一偏轻球。
2.2 若AIJK>EBCD，AE中有一异常球。
2.3 若AIJK<EBCD，BCD中有一偏重球。
3. 若ABCD<EFGH，同2法，可得结果

根据zhangqingqi82(上下而求索……) 的方法可以找出这个不同的球，并且知道它与其他11个球的关系（重或轻）。

同意这个观点：
回复人： fdabobi(小爪尖尖) ( ) 信誉：100  2005-04-25 12:29:00  得分: 0

   想通了！！好象刚刚超过了30分钟，哎，想通后其实很简单的！！！
4/4/4分3种，假设分为红/黄/蓝3组第一步：取2种颜色称
最坏的情况就是不平衡，假设左黄重/右蓝轻
说明要么黄的有一个比较重，要么蓝的有一个比较轻第二步：取走3蓝，并且从左边拿3个黄到右边，左边补上3个红的
  左重右轻：问题在左边一黄或者右边一蓝中
  左轻右重：问题在右边3黄中，且问题球为重
  平衡：问题在拿掉的那3个蓝的中，且问题球为轻第三步，已经没有难度
  3个球并且知道问题球为轻为重，自然很容易判断
  2个球，不知道轻重，拿红色标准球测试一下就OK了

我也是在小学里做过,不过那时是 8个球,2次测出来,分组为2,3,3
同理11个球,就是 2,3,3,3就可以了.
其实11个球不是很好,24个球都只需要3次
分为 8,8,8即可,因为8只需2次,所以24只需3次.
a1 = 3
a2 = 8
a3 = 8*3 = 24
a4 = 24*3 =72
an = 3an-1 (n>=3)...上面是不是最简,还没有经过严密的数学论证,但可以肯定的是 ,当球的个数 M<=an时,所需要的总次数不超过n.
有兴趣的可以试作进行论证,

晕,竟然犯了一个初级错误
8=3*3!
应该是
a1=3
a2 = 9=3*3
a3 = 27 = 9*3
an = 3an-1
个人觉得这是一个3进制问题. 因为,对于2进制是只需要加法就能表示所有的正整数
如果允许加减法,3进制可以表示所有问题

取八个,一边放四个case: 左=右
    把另外四个分成两组放上来,左边的编号1.2,右边的 3,4;
    if (左<右)
    {
        把2和3交换
        if(左<右)
            1号右问题;
        else
            2号有问题;
    }
    else
    {
        把2和3交换
        if(左>右)
            4号右问题;
        else
            3号有问题;
    }
    break;
case:左<右
    编号左:1,2,3,4,右,5, 6, 7, 8;
    将1,2与5,6交换;
    if(左<右)
    {
左边放3,右边放4;
if(左<右)
    3号右问题;
else
    4号有问题;
    }
    else
    {
左边放1,右边放2;
        if(左<右)
        {
    左边放3,右边放4;
    if(左<右)
        4号右问题;
    else
        3号有问题;
        }    }
case:左>右
     和左<右同样的道理!

给小球编号1~12，以下用括号表示天平两边分组。平分成三份，先取两份来称(1 2 3 4)(5 6 7 8) （第一次）。1、假如第一次相同，说明目标球在(9 10 11 12)中，再称(1 9)(10 11) （第二次）a、假如一样重，说明12号球与众不同，将它与任一球称即可知道是重是轻 (第三次）b、假如左重右轻，说明不是9号重就是10或11号轻，只要称(10)(11)即可知道。（第三次）c、假如左轻右重，则与上面同理可推。2、假如第一次左重右轻，说明要么1234中有一球重要么5678中有一球轻，这时称(1 5 6)(2 7 8) （第二次）a、假如一样重，说明3号和4号中必有一球重，称它俩就可知道。（第三次）b、假如左重右轻，说明要么1号重，要么78中有一球轻，则称(7)(8)即可。（第三次）c、假如左轻右重，说明要么2号重，要么56中有一球轻，称(5)(6)即可。（第三次）

xybstone(小胖) 说的精简、通俗易懂。

哎还是没有人来验证我的,我自己来P:当n=1时
显然3个球是,我只需要,取左1,右1 ,如果有一个球勤的话,那么问题解决,如果没有,那么剩下的就是.当n = k时,设支持最多的球数为Ak(k表示次数）当n=k+1时,可以支持最多球数为Ak+1 = 3*Ak;
证明如下: 因为如果平分成3份,那么取其中2份,天平称,
(1) 如果有轻重, 那么其中必有一份有氢球,而这一份中共有球数Ak个(由假设得到需要k次才能分出氢球) 所以此时为k+1次就可以分出
(2)如果没有，那么剩下的为Ak个球，同样需要k次，所以总共也是k+1次综述得，Ak+1 = 3*Ak
又因为A1 = 3
所以An = 3的n次方 == 3^n终于搞定，哈哈哈哈哈，如释重负！！原题的11个球因为 3^2 =9 < 11 < 3^3=27所以至少需要3次。怎么分？不惟一，因为，不恰好是 3^n
感觉出这个题的人也没有太高的水平嘛哈哈哈

楼上的 bigc2000(公元2005年4月9日)
你自言自语半天
结果连题目都没看清楚显然3个球是,我只需要,取左1,右1 ,如果有一个球勤的话,那么问题解决,如果没有,那么剩下的就是.只知道有异常球，谁告诉你有一个球轻

12个球分为 A1234 B1234 C1234

1次...先称 A1234 和 B1234如果一样的话2次...A1 C1 和 A2 C2如果一样3次...A1 和 C3
如果一样就说明C4是不一样的球

我觉得就是把那么有异常的球挑出来是不是? 先取8个球分别发到天平的两边（每一边4个）if （两边平和）那么就是剩下的4个球有问题，随机选取2个 if（两边平衡）把剩下那两个在放到天平上，这样就能找到有异常的球了反之如果第一次选的8个球天平的两边不等，原理是一样的。

to wondfulsun
你这垃圾这么到处发这种垃圾贴？？
想钱想疯啦
BS

回复人： zhangqingqi82(上下而求索……) ( ) 信誉：100 2005-04-26 15:55:00 得分: 0
说的是,教训的是,谢谢!

回复人： prince7171(渴望卓越) ( ) 信誉：100  2005-04-26 00:32:00  得分: 0

   我认为千年一狼说的不对!!!
因为:
b、假如左重右轻，说明不是9号重就是10或11号轻，只要称(10)(11)即可知道。（第三次）
无法判断


你说我说的那里不对的,我来给我分析一下:
1.假如是(10)=(11)根据前面(1)是正确的.可知(9)就是要找的球;
2.假如(10)>(11)可知我们所找的球就在这2个之中,再根据已知的前提是左重右轻(1和9)是正确.可知所要求的球是比其它的球的轻的,这就得出是(11)
3.假如(10)<(11)可知我们所找的球就在这2个之中,再根据已知的前提是左重右轻(1和9)是正确.可知所要求的球是比其它的球的轻的,这就得出是(10)
你还有那里不明白的???????

既然是微软出的题,就不要老老实实按常规想了,兄弟姐妹们!
我也是想破头了,可是大家想到过google,baidu没有???搜搜啊.这个网站里有个答案:
http://www.myjob.com.cn/News/NewsContent.aspx?id=2948　　答案1：12个球，两边各放六个，必然有一边重一边轻（第一次称）。把较重的一边平均分到两个称盘进行称量，会有两种结果：质量相同，说明要找的球在另六个中，且较轻；如果质量不同，说明哪个球在现在所称量的这六个中，且较重（第二次称）如果质量相同，将另外六个球左一个右一个依次放入，就可以找到比较轻的那个球。如果质量不同，将任意两个球放入，就可以找到比较重的那个球。　　答案2：将12个球按左右依次放入，必然有两个球放进去的时候，天平不再平衡。用第三个球，就可以找出哪个不同质量的球。(请注意答案2的思维,其实答案1中最后也用的是)OK! 请结帖吧
^_^

ahchoow(ahchoow) ( )
将另外六个球左一个右一个依次放入，那能算一次么？如果这样算一次，那一开始就把十二个球一个一个依次放入也好啊。那两次就侧出来了。先测出在天平不平时的两个球，那么特殊的小球就在其中，在用其它的小球和其中的一个比较，就知道那个特殊而且是轻还是重了。所以你的算法好像不对吧。

老题目了,google上都可以搜得到

给小球编号1~12，以下用括号表示天平两边分组。平分成三份，先取两份来称(1 2 3 4)(5 6 7 8) （第一次）。1、假如第一次相同，说明目标球在(9 10 11 12)中，再称(1 9)(10 11) （第二次）a、假如一样重，说明12号球与众不同，将它与任一球称即可知道是重是轻 (第三次）b、假如左重右轻，说明不是9号重就是10或11号轻，只要称(10)(11)即可知道。（第三次）c、假如左轻右重，则与上面同理可推。2、假如第一次左重右轻，说明要么1234中有一球重要么5678中有一球轻，这时称(1 5 6)(2 7 8) （第二次）a、假如一样重，说明3号和4号中必有一球重，称它俩就可知道。（第三次）b、假如左重右轻，说明要么1号重，要么78中有一球轻，则称(7)(8)即可。（第三次）c、假如左轻右重，说明要么2号重，要么56中有一球轻，称(5)(6)即可。（第三次）正解........................................................

genggeng1206(庚庚) 说得完全正确,经典的题.我没做出来,汗.真是需要跳跃性思维才做得出来的.我就是走到死胡同去了

Salten(笑天)
我是从网上找的答案，这个题考得不是算法的问题，微软的考题是考思维和逻辑的，我们不能编程编得思维僵化了。

调试易

一道笔试题,汗,没有搞定

解决方案 »