考考大家的逻辑能力（12球问题）
上班无聊来灌一下水，前段时间花了些心思解出了一道蛮难的题，也出给大家：12球问题：有12个几乎一样的球，其中有1个特殊球，除质量与其它不同之外其它各方面都相同（注：不知是比较重还是比较轻）。现有一天平（无砝码）请你只称3次把那个特殊球找出来。 有奖励吗？没有我不做 还是告诉你们答案好了。
把12个球分别记为abcd,efgh,ijkl,并且分为三组,取出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轻的情形。
其实这道题以前有人问过我，上算法分析课的时候无聊，用了一节课的时间把它做了出来。速度还可以吧 ^^ 有奖励吗？没有我不做你是不已经知道答案了.
知道答案？我自己做出来的。
我还将解题过程做成了一张图表，其过程一目了然，思路之清晰堪称天才之作。 ^^ 这是一个很经典的问题，关键就是找出标准质量，当砝码。 没劲了！还没看到呢，答案都出来了！ 看了题目就知道怎么做了……以前看过类似的…… 1995年的science有数学推导，在计算机学上是找路径问题，树的求解
12球最坏情况下的最短路径是3
1001个球最坏情况下的最短路径是9
看出规律了吧；不过球多了人去找很麻烦，这东西用在质量管理上比较多
做游戏能作出12个球也厉害，毕竟是人计算出来的 这个东西在计算机课上好像讲过（信息竞赛）
页:
[1]