还是告诉你们答案好了。
把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轻的情形。
其实这道题以前有人问过我,上算法分析课的时候无聊,用了一节课的时间把它做了出来。速度还可以吧 ^^ |