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

[ncdx2009]

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

[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