12 枚金币中有 1 枚是假的,用天平称 3 次找出结果。

2016-04-04 12:15:43 +08:00
 ncdx2009
12 枚金币外观相同,正常金币重量是标准一致的,假金币只是重量异常,天平没有砝码,如何只称 3 次,找出假金币以及它比正常金币轻了还是重了。
这个问题,网上随便一搜就能找到答案,只是金币换成了小球或别的什么。
有没有用编程作一个通用的解决办法?例如 120 枚中 1 枚假的,称 5 次能不能找出假金币的轻重等
试着用穷举法做了一个,发现计算量有点大。
求思路或答案。
5973 次点击
所在节点    问与答
32 条回复
luguozmy
2016-04-04 14:27:32 +08:00
https://en.wikipedia.org/wiki/Balance_puzzle
https://zh.wikipedia.org/wiki/%E7%A8%B1%E7%90%83%E5%95%8F%E9%A1%8C

我记得这是以前初中的智力题, 不难的, 我家那个小弟弟认真想想就可以解出来
loading
2016-04-04 14:28:07 +08:00
这一题不是考智商的,这是一个记忆题,因为这个题目已经烂大街了…
pimin
2016-04-04 14:50:57 +08:00
@Xs0ul
13 和 12 真的没区别吧
一样解法
vietor
2016-04-04 14:51:02 +08:00
@ncdx2009 金的密度高,所以假的肯定轻
ncdx2009
2016-04-04 15:03:51 +08:00
@pimin 13 称 3 次,好像真的解决不了,操作上不能实现。类似简单的 4 枚称 2 次,信息论上可行,操作上不能实现。

@vietor ,金币中含金量是有限的,不能排除使用含金量高的“假金币”来走私黄金
Xs0ul
2016-04-04 15:04:09 +08:00
@pimin 称球问题是指若在最多 (3^n-3)/2 个球中有一个特殊球的重量与众不同(不知道偏重还是偏轻),而其他球的重量全部相同,则用无砝码的天平称 n 次可以找出特殊球,并确定特殊球是偏轻还是偏重;如果有 (3^n-1)/2 个球,则同样可以保证找出特殊球,但不一定能确定特殊球是偏轻还是偏重
来自维基百科 https://zh.wikipedia.org/wiki/%E7%A8%B1%E7%90%83%E5%95%8F%E9%A1%8C

@ncdx2009 楼主可以看看维基百科提到的矩阵解法
ncdx2009
2016-04-04 15:54:50 +08:00
@Xs0ul 目前是按照这个矩阵解法进行的编程练习, 这解法的数量增长太快了,12 枚称 3 次是 2 的 12 次方(4 位数) , 到 120 枚称 5 次是 2 的 120 次方(37 位数) 。
kaizixyz
2016-04-04 17:27:51 +08:00
12 个球有 1 个异常。可能性有 24 种。称相当于 3 进制。所以 3 位的编码就够了。理论上 13 个球应该也行啊。求大神来个 13 球版的
RqPS6rhmP3Nyn3Tm
2016-04-04 19:09:32 +08:00
这不是很简单吗,二进制编码原理
USCONAN
2016-04-04 19:25:01 +08:00
malcolmyu
2016-04-04 21:09:02 +08:00
@amet @kaizixyz 正解,信息论的题,天平有三种状态,假球有 2N 种状态,只要 3^m > 2N 就一定能求解
yelite
2016-04-05 23:30:58 +08:00
@amet 信息论只能给出下界,如果有两个是假的,那好像是找不出实际方案来达到信息论下界的上取整的

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/268442

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX