找坏球

http://lixinzhang.github.io/jiu-zhang-suan-fa-mian-shi-ti-zong-jie.html

有12个球，1个没有砝码的天秤。其中有11个球的重量是一样的，另外1个是坏球，和其他球的重量不一样，但无法确定是轻了还是重了。请问如何用天秤称3次，就找到坏球并确定是轻了还是重了。（没有砝码的天秤只能比较出两边谁重谁轻或是重量相等，无法求得具体的重量差）

分析

12个球，编号A=（1，2，3，4 ）B=（5，6，7，8）C=（9，10，11，12）

分为三组:A, B, C。

• 先比较A,B,如果A与B平衡，则A，B中均为好球
  • 比较5，6，7与9，10，11
    • 若平衡，则坏球为8或12
      • 比较8与任何一个好球，平衡，坏球为12；不平，坏球为8。
    • 若不平，则目前可以知道是坏的球比好球是重还是轻，假设为重
      • 比较9，10，若平衡，则坏球为12；不平，坏球为重的那个
• 若A，B不平，则C为好球
  • 比较1，2，5 与 3，4，6（交叉，这玩意面试的时候能想到？）
    • 若平衡，则坏球在7，8之间，且之前已经得知轻重的一个关系，再比较一次7，8
    • 若不平衡，或者1，2为坏球，或者5，6为坏球，再比较一次