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

[ncdx2009]

12 枚金币外观相同，正常金币重量是标准一致的，假金币只是重量异常，天平没有砝码，如何只称 3 次，找出假金币以及它比正常金币轻了还是重了。
这个问题，网上随便一搜就能找到答案，只是金币换成了小球或别的什么。
有没有用编程作一个通用的解决办法？例如 120 枚中 1 枚假的，称 5 次能不能找出假金币的轻重等
试着用穷举法做了一个，发现计算量有点大。
求思路或答案。

还是写个答案吧，有些人不认真读题了。。。
这种格式的答案， 楼主穷举了一下，有 304 个，大致就是按照按照 21 楼链接中的方法——矩阵乘法。但这个按照算法，称 5 次时，数量已经大了很多，现在还没算出来 120 枚称 5 次时的答案。楼主更感兴趣的怎么用编程方法，解决这来问题。

一 01, 02, 03, 04 09, 10, 11, 12
二 01, 05, 06, 09 03, 04, 08, 12
三 02, 05, 07, 10 01, 04, 06, 09
结果清单如下
L,O,R 分别表示天平的结果:左重,平衡,右重，
L L R 01 重
L O L 02 重
L R O 03 重
L R R 04 重
O L L 05 重
O L R 06 重
O O L 07 重
O R O 08 重
R L R 09 重
R O L 10 重
R O O 11 重
R R O 12 重
O O O 无
R R L 01 轻
R O R 02 轻
R L O 03 轻
R L L 04 轻
O R R 05 轻
O R L 06 轻
O O R 07 轻
O L O 08 轻
L R L 09 轻
L O R 10 轻
L O O 11 轻
L L O 12 轻

[hinate]

2 分

[vietor]

6,3,1

[zhjits]

每次等分三份，称其中两份

[ncdx2009]

@hinate @vietor 这个只是找出假金币，但是没有找出假金币比正常金币轻了还是重了
@zhjits 这个好像也找不出轻重的。

[smallfount]

在不知道轻还是重的情况下 2 分不能解决...因为第一次称好了完全不知道到底哪个是标准的...
所以至少也得是 3 分....

[sorcerer]

@ncdx2009 为什么会找不出轻重？

[sorcerer]

@sorcerer 哦有次数规定

[Fleeting]

3 分吧

[sciooga]

这题很有趣，小学的时候我爸喜欢给我出这种益智题，当时拿到这道题真的没头绪，晚上睡觉后闭上眼想了半个小时想出来激动得...

给几个提示：
1.给每个硬币编号。
2.硬币间可以交换位置，看天平重轻方向是否改变。
3.原题关键字是“ 12 个乒乓球特征相同 其中只有一个重量异常”搜一搜就有答案了。

[srlp]

一个天平可以比较三份数目相等的硬币，楼主按照这个思路就行

[233]

很经典的题目，从小学做到工作。关键的一步就是在第二次测量时要重新分组

[allan888]

这个之前看过，我说详细点好了，假设硬币叫做 1-12 ：
a. 分 3 份，分别是 1-4 ， 5-8 ， 9-12 ，称 1-4 和 9-8 ，平的话就在 9-12 ，没啥好说的。
b.假设 1 ， 2 ， 3 ， 4 轻， 5 ， 6 ， 7 ， 8 重，那么确定 9 ， 10 ， 11 ， 12 是真的硬币。
c.拿出 1 和 3 个 9-12 里面的，比如 1 ， 9 ， 10 ， 11 ，这里面只有 1 需要确定是不是假的。
d.拿出 1 ， 9 ， 10 ， 11 和 2 ， 3 ， 4 ， 5 称，如果平的话就是 6 ， 7 ， 8 有问题，不用说了。

e.如果 1 ， 9 ， 10 ， 11 轻，那么 1 ， 5 有问题，因为 6 ， 7 ， 8 已经知道没问题， 2 ， 3 ， 4 有问题的话现在 2 ， 3 ， 4 从左边换到了右边，右边应该轻才对， 1 ， 5 有问题的话把 1 和一个真币称一下就知道谁是假币了。

f.如果 1 ， 9 ， 10 ， 11 重，那么 2 ， 3 ， 4 有问题，因为 1 ， 5 有问题的话 1 ， 5 都没有换边，轻重不会变，其实就是 2 ， 3 ， 4 换了位置导致轻重关系变了，到这步的话确定假币是偏轻的。 2 ， 3 ， 4 里面， 2 和 3 称一下轻的是假的，平的话 4 是假的。

[amet]

信息论的题，刚学
称重可能得到三种结果:一边轻、一边重、两边平衡
H_1(x)=log(2)(3)
一共有 N 个球，假球可能轻可能重， N*2
H_2(x)=log(2)(2N)
需要最少次数在( H_1(x)/H_2(x) , H_1(x)/H_2(x)+1 )之间取整数
120 个球即 N=120
H_1(x)/H_2(x)=4.98869 ……
所以 5 次肯定可以
LaTeX 不熟，不会写对数，公式都是以 2 为底，将就看吧

[amet]

@amet 计算次数时分子分母写反了 ……

[sigone]

6/6 ， 3/3 ， 1/1 (1-1-1 排除法)

幼儿园水平水平

[steveshi]

金田一做过这个题目……

[Xs0ul]

@amet 按照你这里的理论， 3 次应该可以分 13 个球（ 3^3 > 13*2 ），然而我见到的题目全是 12 ，我相信不是出题者和做题者没有想到 13 的解法。事实上你不能保证每次获得的信息都是最好的（或者说是对于各种情况都是比较平均的），比如可能在某一步一边重留下的情况比较多，一样重留下的情况比较少。

[mfinal]

@sigone 强调了不知道有问题是轻 or 重🙈，不仔细看题也看看前面的评论吧..

[Exin]

@mfinal 我问过不少人这个题目，一半的人脱口而出“二分法”、“真简单”，说明都太自信了。

[mimzy]

只针对这道题的话 第一次看见是在这里 http://blog.csdn.net/pongba/archive/2008/06/13/2544933.aspx

[luguozmy]

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]

这一题不是考智商的，这是一个记忆题，因为这个题目已经烂大街了…

[pimin]

@Xs0ul
13 和 12 真的没区别吧
一样解法

[vietor]

@ncdx2009 金的密度高，所以假的肯定轻

[ncdx2009]

@pimin 13 称 3 次，好像真的解决不了，操作上不能实现。类似简单的 4 枚称 2 次，信息论上可行，操作上不能实现。

@vietor ，金币中含金量是有限的，不能排除使用含金量高的“假金币”来走私黄金

[Xs0ul]

@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]

@Xs0ul 目前是按照这个矩阵解法进行的编程练习, 这解法的数量增长太快了,12 枚称 3 次是 2 的 12 次方(4 位数) , 到 120 枚称 5 次是 2 的 120 次方(37 位数) 。

[kaizixyz]

12 个球有 1 个异常。可能性有 24 种。称相当于 3 进制。所以 3 位的编码就够了。理论上 13 个球应该也行啊。求大神来个 13 球版的

[RqPS6rhmP3Nyn3Tm]

这不是很简单吗，二进制编码原理

[USCONAN]

https://github.com/jonseymour/12coins

[malcolmyu]

@amet @kaizixyz 正解，信息论的题，天平有三种状态，假球有 2N 种状态，只要 3^m > 2N 就一定能求解

[yelite]

@amet 信息论只能给出下界，如果有两个是假的，那好像是找不出实际方案来达到信息论下界的上取整的