12个球算法又起风波，一千元大赌判对错！！！各位仲裁……

Question

前俩天朋友： mmff 发贴：12个球怎样找出其中的一个是不同重量的？只给一个天平，不
给砝码！请高手帮忙！针对此大家发表了好多争论，我与同事一千元大赌看下面算法对错
问题，请各位高手仲裁：
球放在左右盘右严格的限定
12个球分成三份，球编号为：1——4为一组；5——8一组；9——11一组
第一步：
     左盘1——4，右盘5——8
     if(平衡)
     {//说明9——12中有假球
          这种情况大家都知道如何判断，无疑！     }
     else if( (1,2,3,4) < (5,6,7,8) )//即右盘重
     {
        //说明9——12号球为真球
        操作：左盘方1，9，10，11，右盘放2，3，4，5
        第二步：
        if(平衡)
        {
            //说明6，7，8中有假球 ，并且由第一步得出假球为重球，否
            //则(（1,2,3,4）< (5,6,7,8))不成立
            第三步：
            操作：
            左6，右7
   if(平衡)
       8假；
   else
       重为假；        
        }
        else
        {
    if(天平无变化)//即右盘重
    {//说明6,7,8,9,10,11,12为真，1——5有假，
               //由第一步反推假球在1，5中，若1假则假球轻，而若5假则假球重
      第三步：
      操作：左盘12（任一真球），右盘1
               if(平衡)
                    5为假；
      else
1为假；
    }
    else
             {//即左盘重,即( (1,9,10,11) > (2,3,4,5) )
              //说明6,7,8,9,10,11,12为真球；1,2,3,4,5中有假球
             //由第一步反推5若假不能轻，1若假不能为重；2,3,4可轻不可重
             //而1，5若假，则不会出现左盘重这种情况，所以1，5在这里为真球
             //2，3，4里肯定有个假球
     第三步：
           操作：
左盘2，右盘3
if(平衡)
         4假球;
         else
    轻球一方为假；
    }
         }
      }
      else
     {//( (1,2,3,4) > (5,6,7,8) )//即左盘重,
      //方法与上一逻辑同，
     }

Answer 1

推荐正确详细的算法(本人写的)第一次： 1－4在左边  5－8在右边
   if(平衡）
   {
       假球在9－12中；
       第二次： 左边：9 10   右边：1 2 （此时1,2为真球）   
       if(平衡）
          11 12 有假球  （拿个真球，跟其中一个比较就知道了）
       else
          9 10 有假球  （拿个真球，跟其中一个比较就知道了）
       return (OK);
   }
else{
第二次：// 9-12 真球
  左边：1，2，9    右边 5  3 4 （注意：3 4 由第一次的左边到了右边！！！）
  if(平衡）
  {
      说明 假球在 6 7 8 中，并且第一次左边的1 2 3 4 为真球！
      这时，我们可以返回第一步知道，真球重还是真球轻！！！！！
      第三步：左边6  右边7
      if(平衡）
          8 假球
      else
         拿个真球，跟6，7其中一个比较就知道了；
      return(OK);
  }else
   {
    // 说明第一步中的7 8 为真球
  
      if(天平平衡发生了变化）
      {
          3 4 中有假球（假球移动，天平肯定发生变化）；
         （拿个真球，跟其中一个比较就知道了）
          return(OK) !
      }
      else
      {
          3 4 为真球；（真球移动，天平平衡不变）
          // 此时，我们已经发现天平上真球为：9（左边），3 4（右边）
          第三次：左边： 1    右边： 2
          if( 平衡)
              剩下的5为假球
          else
          {
             // 假球在1 2 中，从而也从第一次知道假球的轻重，
                因为第一次的右边5－8为真球，可以看天平的方向
             拿个真球，跟1，2中一个比较就知道了
             return(OK);
           }
       }
   }
}

Answer 2

unrise你好，我同意你的算法，我看过了。
但这个算法你是否给看一下对错？给于bug！！

Answer 3

我发现了推断中的错误!!!else
    {
       if(天平无变化)//即右盘重
       {//说明6,7,8,9,10,11,12为真，1——5有假，
       //由第一步反推假球在1，5中，若1假则假球轻，而若5假则假球重
               ....看你上面的分析!
if(天平无变化)//即右盘重
// 说明2 3 4  和9-12 为真球!!!!因为2 3 4 在第一次中在左边,而在第二次中在右边,结果天平没有发生变化,说明是真球在移动!假球移动肯定发生天平方向发生变化,我已经解释的很清楚了...这个1000块....呵呵,到手了...
你们打赌方,为什么不好好看我上帖的分析呢?

Answer 4

else
        {
    if(天平无变化)//即右盘重
    {//说明6,7,8,9,10,11,12为真，1——5有假，
               //由第一步反推假球在1，5中，若1假则假球轻，而若5假则假球重
：这儿我没有看明白呀，我假设假球为7号球，按你的方法推不下去了？
是我错了还是别的原因呀？

Answer 5

faint,看算法久了，竟然已经有人发了答案？

Answer 6

等楼主把分的80%给我,今天就有机会升级了...   dreaming....

Answer 7

我肯定会准世结贴，
可条件是必须1000元有了明确归属
大家一定的帮我调出bug，
这个算法的重点是 反推&&天平的变化，1000元啊，我的钱可不多呀，

Answer 8

K是题目要求的称天平的次数，则
第一次称取[3^(k-1)-1]个球放在天平天平两端，则：
       如果平衡，获得[3^(k-1)-1]个标准球，坏球在剩下的[3^(k-1)+1]/2个中。由于   [3^(k-1)-1]>=[3^(k-1)+1]/2，（k>=2),即已知的标准球数不小于未知球数? 所以在以后的测量中就相当于任意给定标准球的情况，可知对于[3^(k-1)+1]/2的情况(k-1)次可解。
       如果不平衡，大的那方记做A,小的那方记作B。标准球记做C.
       则现在我们有[3^(k-1)-1]/2个A球和B球，有[3^(k-1)+1]/2个C球。
       第二次用3^(k-2)个A球加[3^(k-2)-1]/2个B球放左边? 3^(k-2)个C球加[3^(k-2)-1]/2个A球放右边。
            如果左边大于右边，则说明是在左边的3^(k-2)个A球中质量大的为坏球；
            如果左边等于右边，则说明是在第二次称时没用的3^(k-2)个B球中质量轻   的为坏球。以上两种情况都可以再用三分法(k-2)次解决，加上前两次共k次解决。
            如果左边小于右边，则坏球在左边的[3^(k-2)-1]/2个B球中或在右边的同样 数目的A球中。此时的情况和第二次开始时类似（只不过是k-1变成k-2).
               用相同的办法一直往下追溯到一个A球和一个B球一次区分的情况，这时  只需拿A球和标准球比较以下就行了。
               因此在这种情况下也是可以最终用k次解决的。

Answer 9

我上面的方法保证需要的次数K一定是最少的！！！！
如果你不限定次数，这题目一定意义都没有，一次一次成不就行了。faint!!!

Answer 10

这道理都被讨论烂了，你怎么还没弄明白啊。
分别为a b c d, e f g h, i j k l，取出abcd, efgh第一种情形：
如果重量相等，则说明所求在 ijkl 中，
称量 i j ，
如果相等，比较 a k ，如果a=k，则所求为 l ；如果ak不等，则所求为 k 。
如果不等，比较 a i ，如果a=i，则所求为 j ；如果不等，则所求为 i 。第二种：
如果 abcd 轻，
在efgh中取出 fgh ，替掉abcd中 bcd，从ijkl中取出 ijk 个放入 e 中填补空位：
如果afgh轻：则说明所求在a或e，拿 e 和除 a 以外的任意一球比较，如果重量相等，则所求的球是 a ；如果不等，则所求的球是 e 。
如果afgh重：说明所求在 fgh 中，且所求较重；比较 f g ，等重则所求为 h ；不等则重的为所求。
如果一样重：说明所求在 bcd 中，且所求较轻；以下同afgh重的情形。第三种：
如果 abcd 重，
在efgh中取出 fgh ，替掉abcd中 bcd，从ijkl中取出 ijk 个放入 e 中填补空位：
如果 afgh 重：则说明所求在a或e，拿 e 和除 a 以外的任意一球比较，如果重量相等，则所求的球是 a ；如果不等，则所求的球是 e 。
如果afgh轻：说明所求在 fgh 中，且所求较轻；比较 f g ，等重则所求为 h ；不等则重的为所求。
如果一样重：说明所求在 bcd 中，且所求较重；以下同afgh轻的情形。

Answer 11

小超的算法三步出不了结果。
     
第三步：左边6  右边7
      if(平衡）
          8 假球
      else
         拿个真球，跟6，7其中一个比较就知道了；拿个真球，跟6，7其中一个比较就知道了；这可就是第四次比较了。所以请你别在要分了。没有资格。呵呵！

Answer 12

to: mrwws() 第三步：左边6  右边7
      if(平衡）
          8 假球
      else
         拿个真球，跟6，7其中一个比较就知道了；// 不好意思,我解释错误了,步骤还是对的...if(平衡）
    8 假球
else
    6 7 中有假球,由第一次天平(1-4真球在左边)的方向知道假球的轻重,
    因此从 6 7 的天平方向就可以知道哪个是假球了...

Answer 13

感谢大家，终于答案对了
我结贴！！！
哈哈!
如果谁还认为这个算法有问题请致电：[email protected]通知我